排序（9.17）

1.排序的概念及其运用

1.1排序的概念

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

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

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

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

1.2排序运用

把待排序的目标按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

（假设原数组为当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行（逆序）比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移

简单实现：先实现单趟排序，也就是插入一个值，将它与原数组的值依次相比较，找到合适的位置插入；再实现整体排序，也就是从空数组开始插入，到插满数组，插入依次就单趟排序一次，次数为 n 次。

插入时，用一个指针指向要比较的数组成员（从数组尾开始），如果数组成员大于要插入的数，就将该数组成员向后移动一位，如果直到指针走到-1要插入的数都是最小的，就将数插入到数组头，如果中途遇到了小于要插入的数的数组成员，就插入到该数后面。

//直接插入排序
void InsertSort(int* a, int n)
{
	//完整排序
	for (int i = 0; i < n - 1; i++)
	{
		//单趟排序
		int end=i;
		//将待插入数据保存下来
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
 
			}
			else
			{
				break;
			}
			end--;
		}
		//走到这里有两种情况
		//1.end走到-1都没找到比tmp大的值
		//2.找到了比tmp小的值
		a[end + 1] = tmp;
		//单趟
	}
}
int main()
{
	int arr[] = { 5,8,6,7,3,1,9 };
	InsertSort(arr,7);
 
	return 0;
}

gap>1的时候都是预排序，gap==1就是插入排序

希尔排序中预排序的意义是：大的数更快跳到后面去，小的数更快跳到前面来（常规的排序需要一个个挪动，效率低）。gap越大，越不接近有序，gap越小，越接近有序，gap==1,直接变有序。

简单实现：

//希尔排序
void ShellSort(int* a, int n)
{
	//数据间距
	int gap = n;
	while (gap >= 1)
	{ 
		//间隔每次缩小一半
		gap = gap / 2;
		//整个排序
		//gap由大到小最终实现完全有序
		for (int j = 0; j < gap; j++)
		{
			//一趟排序（将间隔为gap的一组数据排序）
			for (int i = j; i < n - gap; i += gap)
			{
				//单次排序
				int end = i;
				//保存下一个（待比较的数据）
				int tmp = a[end + gap];
				while (end >= 0)
				{
					//如果右小于左
					if (tmp < a[end])
					{
						//右边的就等于左边的
						a[end + gap] = a[end];
						//end左移一个gap，以便于给左赋值
						end -= gap;
					}
					else
					{
						break;
					}
				}
				//走到这里有两种情况
				// 1.end为负
				// 2.end左移之后，a[end]<tmp
				//给左赋值
				a[end + gap] = tmp;
				//完成一次排序，一组内的两个数变成左小右大
			}
		}
	}
}

用一个函数来测试对同一个数组进行不同种类的排序的时间花费

// 测试排序的性能（时间）对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	//开辟6个数组空间
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		//给六个数组赋相同值
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	//记录排序开始时间（ms）
	int begin1 = clock();
	InsertSort(a1, N);
	//记录排序结束时间（ms）
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	/*SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();*/
	//相减即为排序花费时间
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	/*printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);*/
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

比较直接插入排序和希尔排序

容易发现两者的差距是巨大的，说明希尔排序的效率更高。

顺便回顾一下之前的排序并比较它们的性能差异

冒泡排序：

//冒泡排序
void BubbleSort(int* a,int n)
{
	//整趟
	for (size_t i = 0; i < n; i++)
	{
		int exchange = 0;
		//一趟
		for (size_t j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				exchange = 1;
			}
		}
        //如果一趟排序结束后一次交换都没有发生，说明数组有序
		if (exchange == 0)
		{
			break;
		}
	}
}

再比较一下它们的效率：

显而易见冒泡排序表现是最差的。

希尔排序的特点：

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度 不好计算，因为 gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定， 大致为n^1.3，略逊于n*log n

堆排序：

//数据向下调整（找较小的孩子往上推）
void AdjustDown(int* a, int n, int parent)
{
	//假设较小孩子为左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		//如果右孩子更小
		//child+1必须小于n，否则当child=n-1,child+1就越界
		if (child + 1 < n && a[child + 1] < a[child])
		{
			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)
{
	向上调整建堆
	// //O(N*logN)
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}
 
	//向下调整建堆
	// //O(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;
	}
}

2.2 选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置/结束位置（最左边/最右边），直到全部待排序的 数据元素排完 。

简单实现：

//选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n-1;
	//整趟排序
	while (begin < end)
	{
		//一趟排序
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			//找最小的
			if (a[i] < a[mini])
			{
				mini = i;
			}
			//找最大的
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//将最小值交换到数组头
		Swap(&a[begin], &a[mini]);
		//如果最大值在开头，数值会被当成begin的值交换走
		//我们需要让maxi跟随最大值
		if (maxi == begin)
		{
			maxi = mini;
		}
		//将最大值交换到数组尾
		Swap(&a[end], &a[maxi]);
		//一趟循环结束缩小一次范围
		begin++;
		end--;
	}
}

 比较一下以上排序的效率：

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

 2.3.2 快速排序

思路为： 任取待排序元素序列中 的某元素作为基准值（一般取数组头元素），按照该排序码将待排序集合分割成左右两子序列，左子序列中所有元素均 小于 基准值，右 子序列中所有元素均 大于 基准值，然后在左右子序列重复该过程（可用递归实现），直到所有元素都排列在相应位置上为止 。

2.3.2.1霍尔法

先将第一个数据存放在临时下标 key 位置的值中，形成一个坑位

该排序由许多趟排序组成，一趟排序完成将一个数放到其相应位置。其他趟为对左右子数递归组重复这个过程；一趟排序中，先从数组尾开始遍历比目标数小的，找到之后在从数组头开始遍历比目标数大的，找到之后交换，最终使得数组的左边都小于目标数，右边都大于目标数，当左右遍历到同意位置时结束遍历，将此位置的值与key位置的值交换，一个数就完成了排序。

单趟排序过程如图

递归过程如图

//快速排序单趟
int PartQuick(int* a,int left,int right)
{
	//记录第一个数下标作为目标位
	int key = left;
	while (left < right)
	{
		//找小
		while(a[right] >= a[key] && left < right)
		{
			right--;
		}
		//找大
		while(a[left] <= a[key] && left < right)
		{
			left++;
		}
	    //找到左右后调整使小在左，大在右
		Swap(&a[left], &a[right]);
	}
	//将目标位放置到合适位置
	Swap(&a[key], &a[left]);
	return left;
}
 
//快速排序
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	//将中间位找出来
	int key = PartQuick(a, begin, end);
	//分别对左右区间递归
	QuickSort(a,begin, key-1);
	QuickSort(a,key+1, end);
}

对比一下效率较高的几个排序，容易发现快速排序依然领先。

排序存在的疑问：如何保证单趟排序中相遇位置的值是小于key位值的？

情况1：R动L不动，R去相遇L，L和R在上一轮交换过，交换后L位置的值一定比R位置的值小

情况2：L动R不动，L去相遇R,R先走，找小找到了，停下来，L找大找不到根R相遇，相遇点的值比key小。

快速排序的时间复杂度：

最好的情况：

key刚好为中位数，时间复杂度为N*logN

最坏的情况：

数列增序且key为最小数，R找小直接从尾找到头，遇到L并交换（自己和自己交换），就完成了本趟排序，然后递归右子数列一直重复此过程（左子数列为空），时间复杂度为N^2

如何避免这样的情况发生呢？

我们需要尽量让下标key的成员值为中位数而非最小值，这里可以采用三数取中的方法，取出有序数列中间位置的值作为key坑位值，即可让有序数列情况下的的时间复杂度接近理想情况

//三数取中(中指中位数）
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
 
	if (a[left] < a[mid])
	{
		//mid为中位数
		if (a[mid] < a[right])
		{
			return mid;
		}
		//left为中位数
		else if (a[left] > a[right])
		{
			return left;
		}
		//right为中位数
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		//mid为中位数
		if (a[mid] > a[right])
		{
			return mid;
		}
		//left为中位数
		else if (a[left] < a[right]) 
		{
			return left;
		}
		//right为中位数
		else
		{
			return right;
		}
	}
}

此时来比较一下有序数列下和希尔排序的时间复杂度，容易看出三数取中让有序数列下的快速排序的时间复杂度有了质的飞跃，在采用了三数取中的优化以后，有序数列情况下不会再出现最坏情况。

2.3.2.2挖坑法

先将第一个数据存在临时变量key中，形成一个坑位，然后从右开始找小于key的位置，找到小于key的就将其填到坑位中，然后该位置形成新的坑位，再从左边找大，以此类推。

//快速排序挖坑法单趟
int PartQuickDig(int* a, int left, int right)
{
	//找出中位数的下标
	int mid = GetMid(a, left, right);
	//将中位数交换到数列头作为key
	Swap(&a[left], &a[mid]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//找小
		while (a[right] >= key && left < right)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//找大
		while (a[left] <= key && left < right)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

整趟排序

单趟排序一次找出一个已经排序好的位置，然后对其左右数组进行递归，直到完全排序。

//快速排序
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	//将已经放置合适的位置找出来
	// 霍尔
	//int key = PartQuick(a, begin, end);
	//挖坑
	int key = PartQuickDig(a, begin, end);
 
	//分别对左右区间递归
	QuickSort(a,begin, key-1);
	QuickSort(a,key+1, end);
}

挖坑法可以算作希尔法的小优化，不用思考为什么要先从右边开始找小。

2.3.2.3前后指针法

思路：用临时变量 key 保存数组第一个值，一前一后指针从头开始，cur 指针在前面找大于 key 的值，在找到之前，prev紧跟cur，找到一个大之后，prev 停下等待 cur 找完连续的大，然后从大后面第一个开始交换 cur 和prev 的数组值（大的到后面，小的到前面），交换一次 cur 和prev 向前移动一次，直到大交换完毕，cur 继续往前走找大。最后交换 key 和 prev 的数组值，返回 prev，即完成了单趟排序，对左右子数组递归即可完成排序。

//快速排序前后指针单趟
int PartQuickPointer(int* a, int left, int right)
{
	int key = left;
	int prev = left, cur = prev + 1;
	while (cur<=right)
	{
		//找大
		if (a[cur] < a[key])
		{
			//prev仅在cur小于key的时候++
			//如果此时prev和cur相邻，++后相等
			prev++;
			//如果prev和cur相等，相当于没交换
			//如果不相等，就将小于key的换到前面，大于key的换到后面
			Swap(&a[prev], &a[cur]);
		}
		//无论cur比key大还是小，均要++
		cur++;
	}
	//key和它的值挪到prev
	Swap(&a[key], &a[prev]);
	return prev;
}

对快速排序的优化：

当待排序的数为10个及以下时，使用递归排序将会造成资源浪费，造成效率的下降，因此在快速排序时，当待排序数为10个以下时，改用直接插入排序。

//快速排序
void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	//待排序数大于10用递归
	if (end - begin + 1 > 10)
	{
		//将已经放置合适的位置找出来
		// 霍尔
		//int key = PartQuickHoare(a, begin, end);
		//挖坑
		//int key = PartQuickDig(a, begin, end);
		//前后指针
		int key = PartQuickPointer(a, begin, end);
 
		//分别对左右区间递归
		QuickSort(a, begin, key - 1);
		QuickSort(a, key + 1, end);
	}
	//小于10个用直接插入排序
	else
	{
		InsertSort(a+begin,end-begin+1);
	}
}

优化前后效率对比：可以看出优化之后的效率是有小幅提升的。

非递归快排： 

学习了使用递归的排序方法后，我们也有必要掌握非递归的排序方法，因为递归算法所使用的空间是在栈区上开辟的，而栈区的空间是有限的，如果递归数据过多，就会造成栈溢出；而非递归算法使用的空间是在堆区上开辟的，就不存在这个问题。这里运用栈来实现非递归，但还是运用递归的思想。

//非递归快排
void QuickSortNonR(int* a, int begin, int end)
{
	//栈声明
	ST st;
	//栈初始化
	STInit(&st);
	//先入尾再入头（栈后进先出，以便出的时候先出头再出尾）
	STPush(&st, end);
	STPush(&st, begin);
 
	while (!STEmpty(&st))
	{
		//获取头
		int left = STTop(&st);
		//获取一个出一次
		STPop(&st);
		//
		int right = STTop(&st);
		STPop(&st);
		//将一个值排序到合适位置
		int key = PartQuickHoare(a, left, right);
		//入尾和头，向左右数组区间“递归”
		//左区间
		if (key + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, key + 1);
		}
		//右区间
		if (left < key - 1)
		{
			STPush(&st, key-1);
			STPush(&st, left);
		}
	}
	//销毁栈
	STDestroy(&st);
}

2.4 归并排序

基本思想： 类似于树的后序遍历

归并排序 （ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并（取同位置较小的数依次尾插到新数组），得到完全有序的序列； 如果子序列无序 ，即先使每个子序列有序（递归并分割左右子序列到最小区间（1和1归并），使子数列一定有序），再使子序列段间有序。将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

在分割子序列的过程中，不用每次都开辟新的空间来存放这个序列，而是在原数组上通过控制下标来实现对子序列的操作（分割和归并），这里额外用一个函数来实现。归并的时候再用新开辟的空间用来存放归并的结果（如果在原数组上归并，会覆盖原数据），每次归并完将结果拷贝到原数组，就完成了对原数组的归并排序。

递归实现：

//子序列递归归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	//序列只剩一个数返回
	if (end <= begin)
	{
		return;
	}
	//找出中界限
	int mid = (begin + end) / 2;
	//递归左右子序列
	//类似后序遍历的思想：先左，后右，再根
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
	//归并到tmp
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	//定义一个下标管理tmp数组
	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, (end - begin + 1) * sizeof(int));
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	_MergeSort(a,tmp,0,n-1);
}

递归展开图：

非递归实现：

与递归不同的是非递归用一个 gap 来控制每轮归并数据的个数。gap为几，就为几个数据和几个数据归并，到新申请的数组空间，归并一次，gap就翻倍一次，从开始的 1 1 归并到最后 n/2|n/2 归并。每轮归并内，用一个 for 循环来控制进度 ，每完成一组（两个区间）归并，就往后移动 gap*2 位。

但是这种方法仅适用于需要递归的目标数组的成员为 二的次方倍数个（因为数据的归并为两两（组）归并），如果不满足，就可能造成如图的两种越界。

测试一下9个数数列（下标0-8）归并的范围，就容易看出 end1, begin2, end2 越界了

此时就需要分情况处理越界：

如果是 end1 越界，那么这一组就没必要归并了；

如果是 begin2 越界，同样这一组不需要归并；

而 begin2 越界，end1必定越界，因此可以将它们归为一类；

如果是 end2 越界，那么这一组就变成了 [begin1,end1]，[begin1] 的归并，需要修正右边的边界。

 

一组归并完毕后将其拷贝到数组 tmp。

需要注意将拷贝放在循环内，归并一组，拷贝一组，这样未归并的数据就不会被拷贝

memcpy(a + i, tmp + i, ( end2 - i + 1 ) * sizeof(int));

//子序列归并排序(非递归）
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 += gap * 2)
		{
			//归并到tmp
			// [begin1,end1],[begin2,end2]
			//  gap个数据      gap个数据
			//第一个区间
			int begin1 = i, end1 = i + gap - 1;
			//第二个区间
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			//定义一个下标管理tmp数组
			int index = i;
			//判断溢出的情况分别处理
			//1.第一组的尾越界或二组的头越界（第二组不存在）
			//这一组就不用归并了
			if (begin2 >= n)
			{
				break;
			}
			//2.第二组的尾溢出
			if (end2 >= 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 + i, tmp + i, (end2-i+1) * sizeof(int));
		}
		//归并每组的个数翻倍
		gap *= 2;
	}
	free(tmp);
}

归并排序的特性总结：

1. 归并的缺点在于需要 O(N) 的空间复杂度(额外开辟数组），归并排序的思考更多的是解决在磁盘中的外排序问题。

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

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

4. 稳定性：稳定

3 常见排序算法复杂度及稳定性分析

稳定性的意义

相同的数在数组中排序前后，相对位置是否发生变化，不变为稳，变则不稳。

例如：

考试排名取前三，先交卷的成绩先进入数组

记忆的时候切忌背结论，而是要搞清楚不同排序的原理，明白为什么不稳。

希尔排序之前先分组进行预排序，预排序中相同的数可能分到不同的组，导致相对位置发生改变。

选择排序将最小值交换到最左边，出现如图情况两个3的相对次序发生改变

堆排序一调整相对次序就变乱了

快速排序当 key 位为5时，多个5的前后次序发生改变。