排序算法总结。
排序算法
这里讨论的一律是对整数排序，并且目标是从小到大排序。
常见排序算法
冒泡排序
冒泡排序是通过每次比较相邻的两个元素，如果顺序错误就交换他们的位置来进行排序，一趟遍历下来，最大的元素就在正确的位置上了，每趟遍历，都要进行很多的元素位置交换，对一个大小为N的数组进行排序，需要进行N-1这样的遍历，需要$O(n^2)$的比较和交换。
冒泡排序的最坏和平均时间复杂度是$O(n^2)$,空间复杂度为$O(1)$,是一种原地的，稳定的排序算法。在复杂度为$O(n^2)$的排序算法中，冒泡的效率也没有其他的插入排序和选择排序高。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
| public static <T extends Comparable<? super T>> void bubbleSort(T[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 1; j < array.length - i; j++) {
if (array[j-1].compareTo(array[j]) > 0) {
swap(array, j-1, j);
}
}
}
}
|
鸡尾酒排序
冒泡排序的变形版，是在两端来回的遍历，将最大值置换到最后，将最小置换到最前。就像一个球在两堵墙之间不断的来回弹，随着来回弹的次数增加，两堵墙之间的距离越来越小，当两堵墙相遇时，就排好序了。
鸡尾酒排序的最好和最坏时间复杂度还是$O(n^2)$，与冒泡不同的一点是对于已经差不多排好序的数组，其比较次数会比冒泡少。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static <T extends Comparable<? super T>> void cocktailSort(T[] array) {
for (int i = 0; i < array.length / 2; i++) {
for (int j = i; j < array.length - 1; j++) {
if (array[j].compareTo(array[j+1]) > 0) {
swap(array, j, j+1);
}
}
for (int j = array.length - 1 - i; j > i + 1; j--) {
if (array[j].compareTo(array[j-1]) < 0) {
swap(array, j-1, j);
}
}
}
}
|
插入排序
插入排序是通过将元素插入到已排序序列的适当位置来实现排序。一开始，认为第一个元素是已排序的，然后，从第二个元素开始，向前遍历，在每次比较的时候，将较大的值后移，直到找到合适的位置插入。
插入排序的平均和最坏时间复杂度为$O(n^2)$，平均需要$O(n^2)$次比较，空间复杂度是$O(1)$，是一种原地的，稳定的排序算法。
排序过程
例子
java代码实现
1
2
3
4
5
6
7
8
9
10
11
| public static <T extends Comparable<? super T>> void insertionSort(T[] array, int left, int right) {
for (int i = left+1; i <= right; i++) {
T tmp = array[i];
int j = i;
while (j > 0 && tmp.compareTo(array[j-1]) < 0) {
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
}
|
选择排序
选择排序通过是每次选择未排序的序列中最小的元素，插入到已排序序列的最后位置来排序。
选择排序的平均和最坏时间复杂度为$O(n^2)$，$O(n)$次交换，空间复杂度为$O(1)$，是一种原地的，不稳定排序算法。
稳定性的反例：对 $3_1\ 2\ 3_2\ 1\ 4$ 进行选择排序，在第一次交换时，$3_i$会与$1$进行交换，最后排好序的样子是这样的 $1\ 2\ 3_2\ 3_1\ 4$，$3$的原先的顺序改变了。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static <T extends Comparable<? super T>> void selectionSort(T[] array) {
for (int i = 0; i < array.length - 1; i++) {
T min = array[i];
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if (min.compareTo(array[j]) > 0) {
min = array[j];
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
|
归并排序
归并排序采用分治思想的排序算法，将数组分成两部分，分别对这两部分进行归并排序，最后将排序好的两部分进行合并。
归并算法的平均和最坏时间复杂度为$O(nlogn)$，空间复杂度是$O(n)$,因为需要额外的一个数组来进行合并操作，是个稳定的排序算法。java的Arrays类中的sort方法就使用到了归并排序。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| @SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] array) {
T[] tmp = (T[]) new Comparable[array.length];
mergeSort(array, tmp, 0, array.length-1);
}
private static <T extends Comparable<? super T>> void mergeSort(T[] array, T[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(array, tmpArray, left, center);
mergeSort(array, tmpArray, center+1, right);
merge(array, tmpArray, left, center+1, right);
}
}
private static <T extends Comparable<? super T>> void merge(T[] array, T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int num = rightEnd - leftPos + 1;
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (array[leftPos].compareTo(array[rightPos]) < 0) {
tmpArray[tmpPos++] = array[leftPos++];
} else {
tmpArray[tmpPos++] = array[rightPos++];
}
}
while (leftPos <= leftEnd) {
tmpArray[tmpPos++] = array[leftPos++];
}
while (rightPos <= rightEnd) {
tmpArray[tmpPos++] = array[rightPos++];
}
for (int i = 0; i < num; i++,rightEnd--) {
array[rightEnd] = tmpArray[rightEnd];
}
}
|
希尔排序
希尔排序就是不断减少间隔的插入排序。
首先选定一个间隔gap，然后对所有间隔gap的数进行插入排序，这样所有间隔gap的数都是有序的，然后减小间隔gap，再次对所有间隔gap的数进行排序，不断重复这样的操作，直到间隔gap为1执行普通的插入排序，此时，数组是大致有序的，所以执行插入排序比较快。
对间隔gap的选择会影响算法的性能，简便起见可以选择数组长度的一半。希尔排序的复杂度分析比较复杂，一般可以认为平均时间复杂度为$O(nlogn)$，空间复杂度为$O(1)$。是一种原地的，不稳定排序算法。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static <T extends Comparable<? super T>> void shellSort(T[] array) {
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
T tmp = array[i];
int j = i;
while (j >= gap && tmp.compareTo(array[j-gap]) < 0) {
array[j] = array[j-gap];
j -= gap;
}
array[j] = tmp;
}
}
}
|
堆排序
堆排序是借助堆(最大堆，最小堆)来进行排序的。首先建堆，然后通过n次的删除操作来得到有序序列。
堆排序的平均和最坏时间复杂度为$O(nlog)$，空间复杂度为$O(1)$。是一种原地不稳定排序算法。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public static <T extends Comparable<? super T>> void heapSort(T[] array) {
for (int i = array.length / 2; i >= 0; i--) {
percDown(array, i, array.length);
}
for (int i = array.length-1; i >= 0; i--) {
swap(array, 0, i);
percDown(array, 0, i);
}
}
build max heap
i 是要下沉的节点
n 是heap的大小
*/
private static <T extends Comparable<? super T>> void percDown(T[] array, int i, int n) {
T tmp = array[i];
while (leftChild(i) < n) {
int child = leftChild(i);
if (child != n-1 && array[child+1].compareTo(array[child]) > 0) {
child++;
}
if (tmp.compareTo(array[child]) < 0) {
array[i] = array[child];
} else {
break;
}
i = child;
}
array[i] = tmp;
}
private static int leftChild(int i) {
return 2 * i + 1;
}
|
快速排序
快速排序也是采用分治思想的一个排序算法，将数组分成两部分，对这两部分分别进行快速排序。
在对数组进行分的时候，选择一个值作为pivot，将数组分为小于pivot的和大于pivot的两部分，pivot选的好坏将直接影响快速排序的算法性能。一个好的pivot需要将数组平均分成两部分，一般可以选择这么一个策略：选择数组头尾两个数和中间一个数这三个数中大小处于中间的那个数作为pivot。
快速排序的平均时间复杂度为$O(nlogn)$，最坏时间复杂度为$O(n^2)$，这是因为pivot选择的不好，使得数组的划分成一个数组只有1个元素，另一个数组拥有剩下的所有元素。考虑到递归调用，空间复杂度为$O(logn)$。java的Arrays类中的sort方法在数组比较小(small array)的时候就使用的快速排序(Dual Pivot Quicksort)，在Dual Pivot Quicksort中，当数组很小(tiny array)的时候使用插入排序。
排序过程
java代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| public static <T extends Comparable<? super T>> void quickSort(T[] array) {
quickSort(array, 0, array.length-1);
}
private static <T extends Comparable<? super T>> void quickSort(T[] array, int left, int right) {
if (left + 10 <= right) {
T pivot = median3(array, left, right);
int i = left, j = right - 1;
while (true) {
while (array[++i].compareTo(pivot) < 0) {}
while (array[--j].compareTo(pivot) > 0) {}
if (i < j) {
swap(array, i, j);
} else {
break;
}
}
swap(array, i, right-1);
quickSort(array, left, i - 1);
quickSort(array, i+1, right);
} else {
insertionSort(array, left, right);
}
}
private static <T extends Comparable<? super T>> T median3(T[] array, int left, int right) {
int center = (left + right) / 2;
if (array[center].compareTo(array[left]) < 0) {
swap(array, left, center);
}
if (array[left].compareTo(array[right]) > 0) {
swap(array, left, right);
}
if (array[center].compareTo(array[right]) > 0) {
swap(array, center, right);
}
swap(array, center, right-1);
return array[right-1];
}
|
计数排序
计数排序
计数排序是通过统计数组中各个值的个数来进行排序的排序算法，不需要进行比较，所以就没有了$O(nlogn)$的时间下限限制。
计数排序首先算出整个待排数组的值的范围，然后统计每个值的个数，接着根据这个来排序。
步骤：
- 找出待排序数组的最大值和最小值
- 统计数组中每个值i出现的次数，存入数组C[i]中
- 对数组C进行累加，即C[i] += C[i-1]
- 反向填充目标数组
长度为n的范围在0-k之间的数组，计数排序的时间复杂度是$O(n+k)$，空间复杂度为$O(n+k)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public static int[] sort(int[] unsorted) {
int max = 0, min = 0;
for (int i : unsorted) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int[] count = new int[max - min + 1];
for (int i : unsorted) {
count[i]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
int[] sorted = new int[unsorted.length];
for (int val : unsorted) {
sorted[count[val] - 1] = val;
count[val]--;
}
return sorted;
}
|
总结
| 名称 |
稳定性 |
平均时间复杂度 |
最坏时间复杂度 |
空间复杂度 |
| 冒泡排序 |
稳定 |
$O(n^2)$ |
$O(n^2)$ |
$O(1)$ |
| 插入排序 |
稳定 |
$O(n^2)$ |
$O(n^2)$ |
$O(1)$ |
| 选择排序 |
不稳定 |
$O(n^2)$ |
$O(n^2)$ |
$O(1)$ |
| 归并排序 |
稳定 |
$O(nlogn)$ |
$O(nlogn)$ |
$O(n)$ |
| 希尔排序 |
不稳定 |
$O(nlogn)$ |
$O(n^i)$1< i<2 |
$O(1)$ |
| 堆排序 |
不稳定 |
$O(nlogn)$ |
$O(nlogn)$ |
$O(1)$ |
| 快速排序 |
不稳定 |
$O(nlogn)$ |
$O(n^2)$ |
$O(logn)$ |
| 计数排序 |
稳定 |
$O(n+k)$ |
$O(n+k)$ |
$O(n+k)$ |