排序算法分析

发表于 | 分类于 ， |

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

概述

排序算法的分类

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

内部排序分成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》，侵删)