数据结构——排序算法（C语言）

本篇将详细讲一下以下排序算法：

1. 直接插入排序
2. 希尔排序
3. 选择排序
4. 快速排序
5. 归并排序
6. 计数排序

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某写关键字的大小，按照递增或递减0排列起来的操作。

稳定性的概念

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变。如一下例子，

5 2 3 4 5 9 8

 经过排序，如果红5和蓝5的相对顺序不对，这就叫稳定，反之则不稳定。

 直接插入排序

直接插入排序的思想：将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的序列中，直到所有的序列为有序序列。

实际中，我们玩扑克牌时，就用到了这样的一个排序算法。

 

时间复杂度： 

直接插入排序时一个稳定的排序，如果有相同的元素，它们的相对位置不会发生变化。它时间复杂度最好的情况下是O（N）,当一个数插入到已经排好序的序列中，只需要比较一次就好了。

最坏情况：O（N^2） ，在完全逆序的情况下，要排升序。

---

希尔排序 

 希尔排序其实和插入排序很像，只不过希尔排序的思想是：先预排序，最后插入排序。

预排序的意义在哪里？？

• 大的数更快到后面去，小的数更快到前面去。gap越大跳的越快，越不有序，当gap =1 时就是插入排序。
• 

 

 

 时间复杂度

 

希尔排序的时间复杂度：大约为O（N^1.3） 

---

选择排序

选择排序的思想：选择排序可以在一次查找中找到最大的数和最小的数，然后把最大的数放到最后，最小的数放到最前面。

 

时间复杂度

时间复杂度是O（N^2）

稳定性：差 

---

 快速排序

快排思想：说到排序，或多或少都听过快速排序，快速排序是Hoare于1962年提出的一种二叉树结构的交换方法，其基本思想为：任取待排序元素序列中的某个元素作为基准值，按照该排序吗将待排序集合分割成2个子序列，左序列小于keyi值，右序列大于keyi值，然后重复此方法，最后拍完序。

快速排序一次可以确定一个值在正确的位置上。（这个值就是key值）

	if (begin >= end)
	{
		return;
	}
	int left = begin, right = end;
	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[keyi], &a[left]);
	keyi = left;
	//[begin,keyi-1]  keyi [keyi+1,end]
	QuickSort(a,begin,keyi-1);
	QuickSort(a,keyi+1,end);

最常见的就是上面的递归代码，这是Hoare的一种方式实现快排。

Hoare思想：让基准值的右边先走，直到找到比基准值小的数，然后让左边走，直到找到比基准值大的数，然后交换，最后left=right相等的时候，将left位置的值与基准值交换。这样就实现了一次排序。

这里我们想一想快速排序为什么要让基准值的对面开始？？？？

 

挖坑法： 用一个tmp记录第一个值的坑位，让右边先走，直到找到比坑位小的数，然后让a[right]赋值给坑位，然后把坑位给给right，继续让左边先走，直到找到比坑位大的数，然后把值赋给坑位，让坑位给给left，一直循环。

 

 

前后指针法：让prev指向key值，cur指向key值之后的一个值，当a[cur] < a[key] 的时候，就让prev++和cur交换，然后一直循环。

 

 

---

快排的非递归： 快排的思想其实不难发现像一个栈（后进先出），因为快排每次可以确定一个基准值的位置，所以，第一次push进left和right，让他们进行一次排序，就接着push进right和keyi+1，再push进keyi-1和left，注意顺序，因为快排的中间也是一个后进先出的思想。

 

快排的缺点

 快排其实是有缺点的，因为快排的时间复杂度不一定是O(N*logN），如果排升序，给一个倒序的序列，就有可能达到O(N^2)。所以有了这么一个缺点，就可以做一个三数区中的优化，其实Sort函数中也有这样的处理，而且Sort中还优化了一次快排递归深度过深的时候会用堆排序，在接近有序的时候会用插入排序，而且Sort中只对了右边进行递归处理。如果有兴趣，可以去了解一下Sort的源码，里面有详细解释。

---

 归并排序

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

归并排序可以看出是一个后序的排序， 先递归，然后从前面开始排好序，然后再memcpy到原数组。

归并排序其实用在解决磁盘外的外排序问题中，如果有下面的场景，归并排序就起到了很大的作用。

时间复杂度

 归并排序也是一种经典的O(N*logN)  空间复杂度是O(N),这时因为开辟了一块tmp临时数组

---

 

计数排序 

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

步骤：1.统计想相同元素出现的次数

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

 

 计数排序的特性：

1. 计数排序在数据范围集中时，效率很高，但是使用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)

   ---