排序算法总结.md

排序算法对大家来说肯定都不陌生吧，作为最基础且最重要的算法之一，在面试中经典排序算法也经常被要求手撕代码。可是排序算法实在是太多了(见下图)，有些名字听起来都莫名其妙的，比如鸡尾酒排序，侏儒排序，煎饼排序等。

当然，这篇文章会为大家讲解众多排序算法中最经典的部分，也是大家最熟悉的几种算法，包括冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、桶排序、希尔排序、堆排序。同时也会利用一些手绘图来帮助大家更好地理解，希望大家在阅读完本文章后都能够有所收获。

声明: 在下面讲解的所有算法中，我们默认需要对待处理的数组进行升序排序。即排序好的数组中，元素的大小从左到右递增排序。

预备知识

在正式开始讲解各种排序算法之前，我还希望大家思考一个问题。什么样的排序算法才是一个好的算法，各种各样的排序算法它们的应用场景又有什么不同？希望大家在读完这篇文章之后能够有一个答案。

其实，要想真正学好排序算法，我们要做的不仅仅是了解它的算法原理，然后背下代码就完事。更重要的是，我们要学会去分析和评价一个排序算法。那么对于这么多的排序算法，我们应该关注它们的哪些方面呢？

1.排序算法的时间复杂度

分析一个算法的好坏，第一个当然就是应该分析该算法的时间复杂度。排序算法需要对一组数据进行排序，在实际的工程中，数据的规模可能是10个、100个，也可能是成千上万个。同时，对于要进行排序处理的数据，可能是接近有序的，也可能是完全无序的。因此，在分析其时间复杂度时，我们不仅要考虑平均情况下的时间复杂度，还要分析它在最好情况以及最坏情况下代码的执行效率有何差异。

对于一个常见的排序算法来说，执行过程中往往会涉及两个操作步骤，一个是进行元素的比较，二是对元素进行交换或者移动。所以在分析排序算法的时间复杂度时，也要特别注意算法实现过程中不同的元素比较和交换(或移动)的次数。

2.排序算法的空间复杂度

这里需要引入一个新的概念，原地排序。原地排序就是指在排序过程中不必申请额外的存储空间，只利用原来存储待排数据的存储空间进行比较和排序的排序算法。换句话说，原地排序不会产生多余的内存消耗。

3.排序算法的稳定性

对于一般的算法，我们一般只需要分析它的时间复杂度和空间复杂度，但是对于排序算法来说，我们还有一个非常重要的分析指标，那就是排序算法的稳定性。

稳定性是指，在需要进行排序操作的数据中，如果存在值相等的元素，在排序前后，相等元素之间的排列顺序不发生改变。

大家可能会想，反正都是相等的元素，通过排序后谁在前谁在后有什么不一样呢？对排序算法进行稳定性分析又有什么实际意义呢？

其实，在学习数据结构与算法的过程中，我们解决的问题基本上都是对简单的数字进行排序。这时，我们考虑其是否稳定似乎并没有什么意义。

但是在实际应用中，我们面对的数据对象往往都是复杂的，每个对象可能具有多个数字属性且每个数字属性的排序都是有意义的。所以在排列时，我们需要关注每个数字属性的排序是否会对其他属性进行干扰。

举个例子，假如我们要给大学中的学生进行一个排序。每个学生都有两个数字属性，一个是学生所在年级，另一个是学生的年龄，最终我们希望按照学生年龄大小进行排序。而对于年龄相同的同学，我们希望按照年级从低到高的顺序排序。那么要满足这样的需求，我们应该怎么做呢？

第一个想到的，当然就是先对学生的年龄进行排序，然后再在相同年龄的区间里对年级进行排序。这种办法很直观且似乎没什么问题，但是仔细一想，会发现如果我们要进行一次完整的排序，我们需要采用5次排序算法(按年龄排序1次，四个年级分别排序4次)。那么我们有没有更好地解决办法呢？

如果我们利用具有稳定性的排序算法，这个问题就会更好地解决了。我们先按照年级对学生进行排序，然后利用稳定的排序算法，按年龄进行排序。这样，只需要运用两次排序，我们就完成了我们的目的。

这是因为，稳定的排序算法能够保证在排序过程中，相同年龄的同学，在排序之后，他们的顺序不发生改变。由于第一次我们已经将学生按年级排序好了，于是在第二次排序时，我们运用稳定的排序算法，相同年龄的学生依旧按年级保持顺序。

了解如何分析排序算法后，接下来就可以开始下面各种排序算法的学习了。

算法介绍

1.插入排序(Insertion Sort)

在讲解插入排序之前，我们先来回顾一下,在一个有序数组中，我们是如何插入一个新的元素并使数组保持有序的呢？

我们需要遍历整个数组，直到找到该元素应该插入的位置，然后将后面相应的元素往后移动，最后插入我们的目标元素。(插入过程如下图)

插入排序其实就是借助这样的思想，首先我们将数组中的数据分为两个区间，一个是已排序区间，另一个是未排序区间，同时这两个区间都是动态的。开始时，假设最左侧的元素已被排序，即为已排序区间，每一次将未排序区间的首个数据放入排序好的区间中，直达未排序空间为空。

• 插入排序算法图解如下：

• 插入排序代码实现：

#include<iostream>
#include<vector>

using namespace std;

void InsertionSort(vector<int>&, int);

int main() {
  vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
  InsertionSort(test, test.size());

  for (auto x : test)
    cout << x << " ";

  return 0;
}

void InsertionSort(vector<int>& arr, int len) {
  for (int i = 1; i < len; ++i) {   //注意i从1开始
    int key = arr[i];    //需要插入的元素  
    int j = i - 1;   //已排序区间 
    while ((j >= 0) && (arr[j] > key)) {
      arr[j + 1] = arr[j];    //元素向后移动
      j--;
    }
    arr[j + 1] = key;
  }
}

• 算法分析:

插入排序的时间复杂度？

最好情况: 即该数据已经有序，我们不需要移动任何元素。于是我们需要从头到尾遍历整个数组中的元素O(n).

最坏情况: 即数组中的元素刚好是倒序的，每次插入时都需要和已排序区间中所有元素进行比较，并移动元素。因此最坏情况下的时间复杂度是O(n^2).

平均时间复杂度:类似我们在一个数组中插入一个元素那样，该算法的平均时间复杂度为O(n^2).

插入排序是原地排序吗？

从插入排序的原理中可以看出，在排序过程中并不需要额外的内存消耗，也就是说，插入排序是一个原地排序算法。

插入排序是稳定的排序算法吗？

其实，我们在插入的过程中，如果遇到相同的元素，我们可以选择将其插入到之前元素的前面也可以选择插入到后面。所以，插入排序可以是稳定的也可能是不稳定的。

2.选择排序(Selection Sort)

选择排序和插入排序类似，也将数组分为已排序和未排序两个区间。但是在选择排序的实现过程中，不会发生元素的移动，而是直接进行元素的交换。

选择排序的实现过程: 在不断未排序的区间中找到最小的元素，将其放入已排序区间的尾部。

• 选择排序方法比较直观，图解如下：

• 选择排序代码实现

#include<iostream>
#include<vector>

using namespace std;

void SelectionSort(vector<int>&);

int main() {
  vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
  SelectionSort(test);

  for (auto x : test)
    cout << x << " ";

  return 0;
}

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

    swap(arr[i], arr[min]);
  }
}

• 算法分析:

选择排序的时间复杂度？

最好情况，最坏情况：都需要遍历未排序区间，找到最小元素。所以都为O(n^2).因此，平均复杂度也为O(n^2).

选择排序是原地排序吗？

与插入排序一样，选择排序没有额外的内存消耗，为原地排序算法。

插入排序是稳定的排序算法吗？

答案是否定的，因为每次都要在未排序区间找到最小的值和前面的元素进行交换，这样如果遇到相同的元素，会使他们的顺序发生交换。

比如下图的这组数据，使用选择排序算法来排序的话，第一次找到最小元素1，与第一个2交换位置，那前面的2和后面的2顺序就变了，所以就不稳定了。

3.冒泡排序(Bubble Sort)

冒泡排序和插入排序和选择排序不太一样。冒泡排序每次只对相邻两个元素进行操作。每次冒泡操作，都会比较相邻两个元素的大小，若不满足排序要求，就将它俩交换。每一次冒泡，会将一个元素移动到它相应的位置，该元素就是未排序元素中最大的元素。

• 将数组元素倒置，第一次冒泡图解如下：

• 冒泡排序整个过程图解如下：

• 冒泡排序代码实现:

#include<iostream>
#include<vector>

using namespace std;

void BubbleSort(vector<int>&);

int main() {
  vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
  BubbleSort(test);

  for (auto x : test)
    cout << x << " ";

  return 0;
}

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

• 冒泡排序的递归实现

如果我们仔细观察冒泡排序算法，我们会注意到在第一次冒泡中，我们已经将最大的元素移到末尾。在第二次冒泡中，我们将第二大元素移至倒数第二个位置，然后以此类推，所以很容易想到利用递归来实现冒泡排序。

递归思路:

1. 如果数组大小为1，则直接返回。

2. 每进行一次冒泡排序，可修复当前数组的最后一个元素。

3. 每完成一次冒泡操作，对剩下未排序所有元素进行递归冒泡。

• 冒泡排序递归代码实现：

#include<iostream>
#include<vector>

using namespace std;

void Recursive_BubbleSort(vector<int>&, int);

int main() {
  vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
  Recursive_BubbleSort(test,test.size());

  for (auto x : test)
    cout << x << " ";

  return 0;
}

void Recursive_BubbleSort(vector<int>& arr, int n) {
  if (n == 1) return;

  for (int i = 0; i < arr.size() - 1; i++) {
    if (arr[i] > arr[i + 1])
      swap(arr[i], arr[i + 1]);
  }

  Recursive_BubbleSort(arr, n - 1);
}

• 算法分析:

冒泡排序的时间复杂度？

最好情况:我们只需要进行一次冒泡操作，没有任何元素发生交换，此时就可以结束程序，所以最好情况时间复杂度是O(n).

最坏情况: 要排序的数据完全倒序排列的，我们需要进行n次冒泡操作，每次冒泡时间复杂度为O(n),所以最坏情况时间复杂度为O(n^2)。

平均复杂度：O(n^2)

冒泡排序是原地排序吗？

冒泡的过程只涉及相邻数据之间的交换操作而没有额外的内存消耗，故冒泡排序为原地排序算法。

冒泡排序是稳定的排序算法吗？

在冒泡排序的过程中，只有每一次冒泡操作才会交换两个元素的顺序。所以我们为了冒泡排序的稳定性，在元素相等的情况下，我们不予交换，此时冒泡排序即为稳定的排序算法。

---

接下来将为大家介绍两种最重要同时也最常用的排序算法，大家一定要提起精神认真看了，这可是10次面试9次都会问到的排序算法。但是在介绍这两种排序算法之前还需要给大家讲一讲什么是分治思想。

分治思想(Divide and Conquer)

在计算机科学中，分治法是基于多项分支递归的一种重要的算法思想。从名字可以看出，**“分治”也就是“分而治之”**的意思，就是把一个复杂的问题分成两个或多个相同或类似的子问题，直到子问题可以简单直接地解决，原问题的解即为子问题的合并。

分治算法一般都是用递归来实现的，具体的分治算法可以按照下面三个步骤来解决问题:

1. 分解: 将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2. 解决: 若子问题规模较小且易于解决时，就直接解决。否则，再递归地解决各子问题。
3. 合并: 将各子问题的解合并为原问题的解。

算法介绍

4.归并排序(Merge Sort)

该算法是利用分治思想解决问题的一个非常典型的应用，归并排序的基本思路就是先把数组一分为二，然后分别把左右数组排好序，再将排好序的左右两个数组合并成一个新的数组，最后整个数组就是有序的了。

运用递归法实现归并操作的主要步骤:

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置。
3. 比较两个指针所指向的元素，选择较小的元素放入到合并空间，并将指针移动到下一位置。
4. 重复步骤3直到某一指针到达序列尾，然后将另一序列剩下的所有元素直接复制到合并序列尾

• 归并算法图解如下：

• 归并排序算法实现代码：

#include<iostream>
#include<vector>

using namespace std;

void Merge(vector<int>& , int , int , int );
void MergeSort(vector<int>& , int , int );

int main() {
	vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
	MergeSort(test,0,test.size()-1);

	for (auto x : test)
		cout << x << " ";

	return 0;
}


void Merge(vector<int>& arr, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = 0;
	vector<int> temp(right - left + 1);
	while (i <= mid && j <= right)
		temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];

	while (i <= mid)
		temp[k++] = arr[i++];

	while (j <= right)
		temp[k++] = arr[j++];

	for (int m = 0; m < temp.size(); m++)
		arr[left + m] = temp[m];
}


void MergeSort(vector<int>& arr,int left, int right) {
	if (left >= right) return;

	int mid = left + (right - left) / 2;
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	Merge(arr, left, mid, right);
}

• 代码讲解:

归并排序中需要用到两个函数，一个是MergeSort函数，一个是Merge函数。MergeSort函数的作用是把数组中left至right的元素全部排列好。而Merge函数的作用是把左右两个已经排序好的数组合并成一个数组。

Merge函数的编写非常重要，首先我们需要创建一个新的数组temp，数组大小为right-left+1.然后定义两个下标i和j, 其中i=left, j=mid+1,i表示第一个数组的起始位置，j表示第二个数组的起始位置。同时还需要一个下标k来标记temp数组中填入元素的位置。

接下来开始遍历两个数组，比较i和j所指元素的大小，将较小者放入temp数组中，同时该较小者下标和k向后移动。当其中一个子数组循环完后，将剩下数组中的元素依次放入temp数组中。

最终，将temp中已排序好的数组拷贝回原数组array，再返回经过归并排序好的数组。

MeergeSort函数主要是用于递归调用。当right >= left时，就直接return。否则，找到数组的中间下标，将数组一分为二，分别两边两边数组进行归并排序，最后将两个数组用Merge函数合并起来。

• 算法分析:

归并排序的时间复杂度？

归并排序的递推公式为T(n)=2*T(n/2)+n

该递归式表明，对n个元素递归排序所需时间复杂度，等于左右子区间n/2个元素分别递归排序的时间，加上将两个已排好的子区间合并起来的时间O(n)

当递归循环至最后一层时，即n=1时,T(1)=1,于是可以推导出归并排序的时间复杂度为O(nlongn)

归并排序是原地排序吗？

从原理中可以看出，在归并排序过程中我们需要分配临时数组temp，所以不是原地排序算法，空间复杂度为O(n).

归并排序是稳定的排序算法吗？

当我们遇到左右数组中的元素相同时，我们可以先把左边的元素放入temp数组中，再放入右边数组的元素，这样就保证了相同元素的前后顺序不发生改变。所以，归并排序是一个稳定的排序算法。

5.快速排序(Quicksort)

快速排序，也就是我们常说的“快排”。其实，快排也是利用的分治思想。它具体的做法是在数组中取一个基准pivot，pivot位置可以随机选择(一般我们选择数组中的最后一个元素)。选择完pivot之后，将小于pivot的所有元素放在pivot左边，将大于pivot的所有元素放在右边。最终，pivot左侧元素都将小于右侧元素。接下来我们递归将左侧的子数组和右侧子数组进行快速排序。如果左右两侧的数组都是有序的话，那么我们的整个数组就处于有序的状态了。

快速排序的主要步骤为：

1. 挑选基准值：从数组中挑出一个元素，称为“基准”（pivot）
2. 分割：重新排序数组，所有比pivot小的元素摆放在pivot前面，所有比pivot值大的元素放在pivot后面(与pivot值相等的数可以到任何一边)。
3. 递归排序子数组：递归地将小于pivot元素的子序列和大于pivot元素的子序列进行快速排序。
4. 递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

• 快速排序图解如下：

• 快速排序实现代码

#include<iostream>
#include<vector>

using namespace std;

int partition(vector<int>& , int , int );
void QuickSort(vector<int>& , int , int );

int main() {
	vector<int> test = { 3, 7, 6, 4, 5, 1, 2, 8 };
	QuickSort(test,0,test.size()-1);

	for (auto x : test)
		cout << x << " ";

	return 0;
}


int partition(vector<int>& arr, int left, int right) {
	int pivot = right;
	int location = left;
	for (int i = left; i < right; i++) {
		if (arr[i] < arr[pivot]) {
			int temp = arr[i]; arr[i] = arr[location]; arr[location] = temp;
			location++;
		}
	}
	int temp = arr[pivot]; arr[pivot] = arr[location]; arr[location] = temp;
	return location;
}


void QuickSort(vector<int>& arr,int left, int right) {
	if (left >= right) return;

	int pivot = partition(arr, left, right);
	QuickSort(arr, left, pivot-1);
	QuickSort(arr, pivot + 1, right);
}

• 代码讲解

快速排序算法中有两个函数,QuickSort函数和partition函数。partition函数的作用返回pivot下标，意思是此时，所有在pivot左侧的元素都比pivot的值小，在右侧的值比pivot大。接下来对左右两侧的数组递归调用QuickSort函数进行快排。

我们每次指定pivot指向最后一个元素，同时定义一个变量location，用来标记pivot最后应该置于的位置。在location左侧的所有元素都是比pivot值小的，从location开始，右侧所有元素都比pivot大。

只要遍历到的元素比pivot的值小，就与location所指的元素进行交换，同时location++，更新pivot应该在的位置。

数组遍历结束，最后将元素pivot与location所指元素进行交换，这样，pivot左侧的元素就全部比pivot小，右侧元素全部比pivot大了。

• 算法分析:

快速排序的时间复杂度？

快排的时间复杂度也可以像归并排序那样用递推公式计算出来。如果每次分区都刚好把数组分成两个大小一样的区间，那么它的时间复杂度也为O(nlogn).但是如果遇到最坏情况下，该算法可能退化成O(n^2).

快速排序是原地排序吗？

根据上述原理可以知道，快速排序也没有额外的内存消耗，故也是一种原地排序算法。

快速排序是稳定的排序算法吗？

因为分区操作涉及元素之间的交换(如下图)，当遍历到第一个小于2的元素1时，会交换1与前面的3，因此两个相等3的顺序就发生了改变。所以快速排序不是一个稳定的排序算法。

---

上面讲的5种排序算法过程都是基于元素之间的比较和交换，所以我们常常把这种排序算法称为比较类排序。同时上面介绍的5种排序算法的时间复杂度最快也只能达到O(nlogn),所以我们也称这类排序算法称为非线性时间比较类排序。

接下将介绍另外几种线性时间非比较类排序，虽然这几种排序算法似乎效率更高，但是经过下面的介绍你就会发现，它们也并不是万能的。

6.计数排序(Counting Sort)

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。简单点说，就是用额外的数组记录输入数据中各数据出现的次数，然后将数据按出现频数取出。

• 计数排序算法图解

其中array为原数组，count数组用于计算每个元素出现次数。

计数排序实现步骤：

计数排序思路比较简单，先找到数组中元素最大值max,额外分配一个大小为max+1的数组用于计算元素出现次数。最后从小到大按元素个数更新原数组。

• 计数排序算法代码实现:

#include<iostream>
#include<vector>

using namespace std;

void CountSort(vector<int>&);

int main() {
  vector<int> test = { 3, 3, 6, 2, 5, 1, 2, 8 };
  CountSort(test);
  for (auto x : test)
    cout << x << " ";
  return 0;
}

int FindMax(vector<int> arr) {
  int max = 0;
  for (auto x : arr)
    if (x > max)
      max = x;
  return max;
}

void CountSort(vector<int>& arr) {
  int max = FindMax(arr);
  vector<int> count(max+1,0);   //需要分配数组大小,节省了数组空间

  for (int i = 0; i < arr.size(); i++) {  //开始计数
    count[arr[i]]++;   //
  }

  int index = 0;
  for (int k = 0; k <count.size(); k++) {
    for (int cnt = 0; cnt < count[k]; cnt++)
      arr[index++] = k;
  }
}

• 算法优化

大家从上面的图中可以看到，我们在计数时分配了计数数组count，但是count数组的两个位置根本没有计入任何数字。那是因为该数组中最小的元素为2，不可能存在0和1了。因此我们可以对我们之前的代码进行改进，找到数组中的最大元素和最小元素，然后分配max-min+1空间的数组即可。

• 改进后的算法如下：

#include<iostream>
#include<vector>
using namespace std;

void CountSort(vector<int>&);

int main() {
  vector<int> test = { 3, 3, 6, 2, 5, 1, 2, 8 };
  CountSort(test);
  for (auto x : test)
    cout << x << " ";
  return 0;
}

int FindMax(vector<int> arr) {
  int max = arr[0];
  for (auto x : arr)
    if (x > max)
      max = x;
  return max;
}

int FindMin(vector<int> arr) {
  int min = arr[0];
  for (auto x : arr)
    if (x < min)
      min = x;
  return min;
}

void CountSort(vector<int>& arr) {
  int max = FindMax(arr);
  int min = FindMin(arr);
  vector<int> count(max - min + 1,0);   //需要分配数组大小,节省了数组空间

  for (int i = 0; i < arr.size(); i++) {  //开始计数
    count[arr[i]-min]++;   //
  }

  int index = 0;
  for (int k = 0; k <count.size(); k++) {
    for (int cnt = 0; cnt < count[k]; cnt++)
      arr[index++] = k+min;
  }
}

注意count数组脚标与原数组脚标之间的转换

经过改进之后的算法节省了一定的空间，但是细心的朋友会发现，每次排序的结果是根据count数组中元素出现次数直接对原数组进行更新。这样的话，我们原数组中的元素被覆盖，算法的稳定性也就得不到保障。那么我们应该怎么保证计数排序前后数组数据的前后一致性和稳定性呢？

接下的讲解会有一些繁琐，希望大家结合文字和图片慢慢理解。

首先，我们需要对我们之前的count数组进行变形，我们将数组中的每一个元素进行累加。换句话说，就是从第二个元素开始，每一个元素都加上前面元素之和。

因此我们count数组进行如下变形：

那么这样累加的意义是什么呢？

其实，这时count数组中的元素值表示相应整数最终的排序位置。

例如我们的数组[5,2,3,6,2,5]，count数组中count[4]=6，(count数组中下标为4，但是表示存储元素的实际大小为6)，所以元素6最终会位于数组中第6的位置。的确，array一共有6个元素，最大值为6，故排序后6处于数组的最后位，即第6位。

由于我们要保证原数组数据的前后一致性，所以接下来我们需要分配一个新的数组，用于拷贝array中的元素，最终达到有序。

但是还有一个问题，我们要如何保证计数排序的稳定性呢？

这里很巧妙地用到了一个办法——反向填充数组

建立好count数组后，我们用k遍历原数组array.

例如当k=5时，我们在count数组中找到对应下标(5-2=3)的位置，count[3]=5.也就是说，我们的元素5最终会在有序数组中的第5位。由于数组下标从0开始，所以我们需要将5保存至Sorted_array下标为4的地方,即Sorted_array[4]=array[5]。同时存入一个数据后，我们需要将count数组中该元素对应值减1,表示下一个相等元素位置向前移动，直到我们遍历完整个数组array.

上面的文字描述可以简单表述为:

k=5 -> array[k]=5 -> array[k]-min=3

count[3]=5 -> sorted_array[4] = array[5]

由于最后我们将原数组反向填充到新数组中，同时指向位置的指针不断向前移动，这样，我们就保证了我们计数排序算法的稳定性。

• 改进后稳定的计数排序算法代码:

#include<iostream>
#include<vector>

using namespace std;

vector<int> CountSort(vector<int>&);

int main() {
  vector<int> test = { 3, 3, 6, 2, 5, 1, 2, 8 };
  vector<int> newarray = CountSort(test);
  for (auto x : newarray)
    cout << x << " ";
  return 0;
}

int FindMax(vector<int> arr) {
  int max = arr[0];
  for (auto x : arr)
    if (x > max)
      max = x;
  return max;
}

int FindMin(vector<int> arr) {
  int min = arr[0];
  for (auto x : arr)
    if (x < min)
      min = x;
  return min;
}

vector<int> CountSort(vector<int>& arr) {
  int max = FindMax(arr);
  int min = FindMin(arr);
  vector<int> count(max - min + 1,0);   //需要分配数组大小,节省了数组空间
  vector<int> sortedarray(arr.size(), 0);

  for (int i = 0; i < arr.size(); i++) {  //开始计数
    count[arr[i]-min]++;   //
  }

  for (int j = 1; j < count.size(); j++) {
    count[j] = count[j - 1] + count[j];
  }

  for (int k = arr.size()-1; k >=0; k--) {
    sortedarray[count[arr[k]-min]-1] = arr[k];
    count[arr[k] - min]--;
  }

  return sortedarray;
}

如果对整个过程还是不太明白，建议大家结合手绘图解，以及代码再仔细看一下。下面总结一下基数排序算法的整个过程。

计数排序算法的基本步骤：

1. 找出待排数组中最大和最小的元素(确定需要分配数组内存)

2. 统计数组中每个值为i的元素出现的次数，存入数组count(开始计数)

3. 对所有的计数进行累加(确定元素位置)

4. 反向填充数组，将每个元素i放在新数组的第count[i]项，每放一个元素，就将count[i]-1.

• 计数排序算法分析

计数算法的时间复杂度为O(n+k),由于我们需要分配额外的数组空间，空间复杂度也为O(n+k),即不是原地排序算法.同时我们通过反向填充数组的办法保证了计数排序算法的稳定性。

由于用来计数的数组count的长度取决于待排序数组中数据的范围，这使得对于数据范围很大的数组，计数排序需要消耗大量额外的内存。也就是说计数排序具有一定的局限性，虽然作为一种线性时间复杂度的排序，计数排序要求输入必须是确定范围的整数。如果数据范围太大，意味着我们需要额外消耗的内存也就更大，所以计数排序也不是那么万能的。

7.桶排序(Bucket Sort)

桶排序中的桶其实有点类似于计数排序中的“键”，不过这里的桶代表的是一个区间范围。桶排序算法的实现就是将数组分配到有限量的桶里，然后对每个桶分别进行排序(有可能用到其他排序算法)，排序完后再将桶里的数据依次拿出，即可得到排序后的数列。

桶排序的步骤：

1. 设定一定数量的空桶。

2. 遍历数组，将元素放入特定范围的桶中。

3. 对每个不为空的桶内数据进行排序。

4.从不为空的桶中按顺序拿出元素放入原本的数组中。

• 桶排序算法图解:

• 桶排序代码实现:

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

void bucketsort(vector<int>&);

int main() {
    vector<int> test = { 40, 8, 2, 15, 37, 42, 11, 29, 24, 7 };
    bucketsort(test);
    for (auto x : test)
        cout << x << " ";
    return 0;
}

void bucketsort(vector<int>& arr) {
    queue<int> buckets[10];
    for (int digit = 1; digit <= 1e9; digit *= 10) {
        for (int elem : arr) {
            buckets[(elem / digit) % 10].push(elem);
        }
        int idx = 0;
        for (queue<int>& bucket : buckets) {
            while (!bucket.empty()) {
                arr[idx++] = bucket.front();
                bucket.pop();
            }
        }
    }
}

• 代码分析

桶排序思路比较简单，如果桶的数量等于数组元素的数量，那么桶排序就变成了计数排序。所以在代码中可以看到与计数排序相似的地方。

假设我们需要排序的数组元素有n个，同时用m个桶来存储我们的数据。那么平均每个桶的元素个数为k = n/m个.如果在桶内我们使用快速排序，那么时间复杂度为klogk,总的时间复杂度即为nlog(n/m).如果桶的数量接近元素的数量，桶排序的时间复杂度就是O(n) 了。但是如果运气不好，所有的元素都到了一个桶了，那么它的时间复杂度就退化成 O(nlogn) 了。

8.基数排序（Radix sort）

基数排序其实也是一个非比较型的整数排序算法，其原理是将整数按位切割成不同的数字，然后按每个位数分别比较。但是在计算机中字符串和浮点数也可以用整数表示，所以也可以用基数排序。

由此可见，基数排序是基于位数的比较，所以再处理一些位数较多的数字时基数排序就有明显的优势了。例如在给手机号排序，或者给一些较长的英语专业名词排序等。

基数排序的主要步骤:

1. 找出数组中的最大值并求其位数bit

2. 初始化一个数组count[]，长度与当前数组所包含数字的进制相同。例如对于整数排序，数组长度应该是10。

3. 运用计数排序的思想对数组进行排序，循环bit次

• 基数排序算法图解如下：

• 基数排序算法实现代码：

#include<iostream>
#include<vector>

using namespace std;

void radixsort(vector<int>&);
int maxbit(vector<int>);

int main() {
    vector<int> test = { 77, 15, 31, 50, 8, 100, 24, 3, 43, 65 };
    radixsort(test);
    for (auto x : test)
        cout << x << " ";
    return 0;
}

int maxbit(vector<int> arr) //求数据的最大位数
{
    int max = arr[0];
    for (auto x : arr)
        if (x > max)
            max = x;
            
    int bit = 1;

    while (max >= 10)
    {
        max /= 10;
        ++bit;
    }
    return bit;
}

void radixsort(vector<int>& arr) //基数排序
{
    int bit = maxbit(arr);
    vector<int> tmp(arr.size());
    vector<int> count(10); //0-9计数器
    int i, j, k;
    int radix = 1;
    for (i = 1; i <= bit; i++) //进行bit次排序
    {
        for (j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for (j = 0; j < arr.size(); j++)
        {
            k = (arr[j] / radix) % 10; 
            count[k]++;
        }
        for (j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; 

        for (j = arr.size() - 1; j >= 0; j--) 
        {
            k = (arr[j] / radix) % 10;
            tmp[count[k] - 1] = arr[j];
            count[k]--;
        }

        for (j = 0; j < arr.size(); j++) 
            arr[j] = tmp[j];
        radix = radix * 10;
    }
}

• 基数排序代码分析:

基数排序算法中，基于位数0-9的排序有点类似计数排序，如果大家对代码有所疑惑，可以多看几次计数排序的思路和代码。

根据上面的讲解大家也可以很容易地看出，基数排序的时间复杂度是O(k*n),其中n是排序的元素个数，k是元素中最大元素的位数。因此，基数算法也是线性的时间复杂度，但是由于k取决于数字的位数，所以在某些情况下该算法不一定优于O(nlogn).

---

到目前为止，我们已经介绍了8种排序算法，其实这8种排序算法已经包括了所有的基本实现思想。但是“革命尚未成功，同志仍需努力”。接下来还会继续为大家介绍另外两种比较特殊的排序算法——希尔排序和堆排序。

9.希尔排序(Shellsort)

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

所以在具体讲解希尔排序之前，我们还是先来回顾一下插入排序的整个实现过程:

首先我们将数组中的数据分为两个区间，一个是已排序区间，另一个是未排序区间，同时这两个区间都是动态的，需要添加和移动元素。开始时，假设最左侧的一个元素已被排序，即为已排序区间，每一次将未排序区间的首个数据插入排序好的区间中，直达未排序空间为空。

• 插入排序算法图解如下:

那么插入排序有哪些不足的地方呢？

在插入排序中，我们每次只交换两个相邻元素，当一个元素需要向前移动至它的正确位置时，只能一步一步地移动。因此插入排序的平均时间复杂度为O(n^2).

而希尔排序的想法是实现具有一定间隔元素之间的交换，即首先排序有一定间隔的元素，同时按顺序依次减小间隔，这样就可以让一个元素一次性地朝最终位置前进一大步，当间隔为1时就是插入排序了。

希尔排序算法步骤：

1. 计算步长间隔值gap

2. 将数组划分为这些子数组

3. 按照插入排序思想进行排序

4. 重复此过程，直到间隔为1,进行普通的插入排序。

• 希尔算法图解如下:

• 希尔排序代码实现:

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

void shell_sort(vector<int>&);

int main() {
    vector<int> test = { 40, 8, 2, 15, 37, 42, 11, 29, 24, 7 };
    shell_sort(test);
    for (auto x : test)
        cout << x << " ";
    return 0;
}

void shell_sort(vector<int>& arr) {

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

            arr[j] = temp;
        }
    }
}

• 代码分析

在希尔算法中，步长的选择尤其重要。在上面的代码中，最初的步长选择为n/2,并且不断对步长取半，直到最后为1.虽然这样可以比普通的插入排序O(n^2)更好，但是根据步长的选择不同，希尔排序的平均时间复杂度还可以更优。下图为不同步长序列选择下的最坏时间复杂度。

下面是几种优秀的步长序列:

1. `Shell’s original sequence: N/2 , N/4 , …, 1
2. Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
3. Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577…4j+1+ 3·2j+ 1.
4. Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
5. Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,…
6. Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81….

• 代码分析

因为希尔排序在实现过程中没有分配额外的内存空间，所以是一种原地排序算法。但是由于希尔排序将数组分组并存在元素的交换，所以并不是一个稳定的排序算法。

10.堆排序（Heap sort）

堆排序是利用**“堆”**这种数据结构实现的一种排序算法。那么什么是堆呢？

先给大家简单介绍一下堆，堆一般具有下面两个性质：

堆总是一棵完全二叉树。(完全二叉树是指即除了最底层，其他层的节点都必须被元素填满，同时最底层的叶子节点必须全部。)

堆中的任意节点的值都必须大于等于或小于等于它的子节点

其中，将每个节点的值都大于等于其子节点值的堆称为**“大顶堆”(max heap)，将每个节点的值小于等于子节点值的堆称为“小顶堆”(min heap)**.

如下图：

因为我们常用数组来存储完全二叉树，所以我们也可以用数组来存储堆。

堆在数组中的存储图如下：

由上图我们可以看出对于堆中元素下标为i的点:

• 2*i+1为它的左子节点

• 2*i+2为它的右子节点

• i/2是它的前继节点

简单介绍完了堆，接下来就让我们看看这些对于堆有哪些具体的操作吧:

(我们常常用“大顶堆”用于堆排序，所以下面将要实现的堆都默认为“大顶堆”。)

• 维护堆(heapify)

对于“大顶堆”，它的每个节点的值都必须大于等于它的子节点的值。所以说为了维护一个“大顶堆”，我们需要设计一个算法将不满足“大顶堆”性质的节点进行修改。修改思路是将其与子节点相比较，如果它的值小于它的子节点，就将其与子节点中最大值发生交换，然后继续对该点进行判断，直到到达合适的地方。

• 建堆(build heap)

我们已经知道怎么维护一个堆了，那么我们怎么将用数组建一个“大顶堆”呢？

当我们需要维护一个大小为n的堆时，一般从下标n/2的位置不断向前移动。如下图，我们首先判断下标为4的元素，其满足堆的定义。然后我们判断下标为3的元素，使其与值为29的子节点发生交换。依次循环，当下标为1时，值为2的节点需要不断与子节点发生交换，直到叶子节点的位置。具体实现如下图：

• 用“大顶堆”实现堆排序(heap sort)

根据“大顶堆”的定义，堆顶元素即为整个数据中的最大值。于是当我们建好堆后，我们将堆顶元素与堆中最后一个元素交换，即将堆中最大元素放在了数组中的最后一个位置。此时，因为我们将较小的元素放在了堆顶，所以我们需要对其进行堆维护(heapify).维护完成后，堆顶元素为此时堆中的最大元素，然后继续重复上面的操作，反向填充数组，直到最后堆中剩下一个元素，即在数组的首位置。

• 堆排序算法图解:

• 堆排序算法实现代码：

#include <iostream>
#include<vector>
using namespace std;

void heapSort(vector<int>&, int);
int main()
{
    vector<int> arr = { 40, 2, 8, 29, 37, 24, 11, 15, 7, 36 };
    heapSort(arr, arr.size());
    for (auto x : arr) 
        cout << x << " ";
}


void heapify(vector<int>& arr, int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    
    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr, int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--)
    {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);   //堆的数量减一
    }
}

• 堆排序代码分析

上面堆排序算法代码中用到了两个函数，heapify和 heapSort.其中heapify函数的作用是对堆中下标为i的点进行堆维护，使其满足堆的性质。在heapSort函数中我们先将堆从下标n/2-1的位置进行维护，直到成为“大顶堆”，然后对堆顶元素进行交换和维护循环。最后，数组中的元素即为有序保存的了。

需要注意的是算法中的heapify函数需要传入除数组外的两个整数，第一个整数是指需要维护堆的大小。在最开始进行堆维护时，我们需要对整个数组进行维护，n即为数组的大小。但是在对堆顶元素和最后位置的元素进行交换后，此时最后一个元素已经在它正确的位置，所以我们需要维护堆的大小将逐渐减小，即传入代码中的i.

我们已经知道，包含n个元素的完整二叉树的高度为logn.

而当我们使用heapify函数，对某个元素进行维护时，我们需要继续将元素与其左，右子元素进行比较，并将其向下推移，直到其两个子元素均小于其大小。在最坏的情况下，我们需要将元素从根移动到叶子节点，进行多次logn的比较和交换。在build_max_heap阶段，我们对n/2元素执行此操作，因此build_heap步骤的最坏情况复杂度为n/2*log(n) ~ nlogn。

在排序步骤中，我们将根元素与最后一个元素交换，并堆放根元素。对于每个元素，这又需要花费logn最长时间，因为我们可能需要将元素从根一直带到最远的叶子上。由于我们重复了n次，因此heap_sort步骤也是nlogn。

由于build_max_heap和heap_sort步骤是一个接一个地执行的，因此算法复杂度不会增加，并且保持为nlogn。

因此，堆排序在所有情况下，即最好最坏以及平均情况下的时间复杂度均为O(nlogn).

总结回顾

到目前为止，已经为大家介绍完了十种基本算法。感谢大家的认真阅读，最后对十种算法的总结如下，希望大家有所收获！