下面选取在实际项目中应用较多的排序方式作一个性能比较,并会对各个方式作一个分析总结。
排序性能比较 测试方案
随机生成10万个整型数字,作为待排序数据。
逐个应用各个排序算法,通过计算开始至结束时间来获得算法执行时间,然后对其进行排序。
测试结果
排序算法
耗时(ms)
直接插入排序
769
希尔排序
10
冒泡排序
18,557
*快速排序
9
直接选择排序
3,811
*堆排序
10
归并排序
20
分析 稳定性
直接插入、冒泡和归并排序算法是稳定的。
直接选择、希尔、快速和堆排序算法是不稳定的。
排序方法的选取
若待排序的一组记录数目n较小(如n<=50)时可采用插入排序或选择排序。
若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++) { 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[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 ; } for (; increment > 0 ; increment = (increment - 1 ) / 3 ) { shellInsert(data, increment); } } private static void shellInsert (int [] data, int increment) { int j, tmp; 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[j + increment] = tmp; } } }
冒泡排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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 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); } } private static int partition (int [] data, int i, int j) { int tmp = data[i]; while (i < j) { while (i < j && data[j] >= tmp) { j--; } if (i < j) { data[i] = data[j]; i++; } while (i < j && data[i] <= tmp) { i++; } if (i < j) { data[j] = data[i]; j--; } } 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 public static void straightSelectSort (int [] data) { int k, tmp; for (int i = 0 ; i < data.length - 1 ; i++) { k = i; for (int j = i + 1 ; j < data.length; j++) { if (data[j] < data[k]) { k = j; } } if (k != 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 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 ); } } 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 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); } 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++]; } }