常用排序方式分析与比较

下面选取在实际项目中应用较多的排序方式作一个性能比较,并会对各个方式作一个分析总结。

排序性能比较

测试方案

  1. 随机生成10万个整型数字,作为待排序数据。
  2. 逐个应用各个排序算法,通过计算开始至结束时间来获得算法执行时间,然后对其进行排序。

测试结果

排序算法 耗时(ms)
直接插入排序 769
希尔排序 10
冒泡排序 18,557
*快速排序 9
直接选择排序 3,811
*堆排序 10
归并排序 20

分析

稳定性

  1. 直接插入、冒泡和归并排序算法是稳定的。
  2. 直接选择、希尔、快速和堆排序算法是不稳定的。

排序方法的选取

  1. 若待排序的一组记录数目n较小(如n<=50)时可采用插入排序或选择排序。
  2. 若n较大时应该采用快速排序、堆排序或归并排序。

排序方法对记录存储方式的要求

一般的排序方法都可以在顺序结构(一维数组)上实现。当记录本身信息量较大时,为了避免移动记录耗费大量的时间,可以采用链式存储结构。例如插入排序、归并排序和基数排序(未评测)易于在链表上实现,使之减少记录的移动次数。但有的排序方法,如快速排序、堆排序在链表上却难以实现,在这种情况下可以提取关键字建立索引表,然后对索引表进行排序。

排序方式实现

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 插入排序:直接插入排序
*/
public static void inlineSort(int[] data) {
int j, tmp;
for (int i = 1; i < data.length; i++) {
//若data[i]大于等于有序区中所有的元素则data[i]不动
if (data[i] < data[i - 1]) {
//把当前元素复制一份副本
tmp = data[i];
//找插入位置
for (j = i - 1; j > -1 && tmp < data[j]; j--) {
//元素后移
data[j + 1] = data[j];
}
//插入data[i]到正确位置
data[j + 1] = tmp;
}
}
}

希尔排序

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
/**
* 插入排序:希尔排序
*/
public static void shellSort(int[] data) {
//计算最大分组间隔
int increment = 1;
while (increment <= data.length / 3) {
increment = increment * 3 + 1;
}

//按照增量序列对顺序表data希尔排序
for (; increment > 0; increment = (increment - 1) / 3) {
shellInsert(data, increment);
}
}

/**
* 希尔排序中的一趟插入排序
*
* @param data 待排序数组
* @param increment 当前增量
*/
private static void shellInsert(int[] data, int increment) {
int j, tmp;
//将data[dk+1...]分别插入有序区
for (int i = increment; i < data.length; i++) {
if (data[i] < data[i - increment]) {
//把当前元素复制一份副本
tmp = data[i];
j = i - increment;
while (j > -1 && tmp < data[j]) {
//元素后移,查找插入位置
data[j + increment] = data[j];
//查找前一记录
j = j - increment;
}
//插入data[i]到正确位置
data[j + increment] = tmp;
}
}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 交换排序:冒泡排序
*
* @param data 待排序数组
*/
public static void bubbleSort(int[] data) {
int tmp;
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data.length - 1; j++) {
if (data[j] > data[j + 1]) {
tmp = data[j + 1];
data[j + 1] = data[j];
data[j] = tmp;
}
}
}
}

快速排序

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
/**
* 交换排序:快速排序(划分交换排序),是对冒泡排序的一种改进。
*
* @param data 待排序数组
*/
public static void quickSort(int[] data, int low, int high) {
if (low < high) {
//做一次划分排序
int p = partition(data, low, high);
//对左区间递归排序
quickSort(data, low, p - 1);
//对右区间递归排序
quickSort(data, p + 1, high);
}
}

/**
* 一趟划分算法
*
* @param data 待排序数组
* @param i 划分区间
* @param j 划分区间
* @return
*/
private static int partition(int[] data, int i, int j) {
//用区间的第一个记录为基准
int tmp = data[i];
while (i < j) {
while (i < j && data[j] >= tmp) {
//从j所指的位置起向前(左)搜索
j--;
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] <= tmp) {
//从i所指的位置起向后(右)搜索
i++;
}
if (i < j) {
data[j] = data[i];
j--;
}
}
//基准记录tmp位于最终排序的位置i上
data[i] = tmp;
return i;
}

直接选择排序

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
/**
* 选择排序:直接选择排序
*
* @param data 待排序数组
*/
public static void straightSelectSort(int[] data) {
int k, tmp;
//做length-1趟排序
for (int i = 0; i < data.length - 1; i++) {
//设k为第i趟排序中关键字最小的记录位置
k = i;
//在[i...length-1]选择关键字最小的记录
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[k]) {
//若有比data[k]小的记录则记住该位置
k = j;
}
}
if (k != i) {
//与第i个记录交换
tmp = data[i];
data[i] = data[k];
data[k] = tmp;
}
}
}

堆排序

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
/**
* 选择排序:堆排序,是对直接选择排序法的一种改进。
*
* @param data 待排序数组
*/
public static void heapSort(int[] data) {
int i, tmp;
for (i = (data.length - 1) / 2; i >= 0; i--) {
sift(data, i, (data.length - 1));
}
for (i = (data.length - 1); i >= 1; i--) {
tmp = data[0];
data[0] = data[i];
data[i] = tmp;
sift(data, 0, i - 1);
}
}

/**
* 调整为大根堆
*
* @param data 待排序数组
* @param i 开始
* @param h 结束
*/
private static void sift(int[] data, int i, int h) {
int x = data[i];
int j = 2 * i;
while (j <= h) {
if (j < h && data[j] < data[j + 1]) {
j++;
}
if (x >= data[j]) {
break;
}
data[i] = data[j];
i = j;
j = 2 * i;
}
data[i] = x;
}

归并排序

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
/**
* 归并排序
*
* @param data 待排序数组
* @param n 待排序数组长度
*/
public static void mergeSort(int[] data, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];

for (int i = 0; i < mid; i++) {
l[i] = data[i];
}
for (int i = mid; i < n; i++) {
r[i - mid] = data[i];
}
mergeSort(l, mid);
mergeSort(r, n - mid);

merge(data, l, r, mid, n - mid);
}

/**
* 合并结果
*
* @param a
* @param l
* @param r
* @param left
* @param right
*/
private static void merge(int[] a, int[] l, int[] r, int left, int right) {

int i = 0, j = 0, k = 0;
while (i < left && j < right) {
if (l[i] <= r[j]) {
a[k++] = l[i++];
} else {
a[k++] = r[j++];
}
}
while (i < left) {
a[k++] = l[i++];
}
while (j < right) {
a[k++] = r[j++];
}
}