排序

排序的概念

• 排序 ：所谓排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
• 排序的稳定性： 排序前后两个相等的数相对位置不变，则算法稳定。
  稳定性是一种人为刻意为之的行为，任何一个稳定的排序方法都可以写成不稳定的。稳定性的意义在于确定值相等的值的输入顺序，有一定参考作用。

同时 还有两个比较基础的概念：

• 内部排序： 数据元素全部放在内存中的排序
• 外部排序： 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

直接插入排序

插入排序的思想十分的简单：
把待排序的元素插入到一个 有序序列 的 正确的位置，直到所有的记录插入完全为止，得到一个新的有序序列。
其实我们在玩扑克牌的时候就是这个思想

为了能更好的理解插入排序，我们从他的一次循环看起：（以升序为例）

• 假设数组a为一个前（end+1）个数有序数组，我们要把第end+1个数插入数组中
  

• 循环的基本思路是： 如果a[end]比temp（待插入的数）要小，就说明还要继续往下寻找，这是执行a[end+1]=a[end]，并将end- -，循环的条件时end >=0
  
  
  

• 直到找到比 temp要小的数 或者 end==0 时还没有找到，这时就要跳出循环执行：a[end+1]=temp
  注意： 这里如果end==0时还没有找到的时候，出循环的时候end为-1，但是a[end+1]实际上还是第一个元素
  

• 这是直接插入排序的一次单次循环，实际上我们发现直接插入排序一个重要的前提是要有一个有序的数组。

在排序的最开始 我们可以认定第一个数为一个大小为1的有序数组，来启动上述介绍的单次循环，循环结束我们就得到了一个前两个元素有序的数组 …直到前n-1个元素（数组大小为n）有序，将最后一个元素插入，这是最后一次循环。 所以我们还要在上面单次循环的基础上在加一个循环来完成排序

代码

void InsertSort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int temp = a[i + 1];
		while (end >= 0)
		{
			if (a[end] > temp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = temp;
	}
}

总结

• 时间复杂度：O(N^2)
• 空间复杂：O(1)
• 稳定性：稳定

希尔排序

希尔排序实际上是在插入排序的基础上做出了一些改进，希尔排序又叫缩小增量法。

其基本思想是：
将数组按一定间隔分成若干个组，对每个组里面的元素进行直接选择排序，然后缩小间隔，在对重新分的组挨个进行选择排序…直到最后间隔为1（实际上直接插入排序是间隔为1的希尔排序）

• 我们以一个数组为例进行希尔排序：
  
• 然后就要对数组进行分组排序，第一次我们把间隔gap设为5
  
• 然后我们要不断缩小间隔，在进行重新分组并排序，这次我们把间隔调成2
  
• 最后一次我们把间隔gap调成1
  
  我们从中可以发现一些规律：

1. 希尔排序是对直接插入排序的一种优化
2. 随着gap的不断减小，数组越来越趋于有序。其实gap>1时都是预排序，目的是让数组更有序。gap==1时，数组已近接近有序。这样最后一次排序就很快，达到优化的效果。
3. 希尔排序的时间复杂度不好去计算，因为gap的取值方法很多，导致很难去计算。

代码

void ShellSort(int* a, int n)
{
	int gap = n ;

	while (gap > 1)
	{
		gap = gap / 3 + 1; //注意这里是以三倍的速度缩小gap，这里+1是因为要保证最后一次gap为1
		for (int i = 0; i < n -gap; i++)
		{
			int end = i;
			int temp = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = temp;
		}
	}
}

总结

• 时间复杂度：O(N^1.25) 这是通过大量实验得到的经验公式
• 空间复杂：O(1)
• 稳定性：不稳定

选择排序

基本思路：
每次遍历整个数组从数组中选择出最大的数（或最小的数），最放到数组的末尾（或数组的首尾），直到全部待排序的数据元素排完

我们以一个数组为例：

• 在begin和end之间（包括begin和end）中找到max和min，并让min和begin、max和end交换
  注意：这里交换的先后顺序，到后面会有些区别！
  
• 按上述步骤不断重复

---

• 最后一次交换比较有代表意义，是一个容易犯的错误，如果先让begin和min交换再让max和end交换会产生一个问题：那就是max和begin重合的时候，如果begin先和min交换，那么max的值会被交换到min上，这时就需要end和min交换
  
  代码：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int min = begin;
		int max = end;
		for (int i = begin+1; i < end;i++)
		{
			if (a[i] > a[max])
				max = i;
			if (a[i] < a[min])
				min = i;
		}


		swap(&a[begin], &a[min]);

		if (begin != max)
			swap(&a[end], &a[max]);
		else
			swap(&a[end], &a[min]);

		begin++;
		end--;
	}
}

总结：

• 时间复杂度：O(N^2)
• 空间复杂：O(1)
• 稳定性：不稳定

堆排序

可以参考一下以前的博客：数据结构：堆 的详解

代码：

void AjustDown(int* a, int n, int parents)
{
	int child = 2 * parents + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			child++;
		if (a[child] > a[parents])
			swap(&a[child], &a[parents]);
		parents = child;
		child = 2 * parents + 1;
	}
}


void HeapSort(int* a, int n)
{
	for (int i = n/2-1 ; i >= 0; i--)
	{
		AjustDown(a,n,i);
	}

	for (int i = n-1; i >0 ; i--)
	{
		swap(&a[0], &a[i]);
		AjustDown(a, i, 0);
	}
}

总结：

• 时间复杂度：O(N*logN)
• 空间复杂：O(1)
• 稳定性：不稳定

冒泡排序

基本思想： 就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，在视觉上的效果像：较大键值的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

• 我们以冒泡排序的一次遍历为例：
  遍历的规则是：两两进行比较，如果前者大于后者就交换，否则就继续往下走。这里要注意一下a[j]的范围是闭区间[0,n-2]，也就是n-1次比较。

---

---

---

---

---

---

看完一次循环大家或许就理解了冒泡排序名字的由来，最大的数像气泡一样向上移动，在往下思考这次遍历过后，实际上最后一个已经是有序的了，所以还要进行n-1次这样的遍历，所以时间复杂的是O((n-1)+(n-2)+(n-3)+(n-4).....+0)=O(n^2)
代码

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int k = 0;
		for (int j = 0; j < n - 1 - i; j++) //每一次遍历结束，下一次要遍历的个数都会减少一个
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				k = 1;
			}
		}
		if (k == 0)
			break;
	}

}

• 这里特意设计了以个变量K，来面对 数组已经是有序的情况 ，如果数组有序的话，就不会进行任何一次交换，所以这时k的值就不会被修改，这样检测到未修改，就可以直接跳出循环了。

总结：

• 时间复杂度：O(N^2) 最好情况是：O(N)
• 空间复杂：O(1)
• 稳定性：稳定

快速排序

快排的思路：
任取待排序元素序列中的某元素作为基准值，按照该基准值将排序分成两个子序列，左子序列的元素均小于基准值，右子序列的元素均大于基准值，，然后在左、右子序列重复上述过程，直到所有元素都有序为止

下面介绍快排的三个版本：

1.hoare版本

思路：

1. 首先从头部或者尾部选出一个值做key（基准值），这里取头部元素a[0]
2. 右边先找（这个很重要！！！！），从数组尾部开始寻找比key小的值，找到后停止。
3. 左边去找，从数组首部开始寻找比key大的值，找到后与右边的进行交换
4. 重复上述步骤直到左边与右边相遇为止，这时把key与相遇位置的值进行交换，完成排序！

看完这个思路之后，我们直到整体思路就是，从左边找比基准值大的与右边找到的比基准值小的进行交换，但是在这里要思考清楚一个问题：
既然最后一步是将相遇的值与key的值交换，也就是说明左右相遇时指向的值一定比key小，这是为什么？
我们从两个情况去考虑：

1. 首先是左边移动与右边相遇，这毋庸置疑右边本来就是找比key小的值，所以相遇时指的值一定比key小
2. 其次时右边移动与左边相遇，这种情况也分两种情况，一种就是左边从来就没移动过，还指向key值，这是key值与自己交换，第二种是左边移动过一次或多次，虽然左边是找比key大的值，但不要忘了在右找左之前，会交换左右的值，交换过后左边就是比key小的值，相遇时也就是比key小的值

我们以第一次循环为例：

---

---

这里我们就实现了把数组分成了两个子序列（左子序列的元素均小于基准值，右子序列的元素均大于基准值），然后我们把这两个子序列看成一个新的序列，对其指向执行相同的程序，并一直递归下去，直到 传进去的数组的 大小为 0 （没有左子序列 或 右子序列 也就是key比该序列的所有元素都要大或小） 或 1（没有执行程序的必要）。实际上执行的思路入下图所示

代码

void QuickSort1(int* a, int n)     //hoare版本
{
	if (n == 1 || n == 0)
		return;
	int key = 0;
	int left = 0;   //这里必须从0开始，如果从1开始，当数组只有两个的时候代码会出现问题
	int right = n - 1;
	while (left < right)  //这里必须是小于号保证出循环left一定等于right
	{
		while (left<right && a[right] > a[key])
			right--;


		while (left<right && a[left] <= a[key])    //注意这里的大于等于号 因为key在左边，为了让key往左走必须大于等于
			left++;

		swap(&a[left], &a[right]);


	}
	swap(&a[left], &a[key]);
	key = left;

	QuickSort1(a, key);
	QuickSort1(a + key + 1, n - key - 1);

}

2.挖坑法

思路：

1. 首先从头部或者尾部选出一个值做key（基准值），把key的值拷贝给临时变量temp，并把数组第一个元素当作第一个“坑”
2. 右边先找（这个很重要！！！！），从数组尾部开始寻找比key小的值，然后填上面挖的“坑”。
3. 左边去找，从数组首部开始寻找比key大的值，找到后填上面挖的“坑”
4. 重复上述步骤直到左边与右边相遇为止，这时把temp与相遇位置的“坑”填上，完成排序！

我们以一次循环作为基础：

• 首先我们选择首元素作为第一个坑
  
• 然后右边找小，填到左边的坑里
  
• 然后是左边找大，填到右边的坑里，后面重复上述步骤
  

---

---

-最后一步左右重合，将temp中的值填入坑内

代码

void QuickSort2(int* a, int n)          //快排——挖坑法
{
	if (n == 1 || n == 0)
		return;
	int key = 0;
	int left = 0; 
	int right = n - 1;
	int temp = a[key];
	while (left < right)
	{
		while (left<right && a[right]>temp)
			right--;
		a[left] = a[right]; //填左边的坑


		while (left<right && a[left]<= temp)
			left++;
		a[right] = a[left];  //填右边的坑

	}
	a[left] = temp;  //最后左右相遇时，填坑
	key = left;
	
	QuickSort2(a, key);
	QuickSort2(a + key + 1, n - key - 1);
}

前后指针法

基本思路： 设置两个指针（prev，cur），还是在数组的头或尾找一个基准值，prev指向第一个元素，cur指向第二个元素，然后cur开始遍历数组，找到比基准值小的值就与prev下一个元素交换，直到cur遍历完数组。
我们以一次循环作为基础：

• 首先我们选择首元素作为第一个坑
  

---

如果没有遇到比基准值小的数cur就直接往后走，找到比基准值小的数就开始交换。

其实我们还可以把数组的最后一个数设为基准值，这时程序也要相应的做出一点改变
这时prev的其实位置就必须时数组第一个数的前一个位置，也就是下表为-1的位置，cur起始位置时数组的 首元素，其他的步骤与上面的一样。

代码

void QuickSort3(int* a, int n)   //快排——双指针法
{
	if (n == 1 || n == 0)
		return;
	int key = 0;
	int prev = 0;
	int cur = 1;
	while (cur < n)
	{
		if (a[cur] < a[key])
			swap(&a[++prev], &a[cur]);
		cur++;
	}
	swap(&a[prev], &a[key]);
	key = prev;
	
	QuickSort3(a, key);
	QuickSort3(a + key + 1, n - key - 1);
}

快排的非递归方法（循环）

把递归转换成非递归有两种方法：

1. 直接转换成 循环
2. 把递归问题转换成 栈 + 循环

因为递归是把大事化成若干个小问题去解决，循环正好是反过来人为的从小问题开始解决。但是有时候递归在把大问题化成小问题的时候，小问题是建立在大问题的基础上的，不解决大问题就无法得到小问题，所以用循环就无法从小问题开始解决，这时就要用到栈的结构，栈的结构正好将这种情况完美解决，从 入栈时的大->小 ，到 出栈进入循环时的 小->大

本体思路：

1. 首先把数组的左右边界先入栈
2. 然后进入循环，取出栈里第一个区间的左右边界，并让左右边界出栈，对齐做单趟排序，这时就的到了key和两个左右子序列，把左右子序列的左右边界分别入栈。
3. 重复上述步骤，直到栈为空

注意：
这里要注意入栈和出栈时的左右边界的顺序，左边界先入栈，右边界后入栈，取栈顶元素时就要先取右边界并出栈，再取左边界

代码

int Partsort(int* a, int left,int right)  //单趟排序
{
	int key = left;
	int temp =Choose_Key(a,left,right);
	swap(&a[temp], &a[left]);
	while (left < right)
	{
		while (left<right && a[right] >= a[key])
			right--;

		while (left<right && a[left] <= a[key])
			left++;

		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[key]);
	return left;
}

void QuickSortNonR(int* a, int n)   //快排的非递归写法
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 0);        // 入左边界
	StackPush(&ps, n - 1);     // 入右边界

	while (!StackEmpty(&ps))
	{
		int end = StackTop(&ps);  //右边界先出栈  一定要和上面入栈的顺序相反！！！！
		StackPop(&ps);

		int begin = StackTop(&ps);  //左边界出栈
		StackPop(&ps);

		int keyi = Partsort(a, begin, end);
		if (keyi + 1 < end)   //判断是否要继续递归
		{
			StackPush(&ps, keyi + 1);    // 右子序列的 左边界入栈
			StackPush(&ps, end);         // 右子序列的 右边界入栈
		}

		if (begin  < keyi-1)
		{
			StackPush(&ps, begin);       //右子序列的 左边界入栈
			StackPush(&ps, keyi - 1);    // 右子序列的 右边界入栈
		}
	}
	StackDestroy(&ps);

}

时间复杂度优化问题

快排的时间复杂度最快的时候可以达到O(N*logN) ,但是当数组为有序的时候 或 有大面积重复的时候，时间复杂度会飙升到O(N^2)
为了解决这种情况，首先要了解为什么会出现这种情况？
最主要的原因是 key每次都取到了整个数组的 最小值或最大值 ，使二叉树变成单边树，这时我们只需要对key选取的值稍加处理就可以了，我们采用三数取中 即选取数组 左 、 中 、 右 大小在中间的数，与key所在的位置交换。
代码

int Choose_Key(int *a,int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[mid] > a[left])
			return left;
		else
		{
			if (a[right] > a[mid])
				return right;
			else
				return mid;
		}

	}
	else
	{
		if (a[mid] > a[right])
			return right;
		else
		{
			if (a[left] > a[mid])
				return left;
			else
				return mid;
		}
	}
}

void QuickSort2(int* a, int n)          //以快排——挖坑法为例
{
	if (n == 1 || n == 0)
		return;
	int key = 0;
	int t = Choose_Key(a, 0, n - 1);  // 选出中间元素的下标
	swap(&a[key], &a[t]);         //与key所在位置的元素交换
	int left = 0; 
	int right = n - 1;
	int temp = a[key];
	while (left < right)
	{


		while (left<right && a[right]>temp)
			right--;
		a[left] = a[right];


		while (left<right && a[left]<= temp)
			left++;
		a[right] = a[left];



	}
	a[left] = temp;


	key = left;
	QuickSort2(a, key);
	QuickSort2(a + key + 1, n - key - 1);
	

}

总结：

• 时间复杂度：O(N*logN) 最坏的情况：O(N^2)
• 空间复杂：O(logN)
• 稳定性：不稳定

归并排序

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

递归法

如上图所示，单趟排序的过程是一个很经典的问题，创建一个额外的数组，将两个顺序的子序列排序，我们只要定义两个个指针，分别指向 待排序的两个序列，对指针所指的内容进行比较，如果满足条件就进入新数组，重复上述步骤直至所有元素都拷贝到新数组。
单趟排序思路了解之后，我们直到单趟排序需要两个有序的序列，所以就用递归将数组不断划分，当序列只有一个元素的时候我们认为他就是大小为1的有序序列，进行单趟排序。然后把排完序的子序列在进行合并的过程。

void _MergeSort(int* a, int left,int right,int *temp)
{
	int mid = (left + right) / 2;
	if (left >= right)
		return;
	_MergeSort(a, left, mid,temp);
	_MergeSort(a, mid + 1, right,temp);

	int cur1 = left, end1 = mid;
	int cur2 = mid + 1, end2 = right;
	int cur3 = left;

	while (cur1 <= end1 && cur2 <= end2)
	{
		if (a[cur1] <= a[cur2])
		{
			temp[cur3] = a[cur1];
			cur3++;
			cur1++;
		}
		else
		{
			temp[cur3] = a[cur2];
			cur3++;
			cur2++;
		}
	}
	while (cur1 <= end1)
	{
		temp[cur3] = a[cur1];
		cur3++;
		cur1++;
	}
	while (cur2 <= end2)
	{
		temp[cur3] = a[cur2];
		cur3++;
		cur2++;
	}
	for (int i = 0; i <= right; i++)
	{
		a[i] = temp[i];
	}

}

void MergeSort(int* a, int n)
{
	int* temp = (int*)malloc(n * sizeof(int));
	_MergeSort(a, 0, n - 1, temp);
}

非递归法

非递归的思路是

1. 我们首先把数组 两个一组 分组，组内对半分成两个子序列（序列大小为1），按照单趟排序排序
2. 我们首先把数组 四个一组 分组，组内对半分成两个子序列（序列大小为2），按照单趟排序排序
   …
3. 直到数组 小于等于 分组大小（这时最后一次），组内对半分成两个子序列（序列大小为2），按照单趟排序排序

注意：
这里的难点是分组的边界问题

1. 当第二个序列完全就不存在时，我们这时对end2进行修改，使其小于begin2，下面的单趟排序，由于受begin2 < end2的限制，会跳过一切与第二个序列有关的步骤，只留下对第一个序列的操作。对end1进行修改使其不会越界。
2. 当第二个序列部分存在时，只需要修改end2，使其不会越界即可。

void fun(int cur1,int end1,int cur2,int end2,int cur3,int *temp,int *a)
{
	while (cur1 <= end1 && cur2 <= end2)
	{
		if (a[cur1] <= a[cur2])
		{
			temp[cur3] = a[cur1];
			cur3++;
			cur1++;
		}
		else
		{
			temp[cur3] = a[cur2];
			cur3++;
			cur2++;
		}
	}
	while (cur1 <= end1)
	{
		temp[cur3] = a[cur1];
		cur3++;
		cur1++;
	}
	while (cur2 <= end2)
	{
		temp[cur3] = a[cur2];
		cur3++;
		cur2++;
	}
	for (int i = 0; i <= end2; i++)
	{
		a[i] = temp[i];
	}
}
void MergeSortNonR(int* a, int n)
{
	int* p = (int*)malloc(n * sizeof(int));
	int index = 2;
	while ((n*2) / index)
	{
		int times = n / index;
		if (n % index != 0)
			times++;
		for (int i = 0; i < times; i++)
		{
			int cur1 = i * index, end1 = cur1+ index/2 -1;
			if (end1 > n - 1)
				end1 = n - 1;
			int cur2 = cur1 + index / 2;
			int	end2 = cur2 + index/2 - 1;
			if (end2 > n - 1)
				end2 = n - 1;
			int cur3 = cur1;
			fun(cur1, end1, cur2, end2, cur3, p, a);

		}
		index *= 2;

	}
	free(p);
}

总结：

• 时间复杂度：O(N*logN)
• 空间复杂：O(N)
• 稳定性：稳定

计数排序

思想：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
   

void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)   //找出最大最小值确定开辟数组的范围
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;
	int* p = (int*)calloc(range, sizeof(int));
	for (int i = 0; i < n; i++)
	{
		p[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (p[i])
		{
			a[j++] = i + min;
			p[i]--;
		}
	}
}

总结：

• 时间复杂度：O(max(N,最大值与最小值之间元素的个数))
• 空间复杂：O(范围)
• 稳定性：稳定

总结

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	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(N^1.2)	不确定	O(N^2)	O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(n)	稳定
快速排序	O(N*logN)	O(N*logN)	O(N^2)	O(1)	不稳定
计数排序	O(max(N,最大值与最小值之间元素的个数))	-	-	O(范围)	稳定