排序算法分析

排序是非常基本的并且是非常重要的算法知识,是每个程序员都应该掌握的内容。

概述

排序算法的分类

一般来说,常见的排序算法分成两大类,一是内部排序,一个是外部排序。内部排序是最为常用的,今天且来讨论内部排序。

内部排序分成4类 :

1
2
A(插入排序) --> B(直接插入排序)
A --> C(希尔排序)

1
2
A(选择排序) --> B(直接选择排序)
A --> C(堆排序)
1
2
A(交换排序) --> B(冒泡排序)
A --> C(快速排序)
1
A(归并排序) --> B(二路归并排序)

排序算法的实现

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class InsertSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
for (int i = 1; i < A.length; i++) {
int tmp = A[i];
int j = i - 1;
for (; j >= 0 && A[j] > tmp; j--) {
A[j + 1] = A[j];
}
A[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
public class ShellSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
int len = A.length;
int gap = 1;
while (gap * 3 < len) {
gap *= 3;
}
for (; gap >= 1; gap /= 3) {
for (int i = gap; i < len; i++) {
int tmp = A[i];
int j = i - gap;
for (; j >= 0 && A[j] > tmp; j -= gap) {
A[j + gap] = A[j];
}
A[j + gap] = tmp;
}
}
}
}

直接选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class SelectSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
for (int i = 0; i < A.length; i++) {
int index = i;
for (int j = i + 1; j < A.length; j++) {
if (A[j] < A[index]) {
index = j;
}
}
int tmp = A[i];
A[i] = A[index];
A[index] = 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
public class HeapSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
for (int i = (A.length - 1 - 1) / 2; i >= 0; i--) {
shiftDown(A, i, A.length - 1);
}
for (int i = A.length - 1; i >= 1; i--) {
int tmp = A[i];
A[i] = A[0];
A[0] = tmp;
shiftDown(A, 0, i - 1);
}
}
public void shiftDown(int[] A, int i, int len) {
while (i * 2 + 1 <= len) {
son = i * 2 + 1;
if (i * 2 + 2 <= len && A[i * 2 + 2] > A[i * 2 + 1]) {
son = i * 2 + 2;
}
if (A[i] >= A[son]) {
return;
}
int tmp = A[i];
A[i] = A[son];
A[son] = tmp;
i = son;
}
}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class BubbleSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
if (A[j - 1] > A[j]) {
int tmp = A[j];
A[j] = A[j - 1];
A[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
class QuickSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
helper(A, 0, A.length - 1);
}
private void helper(int[] A, int start, int end) {
if (start >= end) {
return;
}
int pivot = A[start];
int left = start;
int right = end;
while (left < right) {
while (left < right && A[right] >= pivot) {
right--;
}
A[left] = A[right];
while (left < right && A[left] <= pivot) {
left++;
}
A[right] = A[left];
}
A[left] = pivot;
helper(A, start, left - 1);
helper(A, left + 1, end);
}
}

二路归并排序

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
public class MergeSort {
public void sort(int[] A) {
if (A == null || A.length < 2) {
return;
}
int[] save = new int[A.length];
merge(A, save, 0, A.length - 1);
}
private void merge(int[] A, int[] save, int start, int end) {
if (end <= start) {
return;
}
int start1 = start;
int end1 = start + (end - start) / 2;
int start2 = end1 + 1;
int end2 = end;
merge(A, save, start1, end1);
merge(A, save, start2, end2);
int left = start1;
int right = start2;
int index = left;
while (left <= end1 && right <= end2) {
save[index++] = A[left] < A[right] ? A[left++] : A[right++];
}
while (left <= end1) {
save[index++] = A[left++];
}
while (right <= end2) {
save[index++] = A[right++];
}
for (int i = start1; i <= end2; i++) {
A[i] = save[i];
}
}
}

排序算法的性能比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
直接插入排序 O(n^2) O(n) O(n^2) O(1)
希尔排序 o(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1)
冒泡排序 O(n^2) O(n) O(n^2) O(1)
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n)
简单选择排序 O(n^2) O(n^2) O(n^2) O(1)
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(nlogn) O(1)

就时间性能而言,在希尔排序、堆排序、快速排序和归并排序等改迸算法当中.快速排
序目前被认为是最快的一种方法,而在待排序元素个数比较多的情况下,归并排序较堆排
需更快。

就稳定性而言,直接插入排序、起泡排序和归并排序是稳定的排序方法,而简单选择
排序,希尔排序、快速排序和堆排序是不稳定的排序方法。

因此考虑到以上各种因素,在选取排序方法的时候可以采用如下原则。

① 若排序元素的数目n较小(如n<=50时,可采用直接插人排序或简单选择排序。
由于直接插人排序所需的移动操作较简单选择排序多,因而当元素本身信息量较大
时,用简单选择排序比较好。

② 若元素的初始状态已经按关键码基本有序,可采用直接插入排序或冒泡排序。

③ 若排序元索的数目n较大.则可采用时间复杂度为o(nlogn)的排序方法如快速
排序,堆排序或归并排序等。快速排序的平均性能最好,在待排序序列按关键码随机分
布吋.快速排序最适合。快速排序在最坏情况下的时间复杂度是o(n^2),而堆排序在最坏
情况下的时间复杂度不会发生变化,并且所需的辅助空间少于快速排序。但这两种排序
方法都是不稳定的排序.若需要稳定的排序方法,则可采用归并排序。

(注:本文参考了 北京邮电大学出版社《数据结构与STL》,侵删)