常见的几种排序算法按照是否需要进行两个元素的比较可以分为两类:

  • 比较排序 。比较排序的时间复杂度的下限是:O(n*lgn)常见的比较排序算法有(冒泡排序、选择排序、快速排序、插入排序、堆排序、归并排序)
  • 非比较排序 。非比较排序的数据输入有一定的要求。比如:输入数据是在某一范围内的整数。这类输入数据的排序时间复杂度可以突破O(n*lgn)的下界。达到O(n)。(常见的非比较排序有:基数排序、计数排序、shell排序)
    如下的内容将给我各个排序算法的源代码。并对其进行对比分析。

名词解释

排序算法稳定性:在一个待排序的序列中,如果 a[i]=a[j](其中i在j之前),经过排序之后仍然有a[i]在a[j]之前(i,j的相对顺序不变)则称该排序算法是稳定排序算法,反之如果i,j的顺序发生变化,则称该排序算法为非稳定排序。

辅助空间:在该排序算法中除了输入数组需要额外使用的空间。

各个排序算法的时间复杂度

排序名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 是否稳定 辅助空间
冒泡排序 O(n) O(n^2) O(n^2) 稳定 O(1)
选择排序 O(n^2) O(n^2) O(n^2) 不稳定 O(1)
插入排序 O(n) O(n^2) O(n^2) 稳定 O(1)
快速排序 O(n*lgn) O(n^2) O(n*lgn) 不稳定 O(1)
归并排序 O(n*lgn) O(n^2) O(n*lgn) 2 不稳定 O(n*lgn)
堆排序 O(n*lgn) —- —- —- —-
基数排序 O(d(n+k)) O(d(n+k)) O(d(n+k)) 不稳定 —-
计数排序 O(k+n) O(k+n) O(k+n) 不稳定 —-
桶排序 O(n) O(n) O(n^2) 不稳定 —-

比较排序

冒泡排序

冒泡排序需要重复遍历排序的序列,一次比较两个元素,如果他们的顺序与需求的顺序相反,就将他们进行交换,直到没有需要交换的元素为止。

冒泡排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.qunar.dzs.datahub.common.sort;
import com.alibaba.fastjson.JSONObject;
/*
* Created by guochenglai on 8/3/16.
*/
public class BubbleSort {
public static void main(String[] args) {
int a[] = {8, 3, 9, 0, 2, 4, 1, 7, 6};
System.out.println("origin array is :" +JSONObject.toJSONString(a));
for (int i = 0; i < a.length ; ++i) {
for (int j = 0 ; j < a.length - 1 -i ; ++j) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
System.out.println("sorted array is : "+JSONObject.toJSONString(a));
}
}

或者使用如下的代码排序

1
2
3
4
5
6
7
8
9
for (int i = a.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}

冒泡排序的注意点:冒泡排序最容易和选择排序弄混淆。在区分这两种排序算法的时候只需要记住一个关键点。冒泡排序采用大数下沉的方法。第一次循环第n个元素为最大值,第二次循环第n-1个元素为次大值,循环的大小每次减一

选择排序

选择排序首先从未排序的序列中找到最大(小)值,与第一个元素进行交换。然后找到第二大值与第二个元素交换 …. 以此类推。直到排序完成。

选择排序较冒泡排序对比:

  • 选择排序每次只交换一对元素。而冒泡排序每次需要交换O(n)对元素。
  • 选择排序是不稳定的。例如对于序列: 3 3 1 经过第一次选择,第一个元素排到了第三个位置,这样两个“3”的相对位置就发生了变化。所以选择排序是非稳定排序。

选择排序代码

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
package com.qunar.dzs.datahub.common.sort;
import com.alibaba.fastjson.JSONObject;
/*
* Created by guochenglai on 8/4/16.
*/
public class SelectionSort {
public static void main(String[] args) {
int a[] = {8, 3, 9, 0, 2, 4, 1, 7, 6};
System.out.println("origin array is :" + JSONObject.toJSONString(a));
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
min = j;
}
}
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
System.out.println("sorted array is : "+JSONObject.toJSONString(a));
}
}

插入排序

插入排序的形象化理解就是我们平常在玩牌,取一张新牌插入到手中牌的正确位置。它的工作原理是构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到相应的位置并插入。
插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package com.qunar.dzs.datahub.common.sort;
import com.alibaba.fastjson.JSONObject;
/*
* Created by guochenglai on 8/4/16.
*/
public class InsertionSort {
public static void main(String[] args) {
int a[] = {8, 3, 9, 0, 2, 4, 1, 7, 6};
System.out.println("origin array is :" + JSONObject.toJSONString(a));
for (int i = 1; i < a.length; i++) {
int tmp = a[i];
for (int j = i - 1; j >= 0 && a[j] > tmp; j--) {
a[j + 1] = a[j];
a[j] = tmp;
}
}
System.out.println("sorted array is : "+JSONObject.toJSONString(a));
}
}

快速排序

快速排序是一个典型的使用分治法进行排序的算法。按照分治法的思想,一个快速排序过程分为如下三个过程:

  • Divide 将一个大的排序序列划分为若干个小的排序序列
  • Conquer 当一个排序序列足够小的对其进行排序或者直接排序
  • Combine 将若干个小的排序序列进行整合最后得到需要排序的序列
    根据上述的三个过程可以得到快速排序的伪代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
QUICKSORT(A,p,r)
if p<r
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
```
```java
PARTITION(A,p,r)
tmp = A[r]
i = p-1
for(j = p to r-1)
if A[j] <= tmp
i++
swap(A[i],A[j])
swap(A[i+1],A[r])
return i+1

快速排序的代码

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
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}

归并排序

归并排序和快速排序一样,都是采用分治的思想,他们的主要区别是:

  • 归并排序是将原问题划分为两个子问题之后分别进行排序,然后在对排序之后的结果进行合并操作。
  • 快速排序的子问题进行排序之后,不需要进行归并的过程。

归并排序的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
MERGESORT(A,p,r)
if p<r
q=(p+r)/2
MERGESORT(A,p,q)
MERGESORT(A,q+1,r)
MERGE(A,p,q,r)
MERGE(A,p,q,r)
n1 = q-p+1
n2 = r-q
for i=1 to n1
L[i] = A[p+i-1]
for j=1 to n2
R[j] = A[q+j]
for k=p to r
if L[i] <= R[j]
A[k] = L[i]
i++
ELSE
A[k] = R[j]
j++

归并排序的代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class Mergesort {
private int[] numbers;
private int[] helper;
private int number;
public void sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = new int[number];
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
if (low < high) {
int middle = low + (high - low) / 2;
mergesort(low, middle);
mergesort(middle + 1, high);
merge(low, middle, high);
}
}
private void merge(int low, int middle, int high) {
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
}
```
### 堆排序
堆排序可以拆解为以下的几个子过程:
* 建立大根堆
* 交换堆定的元素和最后一个元素,并将堆大小减一
* 调整大根堆
可用如下的伪代码来表示:
```java
HEAPSORT(A)
BUILD_MAX_HEAP(A) //建立最大堆
for(i= A.length downto 2)
swap(A[1],A[i])
A.length--
MAX_HEAPIFY(A,1) //维护最大堆的性质

从上面的伪代码可以看到两个组要过程,BUILD_MAX_HEAP(建立最大堆)和MAX_HEAPIFY(调整最大堆)
下面先看一下MAX_HEAP(维护最大堆的性质)的实现过程

1
2
3
MAX_HEAPIFY(A,i)
....

有了MAX_HEAP的过程,那么构建最大堆就比较容易了。直接上代码:

1
2
3
4
5
6
7
8
BUILD_MAX_HEAP(A)
A.heapSize = A.length
for( i=A.length/2 downto 1)
MAX_HEAPIFY(A,i)

非比较排序

基数排序

计数排序

桶排序