程序猿养成之路：十大排序算法

2021-03-02

前言

文章主体部分转载自“一像素”的博客十大经典排序算法（动图演示），加上了自己的理解以及C++代码实现

一、算法概述

1. 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

2. 算法复杂度

3. 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、十大排序算法详解

1. 冒泡排序(bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的元素，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述

比较相邻的元素，如果第二个比第一个大，则交换两者位置；
对每一对相邻元素都进行上述工作，从开始第一对到最后一对，第一遍遍历之后最后的元素应该是最大的树；
针对所有元素重复以上步骤，除了最后一个；
重复步骤1~3，直到排序完成。

1.2 算法实现

void BubbleSort(vector<int>& arr){
    int size = arr.size();
    for(int i=0;i<size-1;i++){
        for(int j=0;i<size-1-i;j++){
            if(arr[j]>arr[j+1]){
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return;
}

1.3 算法分析

时间复杂度：对于n个元素的数组来说，第一趟需要比较n-1次，第二趟需要比较n-2次，第3趟需要比较n-3次…那么总的比较次数就为： $(n-1)+(n-2)+(n-3)+...+2+1 = \frac{n(n-1)}{2}$ 所以冒泡排序的时间复杂度为$O(n^2)$
稳定性：比较的时候，如果arr[i]==arr[j]，那么不交换两者，因此算法是稳定的。

2. 选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

2.2 算法实现

void SelectSort(vector<int>& arr){
    int size = arr.size();
     for(int i=0;i<size;i++){
        int min = i;
        for(int j=i+1;j<size;j++){
            if(arr[min]>arr[j]) min = j;
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
     }
     return;
}

2.3 算法分析

时间复杂度：第一趟需要n-1次比较，第二趟需要n-2次比较…总的比较次数为 $(n-1)+(n-2)+...+2+1 = \frac{n(n-1)}{2}$ 所以时间复杂度为$O(n^2)$
算法稳定性：选择排序的交换会破坏算法稳定性。Eg.[5,8,5,2,9]第一次遍历时，第一个5会和2交换位置，从而到第二个5的后面去，从而破坏稳定性。

3. 插入排序(Insertion Sort)

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

3.2 算法实现

void InsertSort(vector<int>& arr){
    int size = arr.size();
    for(int i=0;i<size;i++){
        preIndex = i-1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current){
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return;
}

3.3 算法分析

时间复杂度：元素比较次数为$\frac{n(n-1)}{2}$，元素交换次数为比较次数的三倍$\frac{3n(n-1)}{2}$，时间复杂度为两者相加$O(n^2)$。
稳定性：比较的时候，如果两个数相等则不移动，因此算法稳定。

4. 希尔排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 算法实现

void ShellSort(vector<int>& arr){
    int size = arr.size();
    for(int gap = size/2;gap>0;gap/=2){
        for(int i=gap;i<size();i++){
            int j = i;
            while(j - gap >= 0 && arr[i] <arr[j-gap]){
                int temp = arr[j];
                arr[j] = arr[j-gap];
                arr[j-gap] = temp;
            }
        }
    }
    return;
}

4.3 算法分析
希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量)，其最坏时间复杂度依然为O(n2)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

5. 归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

5.2 算法实现

//递归版本
void mergeSort(vector<int>& arr,int low , int high) {
    //split
    if (low >= high) return;
    int mid = (low + high) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    //merge
    merge(arr, low, mid, high);
}

void merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp(high - low + 1);
    int i = low, j = mid + 1, t = 0;
    while (i <= mid && j <= high) {
    	temp[t++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) {
    	temp[t++] = arr[i++];
    }
    while (j <= high) {
    	temp[t++] = arr[j++];
    }
    t = 0;
    while (low <= high) {
    	arr[low++] = temp[t++];
    }
}

//迭代版本

5.3 算法分析
时间复杂度为$O(nlogn)$，空间复杂度为$O(n)$。
归并排序是一种稳定的排序算法。

6. 快速排序(Quick Sort)

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

6.2 算法实现

void quickSort(vector<int>& arr,int low ,int high) {
	//递归出口
	if (low >= high) return;
	//找基数， 这里以最左边的数为基数
	int temp = arr[low];
	int i = low, j = high;
	//将小于基数的放前面，大于基数的放右面，用“挖坑填数”的方式
	while (i < j) {
		while (i < j && arr[j] >= temp) {
			j--;
		}
		arr[i] = arr[j];
		while (i < j && arr[i] <= temp) {
			i++;
		}
		arr[j] = arr[i];
	}
	arr[i] = temp;
	quickSort(arr, low, i-1);
	quickSort(arr, i + 1, high);
}

快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用别的方法排序以减小递归深度。

PS：如果以中间的数作为基准数，直接将中间的数和第一个数进行交换就可以了

6.3 算法分析

时间复杂度：
最优情况: 每一次的基准数刚好都可以平分整个数组，此时的时间复杂度为$O(nlogn)$
最坏情况: 每一次的基准数刚好都是最大或者最小的数，此时的时间复杂度为$O(n^2)$
平均情况: $O(nlogn)$
稳定性：不稳定。Eg.[8,3,6,3]选取6为基准，第二个3会被放到5的位置。

7. 堆排序(Heap Sort)

算法描述
算法实现
算法分析

8. 计数排序(Counting Sort)

8.1 算法描述
8.2 算法实现
8.3 算法分析

9. 桶排序(Bucket Sort)

9.1 算法描述
9.2 算法实现
9.3 算法分析

10. 基数排序(Radix Sort)

10.1 算法描述
10.2 算法实现
10.3 算法分析

Joe Chen