一文带你彻底掌握八大排序算法——插入、希尔、选择、堆排、冒泡、快速、归并、计数_快速、堆、计数、冒泡、选择,希尔、直接插入,桶排序

前言

  所谓排序，就是将一堆数据按照某个或者某些关键字的大小，进行降序或升序排列起来的操作。注意这里说的是关键字，也就是说排序的对象不一定是数字，例如我要将班上的学生按照数学成绩来排序，这里的排序的对象就是学生，而关键字就是每个学生的成绩。

常见的排序可分为四种

1.插入排序(直接插入排序、希尔排序)

2.选择排序(直接选择排序、堆排序)

3.交换排序(冒泡排序、快速排序)

4.归并排序

以上几种排序方法都要通过不断地比较数据大小来调整位置，从而达到有序，都属于比较排序。但是还有一些非比较排序，例如桶排序，基数排序和计数排序，其中计数排序在很多算法题中都会用到，所以简单介绍它，其它的排序有兴趣可以了解了解。

不管是比较排序还是非比较排序，他们都属与内排序，也就是说要先将所有数据放入内存才对他们进行操作排序。然而有的数据量非常大，不能一次性全部存下，这时候的排序就是外排序。外排序用到归并排序的思想，在介绍归并排序时会简单提一下。

一.八种排序算法介绍

（注意：下列所有的算法介绍都以升序为例）

1.插入排序

想一下你平时是怎样摸扑克牌的？

+ 

如上图，假如手里的牌是2，4，5，10，已经升序排列，这时候你摸到了一张7，于是你先和10比较，比10小，继续和左边的5比较比较；比5大，于是放到5的后面。上述就是插入排序的一趟过程。

一趟插入排序：

在一串有序数字中插入数字tmp，先将tmp和最后一个数字比较，如果比它大，就将tmp放在它的后面；如果比它小，就将它往后挪动一位，将tmp和前一个数字继续比较。重复上述过程，直到tmp比某个数字大就放到该数字的后面，如果没有比tmp大的数字，就将tmp放在最前面。

一趟插入排序的前提是数组已经有序，但我们最开始得到的是一个无序的数组，应该如何操作呢？

其实我们可以认为数组一开始只有第一个数字，那么它自然就是有序的，所以将第二个数字插入，这样前两个数字就有序了，接下来再插入第三个数，插入第四个数……有序序列不断扩大，最终将最后一个数字插入则排序完成。

动图

void InsertSort(int a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		//假设[0, end]有序，则插入tmp后依然有序
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				//挪动数据
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

复杂度分析

假设有n个数，最坏情况下，插入第二个数比较1次，插入第三个数比较2次……插入第n个数比较n-1次，所以比较次数是一个等差数列求和，时间复杂度为O(n^2)。

当数组是有序时，插入所有数字时都只需和前一个数字比较一次，总共比较n-1次，所以最好情况下时间复杂度可达到O(n)。

排序过程中只创建了end和tmp两个变量，空间复杂度为O(1)。

2.希尔排序

希尔排序实际上是插入排序的加强版，相比于插入排序，希尔排序多了几趟预排序，而且这几趟预排其实也是插入排序的思想。

一趟预排序，就是先将数据分成gap组（每一组数与数的间隔为gap），每组再进行插入排序。每一趟预备排序完成后，将gap的值缩小，进行下一趟预排，直到最后gap变成1，接下来就完全变成了上面的插入排序。

这样做的意义是什么呢？反正最后是一趟就是插入排序，为什么前面还要搞那么多趟预排呢？

上面我们分析了插入排序的时间复杂度，数组越有序，时间复杂度就越低，而预排序的目的就是让数组变得基本有序。

但是这样做真的划算吗？其实可以简单想一想，例如你要将5移动到相应的位置，如果是单纯的插入排序就要移动5次。但如果有了预排序，第一趟的时候gap=5，直接移动gap步就插入到了相应的位置，一次到位。所以希尔排序正好应了那句话，“磨刀不误砍柴功”。

还有一个问题，这个gap怎么定呢？统一取5可以吗？假如是对二三十个数据排序，gap=5，一次可以移动5个位置，看起来还不错。但如果是1万个数字呢？一次才移动次也太小气了吧。所以gap的初始值要根据数据量来定。根据大量的数据测试，或者说主流的写法，gap取初值n/3+1或者n/2比较合适。每完成一趟预排，gap也按照此比例进行缩小。

动图

void ShellSort(int a[], int n)
{
    while (gap > 1)
    {
        //一趟预排序
	    int gap = gap / 3 + 1;
	    //gap组数据排序
	    for (int i = 0; i < gap; i++)
	    {
		    //一组数据排序
		    for (int j = gap + i; j < n; j += gap)
		    {
			    int end = j - gap;
			    int tmp = a[j];
			    while (end >= 0)
			    {
				    if (tmp < a[end])
				    {
					    //挪数据
					    a[end + gap] = a[end];
					    end -= gap;
				    }
				    else
				    {
					    break;
				    }
			    }
			    a[end + gap] = tmp;
	        }
        }
    }
}
 

 上面的写法就是按照我介绍的思路来写的，用到了三层循环,比较好理解。我们还可以简化成两重循环，使代码看起来更简洁

void ShellSort(int a[], int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap; i < n; i++)
		{
			int end = i - gap;
			int tmp = a[i];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

前者的每一趟排序是先排完一组，再排下一组 ，而后者是多组并排。因为组与组之间是互不影响的，不一定非要排完一组再进行下一组。虽然说少了一层循环，但时间复杂度是不变的，所以两种写法都是可以的，根据自己的口味选择。

复杂度分析

  希尔排序的时间复杂度并不能通过高中数学知识简单地计算出来，原因是你不能把每趟的预排和最后的插入排序都按最坏的情况计算。数组越有序，插入排序的效率就越高，而每一趟预排都会使数组变得更加有序，所以前面的排序会影响后面的排序，不能简单地按照最坏情况计算。

我们可以记一个结论，希尔排序的时间复杂度是O(n^1.3)，知道它就够了。

关于空间复杂度，因为创建了常数个变量，所以复杂度为O(1)。

3.选择排序

同样拿摸扑克牌举例，假如打完一局你要去上厕所，你交代下手帮你把牌放到桌上。等你回来，一把抓起所有的牌开始排序，这时候你是怎么做的呢？

你会先浏览一遍，找出最小的那张牌放到第一个位置，然后在剩下的牌中找到最小的放在第二个位置……当所有的位置都排好后这手牌就插完了。

这个浏览找最小牌的过程实际上就是遍历数组找最小值的过程，每遍历一遍数组就可以找到最小的那个数。

动图

void SelectSort(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		int mini = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[mini])
			{
				mini = j;
			}
		}
		Swap(&a[mini], &a[i]);
	}
}

上面的过程是从前往后排，每一趟只能排一个数。其实可以优化一下，从两头向中间靠拢，每一趟选出一个最大值和最小值放在两边，当两边相遇时排序就完成了。

void SelectSort(int a[], int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		
		//交换
		Swap(&a[begin], &a[mini]);
		//如果maxi和begin重叠则maxi需要修正，因为begin的位置已经不是原来的值了
		if (maxi == begin)
		{
			maxi = mini;
		}
 
		Swap(&a[end], &a[maxi]);
 
		begin++;
		end--;
	}
}

这里需要注意，如果你选出那个最大数刚好就在begin的位置，首先你将mini位置和begin位置的值交换，那么begin位置的值就不是最大值了，他已经换到了mini位置，所以要想再交换就必须修正maxi

复杂度分析

按照优化前的选择排序来计算，第一次遍历数组，访问n-1个数据，第二次遍历访问n-2个数据……总共的访问次数是一个等差数列求和，所以时间复杂度为O(n^2)。优化后效率提升了一倍，但依然没有质的变化，访问次数依然是n^2这个量级。

和插入排序不同的是，无论数组是有序还是无序，总之都要遍历n-1次数组，时间效率基本不变。

排序过程中只开了常数个单位的空间，所以空间复杂度为O(n^2)。

4.堆排序

堆是一种重要的数据结构，想要了解堆排序就要知道什么是堆。大家可以参考我以前的文章，里面详细介绍了堆的的相关应用，其中就包括堆排序，还有TopK问题

堆以及堆的相关应用

5.冒泡排序

总共有n个数据，进行n-1趟排序，每一趟排出一个数：相邻两个元素进行比较，如果前者比后者大，就将二者交换，重复此过程，直到将最大的元素交换到末尾则一趟排序完成。由于最大数从前往后不断地挪动，就像泡泡从水底往上缓缓冒出，所以形象地称为冒泡排序。

void BubbleSort(int a[], int n)
{
	//n-1趟
	for (int i = 0; i < n - 1; i++)
	{
        bool exchange = false;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange = true;
			}
		}
		if (exchange == false)
		{
			break;
		}
	}
}

这里有个小小优化，如果一趟冒泡排序下来没有交换任何元素，说明剩下的元素已经有序了，不用继续排了直接退出。

复杂度分析

最坏的情况下比较的次数是一个等差数列求和，时间复杂度是O(n^2)

最好的情况是数组本身有序，经过一趟冒泡就退出了，复杂度是O(n)

开辟常数个单位的空间，空间复杂度O(1)

6.快速排序

快速排序正如它的名字一样，真的非常非常快！以至于基本所有关于排序的库函数底层都是用快排实现的。

快速排序是名叫Hoare的一位大佬，想出来的一种二叉树结构的交换排序方法。快速排序主流版本有三种，第一种就是Hoare当年提出的方法，第二种“挖坑法”，第三种“前后指针法”。虽然三种的代码实现形式不同，但思想都是一致的：任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1.Hoare法

 上面就是快速排序一趟的完整过程，通过这趟排序，我们确定了6的最终位置。也就是说，每趟排序都可以确定一个key值的最终位置。

那总共要排多少趟呢？n-1趟吗？其实不是。因为这一趟排序已经把6排好了，那么下一趟排序它就不应该再参与进来，否则可能又会被挪走。所以应该对6的左边序列和右边序列分别进行排序。

看到这里是否会觉得有些熟悉，这好像是二叉树的前序递归遍历类似呀！！！先访问根节点，再访问左子树和右子树。这里是先单趟排序确定key的位置，然后对key的左右区间进行排序，整个过程是递归的。

递归的出口是什么呢？在不断划分区间的过程中，当该区间只有一个数或者区间不存在时，就可以return了

int PartSort1(int a[], int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}
 
void QuickSort(int a[], int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

tips：

（1）为什么是“>=”,"<=",等号能去掉吗？

不能！！！考虑这样一种情况，如果去掉等号，right在找小的过程中，遇到了和key相等的值就会停下。而left在找大的过程恰好也停在和key相等的位置，left和right交换，进行下一轮循环，right和left在原地又会进行交换，如此就陷入了死循环……

（2）为什么left和right相遇的位置可以保障左边的值小，右边的值大？

整个过程，left和right的作用就是把小的值换到左边来，把大的值换到右边去，所以left和right相遇前肯定是left左边小于key，right右边大于key。关键在于最后一次要将相遇点的值换到最左边，所以必须保障相遇点的值小于key。分两种情况：

第一，left遇right。如果right先停下来，left向右走遇到right停下。那么二者相遇的位置就是right主动停下来的位置，该位置的值一定比key小。

第二，right遇left。极端的情况就是left在keyi的位置还没动，right一直往左走直到遇见left停下，那么相遇点就是keyi，key和自己交换，满足条件。而正常情况是left先停下来与right交换，那么left位置的值就比key小了。新的一轮开始，right向左走遇到key停下，所以相遇点一定小于key。

（3）为什么right要先走，可以让left先走吗？

左边做key，右边先走，这样是为了保障相遇位置的值比key小；右边做key，则要左边先走，以保障相遇位置的值比key大。

2.挖坑法

我们可以发现，Hoare法有许多细节需要我们去推敲，不太容易理解，而挖坑法更好理解。

int PartSort2(int a[], int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
 
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
 
	return hole;
}

因为一开始的坑在左边，所以右边先走填左边的坑，填完之后形成了新的坑，然后让另一边走填坑。最终left和right相遇的位置也是坑，所以把key填进去，一切都那么符合逻辑，顺利成章。

3.前后指针法

 动图

复杂度分析

 递归的过程类似于前序遍历二叉树，每层有n个元素，共有logn层，故时间复杂度为O(logn),递归最深的层数为logn,故空间复杂度为O(logn)。

4.快速排序优化

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。但在某些特定情况下会很慢。上面计算时间复杂度是我们是假设每一趟排序的key最终都放在正中间，所以才有了不断二分的过程。

如果数组是随机的，无序的，会很接近二分的情况。但如果数组是有序的，每次都选择最左边的元素作为key，那么key的最终位置不变，共有n-1趟排序，时间复杂度是等差数列求和，O(n^2)

为了应对这种特殊情况，我们需要保证每次选择的key不是所有数中的最值，尽可能取一个中位数就好了。于是提出随机数取中的办法，即每一次选择两端的数和他们中间的任意一个数，比较他们的大小，取中间的数作为key。

int GetMidIndex(int a[], int begin, int end)
{
	int mid = begin + rand() % (end - begin);
	if ((a[mid] >= a[begin] && a[mid] <= a[end])
		|| (a[mid] <= a[begin] && a[mid] >= a[end]))
	{
		return mid;
	}
 
	if ((a[begin] >= a[mid] && a[begin] <= a[end])
		|| (a[begin] <= a[mid] && a[begin] >= a[end]))
	{
		return begin;
	}
 
	return end;
}

还有一种情况，如果所有的数都相同，随机数取中也没有效果，时间复杂度仍为O(n^2),这时可以采用三路划分的办法，即将数组划分成小于key，等于key和大于key的三部分。思想和前后指针法是类似的，前后指针法实际是划分成小于key和大于等于key两部分。

int PartSort(int a[], int begin, int end)   
{     
        int key = a[begin];
		int left = begin - 1;//小于key的最后一个位置
		int right = end + 1;//大于key的最前一个位置
		int cur = begin;//遍历区间
		//[begin, left][left+1, cur-1][right, end]
		while (cur < right)
		{
			if (a[cur] < key)
			{
				Swap(&a[++left], &a[cur]);
				cur++;
			}
			else if (a[cur] > key)
			{
				Swap(&a[--right], &a[cur]);
			}
			else
			{
				cur++;
			}
		}
}

此外，递归需要开辟频繁开辟栈帧，既消耗空间又消耗时间，可用栈模拟递归过程，改成循环。
以下是快速排序的非递归版本，并结合了随机数取中个三路划分的方法(注意栈是用C语言实现的，代码中没有给出，可用·STL中的stack代替)

void QuickSortNonR(int a[], int n)
{
	ST st;
	STInit(&st);
	
	
	STPush(&st, n - 1);
	STPush(&st, 0);
	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
 
		//随机数取中
		int midi = GetMidIndex(a, begin, end);
		Swap(&a[begin], &a[midi]);
		//三路划分
		int key = a[begin];
		int left = begin - 1;//小于key的最后一个位置
		int right = end + 1;//大于key的最前一个位置
		int cur = begin;//遍历区间
		//[begin, left][left+1, cur-1][right, end]
		while (cur < right)
		{
			if (a[cur] < key)
			{
				Swap(&a[++left], &a[cur]);
				cur++;
			}
			else if (a[cur] > key)
			{
				Swap(&a[--right], &a[cur]);
			}
			else
			{
				cur++;
			}
		}
		//[begin, left][left + 1, rignt - 1][right, end]
		if (end > right)
		{
			STPush(&st, end);
			STPush(&st, right);
		}
 
		if (left > begin)
		{
			STPush(&st, left);
			STPush(&st, begin);
		}
	}
}

7.归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

上述过程好像开辟了很多数组，其实不然，这样太耗费空间了，我们采用的方法是利用begin和end控制区间范围，借用一个临时数组将两组的数归并，然后再拷贝回原数组。

void _MergeSort(int a[], int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
 
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		//谁小谁尾插
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//拷贝回a数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

复杂度分析

归并排序类似于二叉树的后序遍历过程，先使左右两部分有序，然后左右归并。共有logn层，每层n个元素，故时间复杂度为O(logn)。

由于要开辟一个大小为n的临时数组，故空间复杂度为O(n)

归并排序的非递归版本

递归那么多层的目的就是为了不断的划分区间，当一个区间只有一个数时就认为有序了，可以用于归并了。那我直接一开始就一一归并，得到n/2个有序的序列，然后两两归并，得到n/(2^2)个有序序列……最终得到一个有序序列。

动图

 

void MergeSortNonR(int a[], int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	一一归，两两归，四四归………………
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				//谁小谁尾插
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//归并一组，拷贝一组
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		
		gap *= 2;
	}
}

非递归方法的框架建立了，但还有许多细节要考虑。上面的方法只在数据个数刚好是2^n时才适用，否则会出现数组越界问题。例如右6个元素， 第二次归并就出了问题

因此需要处理越界情况。

越界情况我们可以分为三种：

 第一种和第二种情况，第二组的范围根本不在数组以内，而第一组的数据本身就是有序的，所以不需要归并。第三种情况，第二组的部分范围在数组内，需要归并，此时我们只需调整一下范围，把end2改成n-1即可。

 完整代码如下：

void MergeSortNonR(int a[], int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	一一归，两两归，四四归………………
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//处理越界情况
			if (begin2 >= n)//第二组不在数组中，不需要归并
			{
				break;
			}
			if (end2 >= n)//第二组部分在数组中，修正end2后归并
			{
				end2 = n - 1;
			}
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				//谁小谁尾插
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//归并一组，拷贝一组
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		
		gap *= 2;
	}
}

 8.计数排序

算法步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

void CountSort(int a[], int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* countA = calloc(range, sizeof(int));
	if (countA == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	//计数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
 
	//排序
	int k = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[k++] = i + min;
		}
	}
}

 复杂度分析

第一次遍历数组找出最大值和最小值，计算这组数据的范围，并建立一个大小为range的数组countA；第二次遍历数组统计每个数字的出现次数，记录在countA数组中；最后遍历countA数组，并将数据写入到原数组。故时间复杂度为O(MAX(n, range))

额外开辟了一个大小为range的数组，故空间复杂度为O(range)

二.各种排序算法的稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。