7种经典排序算法总结和实现

发表于

基于比较的7种排序算法

冒泡排序BubbleSort

介绍

冒泡排序的原理比较简单，主要是两两比较，每次把比较大的数据放在后面，这样一次下来，最大的数就放在数组最后了。然后依次类推。

主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

步骤

  • 从索引为0的位置开始，往后依次两两比较，把大的数放在后面，小的数放在前面，这样一次下来最大的数就在数组末尾了(n)；
  • 最后一个数完成排序，退出排序工作，也就是令n–；
  • 重复第一步，直到n=0；

源码

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] a){
        int temp = 0;
        for(int i = 0; i < a.length - 1; i++){// 遍历第i次，每一次排好后面的1个
            for(int j = 0; j < a.length - i - 1; j++){// 从a[0]开始，依次去后面尚未排序的元素两两比较，大的置后
                if(a[j] > a[j + 1]){
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

优化方案

  • 每次排序，如果没有发生任何一次交换位置，说明已经是有序的了。因此可以用一个标识位记录是否交换了位置，如果没有则直接结束排序工作。

选择排序SelectionSort

介绍

选择排序每次用一个记录最小值的下标，然后把下标和前面未排序的序列中的第一个数据交换位置。依次类推。

主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定

步骤

  • 在未排序序列中找到最小元素，存放到排序序列的起始位置。
  • 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
  • 重复上面2个步骤，直到所有元素均排序完毕。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] a){
		int temp = 0;
		int min = 0;
		for(int i = 0; i < a.length - 1; i++){// 最后2个一比较就出结果了，所以最后一个不用比较了。i个元素排好序。
			min = i;
			for(int j = i + 1; j < a.length; j++){// 需要和全部未排序序列比较
				if(a[min] > a[j]){
					min = j;
				}
			}
			temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}

插入排序InsertionSort

介绍

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
—摘自维基百科

主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

步骤

  • 从第一个元素开始，认为是有序的；
  • 取出下一个元素继续，往前面比较，如果遇到比新元素小的，则把该元素往后移动一位；
  • 重复步骤2，直到找到已排序中小于或等于新元素的位置；
  • 把新元素插入到该位置中；
  • 重复步骤2-5；

源码

1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort(int[] a){
		for(int i = 1; i < a.length; i++){ // 因为第一个元素可以认为是有序的，所有从索引为1开始
			int key = a[i];
			int j = i;
			while(j > 0 && a[j - 1] > key){ // 如果前面元素大于新元素
				a[j] = a[j - 1]; // 该大元素往后移动1位
				j--;
			}
			a[j] = key; // 把新元素插入到找到的位置当中
		}
	}

希尔排序ShellSort

介绍

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

—摘自维基百科

主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
希尔排序 O(nlogn)~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

步骤

  • 假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
    13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10
  • 然后我们对每列进行排序：
    10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45
  • 将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
    10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45
  • 排序之后变为：
    10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94
  • 最后以1步长进行排序（此时就是简单的插入排序了）。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void shellSort(int[] a) {
        int size = a.length;
        // 初始步长为数组长度1/2，每次减半
        for(int gap = size / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) { // 分别处理每个步长分组
                for (int j = i + gap; j < size; j += gap) { // 插入排序
                    if (a[j] < a[j - gap]) {
                        int temp = a[j];
                        int k = j - gap;
                        while (k >= 0 && a[k] > temp) {
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        a[k + gap] = temp;
                    }
                }
            }
        }
    }

归并排序MergeSort

介绍

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
— 摘自维基百科

主要特性如下：

归并算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

步骤

  • 先考虑合并2个有序数组：基本思路是比较2个数组中最前面的数，谁小就取谁并填到合并数组中，取后其数组索引往后移动一位。然后再重新比较，直到其中的一个数组为空，最后把另一个数组的多出来的元素直接复制到合并数组中。
  • 再考虑递归分解：基本思路是把数组分解为左右2个数组，然后再对这2个数组递归分解，直到分解出来的数组只有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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static int[] mergeSort(int[] a) {
    if(a.length == 1) { // 先分解到最小数组，然后一层层合并
        return a;
    }
    int half = a.length / 2;
    int[] a1 = new int[half];
    int[] a2 = new int[a.length - half];
    System.arraycopy(a, 0, a1, 0, a1.length); // 新建左边数组
    System.arraycopy(a, half, a2, 0, a2.length); // 新建右边数组
    a1 = mergeSort(a1);
    a2 = mergeSort(a2);
    return mergeSortSub(a1, a2);
}
public static int[] mergeSortSub(int[] a1, int[] a2){
    int[] result = new int[a1.length + a2.length];
    int i = 0; // 记录左数组下标
    int j = 0; // 记录右数组下标
    int k = 0; // 记录合并数组下标
    while(true) {
        if(a1[i] < a2[j]) { // 左边数组元素小于右边，左边元素放到合并数组中
            result[k] = a1[i];
            i++;
            if(i > a1.length - 1) { // 左数组已全部遍历
                break;
            }
        }else { // 左边数组元素大于等于右边，右边元素放到合并数组中
            result[k] = a2[j];
            j++;
            if(j > a2.length - 1) { // 右数组已全部遍历
                break;
            }
        }
        k++; // 移动合并数组下标
    }
    // 把左右数组中元素比较多的那个数组多余的元素填到合并数组中
    for(; i < a1.length; i++) {
        result[++k] = a1[i]; // 因为上面赋值完后没执行k++，所以k指向的是最后赋值的下标，所以这里需要先++k
    }
    for(; j < a2.length; j++) {
        result[++k] = a2[j];
    }
    return result;
}

堆排序HeapSort

介绍

堆排序在top问题中使用比较频繁。堆排序是使用二叉树来实现的，不过实质上还是二维数组。二叉树是一个近似完全二叉树。

堆中二叉树特性(序号从0开始)：

  • 父节点的键值总是>=(<=)任何一个子节点的键值；
  • 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)；
  • 树里面每个节点的子女和双亲节点都可以根据当前节点的序号求出：
    • parent(i) = (i-1)/2;
    • left(i) = 2*i + 1;
    • right = 2*i + 2;
  • 非叶子节点 = n / 2 -1;

堆排序主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

步骤

  • 构造最大堆：若数组长度为size，因为单个元素(也就是叶子节点)可以看成是最大堆，则从size/2开始的元素是最大堆。于是从size/2-1开始，向前依次构造最大堆，这样就能保证，构造到某一个点，它的左右子树都是最大堆。
  • 堆中排序：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
  • 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。

源码

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
/*
     * 堆排序(从小到大)
     *
     * 说明：2个for循环，第一个用于初始化最大堆，第二个用于交换root数据和调整堆；
     */
    public static void heapSortAsc(int[] a) {
        int tmp;
        int arraySize = a.length;
        // 初步全局调整：从第一个非叶子节点开始，调整size/2-1次，也就是对所有非叶子节点进行调整
        for (int i = arraySize / 2 - 1; i >= 0; i--) {
            maxHeapDown(a, i, arraySize - 1);
        }
        // 把a[0]依次与最后一个节点调换，然后调整最最大堆，然后需要调换的节点数量-1
        for (int i = arraySize - 1; i >= 0; i--) {
            // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            // 局部调整：从root开始，只需要调整一次，调整的是尚未交换数据的节点
            maxHeapDown(a, 0, i - 1);
        }
    }
    /*
     * (最大)堆的向下调整算法
	 *
	 * 注：数组实现的堆中，第n个节点的左孩子的索引值是(2n+1)，右孩子的索引是(2n+2)。
	 *     其中，n为数组下标索引值。
	 *
	 * 参数说明：
	 *     a -- 待排序的数组
	 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
	 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
	 */
    public static void maxHeapDown(int[] a, int start, int end) {
        int current = start;            // 当前(current)节点的位置
        int left = 2 * current + 1;        // 左(left)孩子的位置
        int tmp = a[current];            // 当前(current)节点的大小
        // 依次遍历其子树
        for (; left <= end; current = left, left = 2 * left + 1) {
            // "left"是左孩子，"left+1"是右孩子
            if (left < end && a[left] < a[left + 1]) {
                left++;        // 左右两孩子中选择较大者
            }
            if (tmp >= a[left]) // 调整结束
                break;
            else {            // 交换值
                a[current] = a[left];
                a[left] = tmp;
            }
        }
    }

快速排序QuickSort

介绍

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
—摘自维基百科

快排通常明显比其他nlog(n)的算法更快，所以被广泛引用。在笔试的过程中更是可以说是必考。可见掌握快排的重要性。快排主要特性如下：

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

步骤

  • 选定基准数：从数组中选出一个元素作为基准数；
  • 分区过程：将比基准数大的放在右边，小于或等于基准数的放在左边；
  • 再对左右区间递归执行第二步，直至各个区间都只有一个元素；

源码(Java)

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
public static void quickSort(int[] a, int begin, int end){
        if(begin < end){ // 如果区间不是只有一个元素，则继续分区
            int i = begin;
            int j = end;
            int pivot = a[begin]; // 保存基准数，并在此处挖坑
            while(i < j){
                while(i < j && a[j] >= pivot){ // 在右边寻找比基准数小的元素
                    j--;
                }
                if(i < j){
                    a[i] = a[j]; // 找到一个比基准数小的元素，扔到左边，在j处挖坑
                    i++; // i开始移动
                }
                while(i < j && a[i] < pivot){ // 在左边寻找比基准数大的元素
                    i++;
                }
                if(i < j){
                    a[j] = a[i]; // 找到一个比基准数大的元素，扔到左边，在i处挖坑
                    j--;
                }
            }
            a[i] = pivot;// 此时i == j，存在一个坑，把基准数填下
            quickSort(a, begin, i - 1); // 对左区间递归
            quickSort(a, i + 1, end); // 对右区间递归
        }
    }

总结

排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
插入排序 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(nlogn) O(nlogn) O(nlogn) O(n) 稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~log(n) 不稳定

附录

参考文档