1.排序的概念及其运用

1.1排序的概念

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

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

内部排序：数据元素全部存在内存中的排序。

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

1.2排序应用

排名，商品筛选等。

1.3常见的排序算法

插入排序	直接插入排序
希尔排序
选择排序	选择排序
堆排序
交换排序	冒泡排序
快速排序
归并排序	归并排序

2.常见排序算法的实现

1.插入排序

基本思想：有一个有序区间，插入一个数据，依旧保持他有序。

1.1单趟插入排序

假设n-1个数据是有序的，第n个数据是要插入的数据，那么从后往前进行插入，原因：挪动数据比较方便。

画图：


void InsertSort(int* a, int n)
{
	//记录倒数第二个数据的下标
	int end = n - 2;
	//记录最后一个数据
	int tmp = a[end + 1];
	while (end>=0)
	{
		if (tmp < a[end])
		{
			//将数据往后挪一位
			a[end+1] = a[end];
			end--;
		}
		else
			break;
	}
	//考虑极限情况，插入的数据是最小的，那么end就为-1.
	a[end+1] = tmp;
}

多趟即可实现完全版插入排序


void InsertSort(int* a, int n)
{
	//将单趟做成循环就行
	for (int i = 0; i < n-1; i++)
	{
		//单趟是[0,end]是有序的，end+1是需要处理的元素
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

时间复杂度：O(N^2)

最好的情况：顺序有序O(N)

1.2.希尔排序（缩小增量排序）

基本思想：先选定一个整数，吧待排序文件中所有记录分成个组，所有距离为的记录分在同意需内，并对每一组内的记录进行排序。然后，去重复上述分组和排序的工作。当到达1是，所有记录在同一组内排好序。

实现思路：1.预排序接近有序

2.直接插入排序

预排序：分组排大，大的数更快到后面去，小的数更快到前面，接近有序。

分割：

先进行预排序：

调换三次：

5 1 2 5 6 3 8 7 4 9

代码延续插入排序的基本思路，只是“1”变为了gap


//手动规定gap = 3
	int gap = 3;
	//for循环控制走三次
	for (int j = 0; j < gap; j++)
	{
		//单趟选择，但要走三次
		for (int i = j; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}

2.gap = 1时，进行一次插入排序即可。

考虑优化一下代码，使得不用调用插入排序就能直接实现希尔排序。

思路：官方并未给gap任意的限制，可知gap的取值并不能完全影响希尔排序。

所以考虑用数学的方法，手动规划让gap最后一步等于1，完成最后的插入排序。

一般情况下gap = 3为最佳。

gap = gap / 3 + 1;

代码：


	//gap的取法没有啥具体的讲究，可随意取。
	int gap = n;
	while (gap > 1)
	{
		//保证最后一次gap==1，完成一次完整的插入排序。
		gap = gap / 3 + 1;
		//因为代码中出现了 end+gap 所以 判断部分就必须防止数组越界，为n-gap
		for (int i = 0; i < n - gap; i++)
		{
			//这里采用的是三路各走一步的方式来做，
			//将三个阶段的第一小阶段先走
			//插入排序的老套路
			int end = i;
			int tmp = a[i + gap];
			while (gap >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
 
	}
}

总结：

1.希尔排序是堆插入排序的优化。

2.当gap>1时都是预排序，目的是让数组更接近有序。当gap == 1时，数组几乎就是有序的了，这样就会很快。

整体而言，可以达到优化结果。

3.希尔排序的时间否咋读不太好计算，因为gap的取值方法很多，所以希尔排序的时间复杂度是不确定的。

4.稳定性：不稳定。

3.选择排序

3.1基本思想

每一次从待排序的元素中选出最小的（或最大）一个元素，存放在序列的起始位置，知道全部待排序的数据元素排完。

在学习C语言的时候，就会介绍选择排序，现在选有的基础上进行优化，同时进行最大最小元素的处理。

方法：采取双下标的方法，定义left 和 right maxi 和 mini 开始做比较，若是a[i]>a[maxi]

交换，a[i]<a[mini] 交换,知道left>=right.

这里存在一个小问题，代码中会有说明。


void SelectSort(int* a, int n)
{
	//以升序为例
	//左右，记录下标
	int left = 0, right = n - 1;
	while (left < right)
	{
		int maxi = left;
		int mini = left;
		//遍历，在[left+1,right]中找到最大值，最小值的下标
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
			//交换最小值和最左边值的位置
			Swap(&a[mini], &a[left]);
			//如果left 和 maxi 重合，修正即可
			//在遍历过程中，前面交换了，再次进行交换2就是得最小值标
			//调换到right位置。
			if (left == maxi)
				maxi = mini;
			//交换最大值和最右边的值的位置
			Swap(&a[maxi], &a[right]);
		left++;
		right--;
	}
}

总结：

1.直接选择排序思路非常好了解，但效率低，实际操作很少使用。

2.时间复杂度：O(N^2)

3.空间复杂度：O(1)

4.稳定性：不稳定。

4.堆排序

堆排序是在选择排序的基础上，以二叉树为载体，构建的一种效率更优的一种算法。


void AdjustDown(int* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//选出左右孩子中较大的那一个
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void HeapSort(int* a, int n)
{
	//向下调整建堆,升序建大堆,并把最大的值放在根结点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n,i);
	}
	
	//循环调整堆
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}	
}

总结：

1.效率高

2.时间复杂度：O(N*lonN)

3.空间复杂度：O(1)

4.稳定性：不稳定

交换排序

冒泡排序

冒泡是第一个学习的排序，所以可以直接整完全版的。

冒泡基本思想：相邻两个元素比较，交换位置。

交换函数：


void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		//因为是两两比较，所以当单趟走完exchang未发生变化，就能说明，
		// 相邻的两个数符合“规则”。
		//单趟
		for (int j = 1; j < n - i; j++)
		{
			if (a[j] < a[j - 1])
			{
				Swap(&a[j], &a[j - 1]);
			}
		}
	}
}

优化：


void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		//因为是两两比较，所以当单趟走完exchang未发生变化，就能说明，
		// 相邻的两个数符合“规则”。
		//单趟
		for (int j = 1; j < n - i; j++)
		{
			if (a[j] < a[j - 1])
			{
				exchange = 1;
				Swap(&a[j], &a[j - 1]);
			}
		}
		if (exchange == 0)
			break;
	}
}

虽然优化了，但由于冒泡算法时间复杂度为O(N^2),所以在处理较多数据时，还是远远不如其他排序，但它好理解。

6.快速排序

快速排序是一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某一个元素作为基准值，

按照该排序码将待排序集合分割成两个子序列，做子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，

然后最左右序列重复该过程，知道所有元素都排列在相应的位置上。

将区间按照基准值划分为左右两半部分的常见方式有：

1.hoare版本

单趟排序：选出一个key，一般是第一个或者最后一个数。

要求：左边的值都比key小，右边的值都比key大。

如何保证相遇的位置比key小？

右边先走保证。

R先定下来，L走去遇到R

相遇的位置是比key小的。

刚交换完，R先走，R没有找到比key小的直接跟L相遇。

相遇点而为之也是比key小的。

也就是说，key的位置在哪完全是随机的，比不是意味着key必须在中心位置。

先将单趟排序完成：


//单趟的目的是，keyi左边都是小于a[keyi]的数据，右边都是大于a[keyi]的数据
int PartSort1(int* a, int left, int right)
{
	int midi = GetKeyi(a, left, right);
	Swap(&a[left], &a[midi]);
	//规定keyi，一般为第一个数或者最后一个数。
	
	int keyi = left;
	while (left < right)
	{
		//循环，找到不符合的那个数据的下标
		while (a[keyi] <= a[right] && left < right)
		{
			right--;
		}
		while (a[keyi] > a[left] && left < right)
		{
			left++;
		}
		//交换数据
		Swap(&a[left], &a[right]);
	}
	//此时将keyi的位置与left交换
	
	Swap(&a[left], &a[keyi]);
	return keyi;
}

行完单趟排序后，key放在了合适的位置，可以采取分治递归的思想，将其完成排序。


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//先单趟排序,找到keyi
	int keyi = PartSort1(a, begin, end);
 
	//递归分治
	//数据现在被分为[begin,keyi-1] keyi [keyi+1,end]
	//对[begin,keyi-1] 和 [keyi+1,end] 进行处理排序
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2.挖坑法

将一端第一个数存放在临时变量中，构成第一个坑位。从另一端开始寻找符合关系的数，

去占领上一个数的坑位。依次循环，当left>=right时，将临时变量放入最后的坑位。

画图：

right--

找到比key小的值，将值放入pit中，同时更新pit

left左移，寻找比key大的值

当left = right时，循环结束，key扔进pit即可

代码：


//挖坑法
int PartSort2(int* a, int left, int right)
{
	//找好坑位。
	int key = a[left];
	//key定在左边
	int pit = left;
	//从右找小于key的数
	while (left < right)
	{                           //防止a[right]和key相等，导致陷入死循环
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] < key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
		
	}
	a[pit] = key;
	return pit;
}

对比hoare版本：

1.比hoare版本好理解。

2.本质上没啥大的差别。

3.前后指针版本

思路：定义两个指针，prev 和 cur ，cur找比key小的数，prev找比key大的数，

找到后，两者交换位置，循环结束后，a[keyi] 与 a[prev]交换值。

画图：


int PartSort3(int* a, int left, int right)
{
	//以左边为例
	int keyi = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{      // 找小                    //用于规避无用的交换操作
		if (a[cur] < a[keyi] && a[++prev] != a[cur])
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

快速排序的时间复杂度

最好的情况：每次都是接近或者就是二分的，时间复杂度：O(N*logN)

最坏的情况：每次所分的都是最小值或者最大值，相当于二分失效了，时间复杂度：O(N^2).

相差还是蛮大的。

优化一：

考虑对快速排序进行优化，使得其时间复杂度更加靠近O(N*logN)

可以发现：出现最坏的情况还是和keyi的取向有极大的关系，考虑去取区间内的某一个随机值。

可以考虑取其a[left] a[right] a[midi] 的中间值，来实现一定的“伪随机”。

三者比较取其中，代码：


int GetKeyi(int* a,int left, int right)
{
	int midi = left + (right - left) / 2;//防止溢出
	//比较，选出中间的一个
	if (a[left] < a[right])
	{
		if (a[right] < a[midi])
			return right;
		else if (a[midi] < a[left])
			return left;
		else
			return midi;
	}
	else //a[left]>=a[right]
	{
		if (a[midi] < a[left])
			return midi;
		else if (a[midi] > a[left])
			return left;
		else
			return right;
	}
 
}

在原有代码中稍作修改，就可以继续使用原有代码了。

因为返回的是下标，那么考虑将返回下标的值与最初设立的下标的数进行交换，就不会打乱原有的代码。

优化二：不痛不痒，相较于优化一，优化的情况不是太大。

递归是要调用栈帧的，当数据趋于有序，接近有序的时候，可以考虑减少栈帧的调用，采用插入排序的方法，

实现最后一步。希尔排序不是也延续了这种思想吗？


//优化二：递归调用可以减少部分，以10为界
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin + 1 < 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	//先单趟排序,找到keyi
	int keyi = PartSort1(a, begin, end);
	//int keyi = PartSort2(a, begin, end);
	//int keyi = PartSort3(a, begin, end);
	
	//递归分治
	//数据现在被分为[begin,keyi-1] keyi [keyi+1,end]
	//对[begin,keyi-1] 和 [keyi+1,end] 进行处理排序
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

提升不太明显，但也算有所提升。

快排非递归代码：

递归是创建栈帧的，这里可以通过数据结构中的栈，完成对“递归”的模拟和替代

可以极大的提高代码的运行效率。


//快速排序的非递归版本
/*快速排序递归本质上就是调动函数栈帧，可以考虑用数据结构的栈来完成*/
 
void QuickSortNone(int* a, int begin, int end)
{
	//建栈
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	//当栈不为空就继续。
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		//找keyi
		int keyi = PartSort2(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		//用栈模拟递归,左部分
		if (left < keyi - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
		//右部分
		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
	}
	StackDestroy(&st);
}

归并排序

基本思想：是建立在归并操作上的一种由小的算法，采用分治法的一个典型应用。

将已有的子序列合并，得到的完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两者合并成一个有序表，称为二路归并。

思路图：

分解：递归分治完成

归并：将一个集合看做一个数组，实现2个小数组合并成一个数组。这里可以动态申请一个

tmp数组，在tmp数组中完成合并后，再拷贝回原数组。


//归并排序
//建立在归并排序上的一种有序算法，递归分治
//归并排序是完全的二分
//递归版本
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//递归分治，将数据分割成不可再分的单一元素。
	if (begin >= end)
		return;
	int mid = begin + (end - begin) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//[begin, mid] [mid + 1, end] 
	//开始归并，就是给定两个数组，将两个数组合并成一个有序的数组tmp，最后再拷贝进原数组。
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while(begin1<=end1)
		tmp[index++] = a[begin1++];
	while(begin2<=end2)
		tmp[index++] = a[begin2++];
	//拷贝
	memcpy(a + begin , tmp + begin , sizeof(int) * (end - begin + 1));
}


void MergeSort(int* a, int n)
{
	//归并排序是需要分治至最小单元后，再进行局部->整体的有序，一般情况下，可以创建临时
	//空间进行辅助。
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		exit(-1);
	_MergeSort(a, 0, n - 1, tmp);
 
	//释放空间
	free(tmp);
}

出现了递归，那么就可以考虑一下非递归版本。

考虑递归本身就是将原数组进行分割化为单一元素，那么非递归就可以考虑将这一步循环完成，或者直接完成归并。

直接将原有的数组分割难度有点大，所以考虑反着来，考虑由单一的数到整个数组推广。

前面提及，归并排序使完全的二分，那么，就可以考虑每次乘2来完成“归并”。

归并测试数组：

int a[] = { 9,1,2,5,7,4,8,3,5,6};

思路：排序由单一的一个数到整个数组，间隙gap从1每次*2直到>=n跳出循环。

数组中的数据处理完所有组后，在进行下一个gap的循环归并。所以返回划分比较绕而且比较重要。

先完成第一版：


//非递归版本
//将原先递归分治改为循环来处理
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		exit(-1);
	memset(tmp, 0, sizeof(int) * n);
	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 index = i;
			//printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
				tmp[index++] = a[begin1++];
			while (begin2 <= end2)
				tmp[index++] = a[begin2++];
		}
		memcpy(a, tmp, n * sizeof(int) );
		gap *= 2;
	}
	free(tmp);
}

代码有bug，打印归并数的下标：

可以发现：除了begin1，end1,begin2,end2都有越界的情况。

所以思路错了吗？不，考虑进行手动修正代码即可。

分三种情况：

end1越界，手动修改回n-1即可
begin2越界，代表[begin2,end2]已经是不存在的区间了，begin2>=end2即可。
end2越界，这里考虑将end2 = n-1即可。


//非递归版本
//将原先递归分治改为循环来处理
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		exit(-1);
	memset(tmp, 0, sizeof(int) * n);
	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 index = i;
			//printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			//出现了越界访问的问题，要手动修正
			//出现越界的有：end1 begin2 end2
			//end1越界
			if (end1 >= n)
				end1 = n - 1;
			//begin2 越界,[begin2,end2]就不该存在。
			if (begin2 >= n)
			{
				begin2 = -1;
				end2 = -2;
			}
			//只有end2越界，那就将end2修正
			if (end2 >= n && begin2 < n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
				tmp[index++] = a[begin1++];
			while (begin2 <= end2)
				tmp[index++] = a[begin2++];
		}
		memcpy(a, tmp, n * sizeof(int) );
		gap *= 2;
	}
	free(tmp);
}

归并排序的特性总结

归并的缺点在于需要O(N)的空间复杂度，归并排序更多是解决磁盘外排序的问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

计数排序

计数偶爱徐又称为鸽巢原理，是对哈希直接地址法的应用变形。

操作步骤：

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

计数排序分绝对路径和相对路径，本身计数排序对空间的利用率就特别底，绝对路径较相对路径浪费率更高。

所以较为优秀的排序自然就是相对路径下的计数排序。

操作步骤：

统计相同元素出现的个数。
根据统计的结构将序列会受到原来的序列中。


//计数排序
void CountSort(int* a, int n)
{
	//确定范围,找到最大值和最小值
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (max < a[i])
			max = i;
		if (min > a[i])
			min = i;
	}
	//计算需要开辟的空间
	int range = max - min + 1;
	int* countA = malloc(sizeof(int) * range);
	//初始化为0
	memset(countA, 0, sizeof(int) * range);
 
	//相对路径
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
			a[j++] = i + min;
	}
}