排序的概念

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

常见的排序算法

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤（除了最后一个）即可完成排序。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubbleSort(int* a, int n)
{
	assert(a);
	//外层循环走n-1次，因为最后一趟不需要比较
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		//每次外层循环能确定一个最大的数在正确的位置，所以只需要比较n-i次
		for (int j = 1; j < n - i; j++)
		{
			//比较相邻的两个元素，如果他们的顺序错误就把他们交换过来
			if (a[j-1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				flag = 1;
			}			
		}
		//如果走了一趟都没有交换说明已经有序
		if (flag == 0)
			break;
	}
}

选择排序

每一次从待排序的数据元素中选出最小和最大的一个元素，存放在序列的起始位置，在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素 。因为可能把相同的元素换到不同的位置，所以选择排序也是不稳定的。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	assert(a);

	int begin = 0, end = n - 1;
	while (begin < end)//迭代的过程中，n为奇数个数会相遇，偶数个会错过
	{
		int mini = begin;
		int 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重叠，那么上一步中就把max换走了，那么max就到了min的位置
		if (begin == maxi)
		{
			maxi = mini;
		}
		//结尾和最小交换
		Swap(&a[end], &a[maxi]);
        //迭代
		++begin;
		--end;
	}
}

插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列。即：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

每一次从待排序的数据元素中选出最小和最大的一个元素，存放在序列的起始位置，在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素 。最好的情况是接近有序；最坏的情况是逆序。

void InsertSort(int* a, int n)
{
	assert(a);
	//外层循环n-1次
	for (int i = 0; i < n - 1; ++i)
	{
		// [0,end]有序，把end+1位置的值插入，保持有序
		int end = i;		  //每次都要对end重新赋值
		int tmp = a[end + 1];  //tmp保存end+1位置的元素
		while (end >= 0)
		{
			//如果不满足条件就把前面的元素后移，直到数组起始位置
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//到这里就满足条件了，证明end前面的元素就是tmp应该存放的位置
		a[end + 1] = tmp;
	}
}

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：把待排序文件中所有记录分组，所有距离为Gap的分在同一组内，并对每一组内的记录进行排序。待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 预排序的时候，相同的数据可能分到了不同的组，所系希尔排序是不稳定的。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当 gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，就变为插入排序了，这样整体而言，可以达到优化的效果。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//gap = gap / 2;
		for (int i = 0; i < n - gap; ++i) //注意循环条件，当i=n-gap的时候，a[end+gap]越界
		{
			//类似插入排序，只不过把1换为了gap
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap; //这里不是--，而是-=gap
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据，需要注意的是排升序要建大堆，排降序建小堆。

为什么排升序要建大堆

  排升序时，如果建小堆， 最小的数已经在堆顶的位置上，但是除了堆顶以外，剩下的数都不是有序的，如果需要找出剩下的数中最小的数，需要重新建堆这样排序的时间复杂度太大，还不如直接遍历排序。所以需要建立大堆，堆顶是最大的数，然后同最后一个数交换，再把交换后的堆顶数向下调整，然后重复交换再向下调整新堆顶数，直到实现排序。

代码实现

#include<stdio.h>
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDwon(int* a, int size, int parent)
{
	assert(a);
	// 默认左孩子小
	int child = parent * 2 + 1;
	// 到叶子就是孩子不存在，孩子不存在就是child>=parent
	while (child < size)
	{
		// 选出左右孩子中小/大的那个
		// 避免越界访问
		if (child + 1 < size && 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)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}

	// 依次调整大的数据放到堆尾
	// O(N*logN)  总时间复杂度O(N*logN)+O(N)——>O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		//选出次大的
		AdjustDwon(a, end, 0);
		--end;
	}
}

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

hoare版本

选出一个key，一般为最左边的值。先让right先往左遍历寻找一个比key小的数字，找到后停下来，再让left向右遍历寻找一个比key大的数字，找到后把这两个数交换。以此类推，直到left和right相遇，再把这个相遇的位置的数字和key交换就完成了一趟快速排序。单趟排序完后能达到左边比key小，右边比key大。然后再把key的左边和右边作为一个局部的数组重复上面的步骤，直到每一个局部区间都是有序的，那么这个数组也就是有序的了。

void QuickSort(int* a, int begin, int end)
{
	// 区间不存在，或者只有一个值则不需要再处理
	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]);
	}

	// 如果左边先走，并与右边相遇，此时不能保证右边的值小于key，而在最后交换的时候产生bug
	// 即：右边先走，右边停下来的位置能保证相遇的位置比key都小
	Swap(&a[keyi], &a[left]);
	//keyi = left;使左边比key小，右边比key大
	keyi = left;
	
	//递归
	// [begin, keyi-1] keyi [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

挖坑法

首先选取左边第一个为key值形成第一个坑。右边先走，找到小于key的值，填入左边的坑位置中，该位置形成新的坑。左边找大于key的值，再填入右边的坑位中，该位置再形成新的坑。直到左右相遇，一定相遇再坑的位置处。单趟排序完后能达到左边比key小，右边比key大。然后再把key的左边和右边作为一个局部的数组重复上面的步骤，直到每一个局部区间都是有序的，那么这个数组也就是有序的了。

void QuickSort(int* a, int begin, int end)
{
	// 区间不存在，或者只有一个值则不需要再处理
	if (begin >= end)
	{
		return; //递归出口，整个过程非常类似二叉树的前序遍历
	}
	int key = PartSort(a,begin,end);
	//递归
	// [begin, keyi-1] keyi [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}
// 挖坑法
int PartSort(int* a, int begin, int end)
{
	int key = a[begin];
	int piti = begin;
	while (begin < end)
	{
		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[piti] = a[end];
		piti = end;
		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[piti] = a[begin];
		piti = begin;
	}
	a[piti] = key;
	return piti;
}

前后指针版本

先选定左边第一个为基准值key，同时设定left位置为prev，prev的后一个位置为cur，从a[cur]开始和key比较，如果a[cur]比key小，就先将prev++，再让a[cur]和a[prev]交换，然后cur++，如果a[cur]比key大，那么就不改变prev，也不用交换，只对cur++，以此类推，直到cur>right就结束，最后将a[prev]和a[cur]交换就完成了一趟快排。

void QuickSort(int* a, int begin, int end)
{
	// 区间不存在，或者只有一个值则不需要再处理
	if (begin >= end)
	{
		return; //递归出口，整个过程非常类似二叉树的前序遍历
	}
    // 当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差
    // 此时可以使用插排而不是快排
    // 还可以减少大量的递归次数，防止栈溢出
    if (end - begin > 10)
	{
		int keyi = PartSort3(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a+begin, end - begin + 1);
	}
}
// 前后指针法
int PartSort(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	// 加入三数取中的优化，因为选取的key值会影响快排的效率
	int midi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[midi]);
    
	while (cur <= end)//begin和end是闭区间，大于end才结束
	{ 
		// cur位置的之小于keyi位置值
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur; 
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

快速排序的非递归形式

// 递归大问题，极端场景下面，如果深度太深，会出现栈溢出
// 1、直接改循环 -- 比如斐波那契数列、归并排序
// 2、用数据结构栈模拟递归过程
// 栈里面的区间都会拿出来，单趟排序分割，子区间再入
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st)) //栈为空就不用入了
	{
        // 先出左再出右
		int left = StackTop(&st);
		StackPop(&st);
        
		int right = StackTop(&st);
		StackPop(&st);
        
		int keyi = PartSort(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
     
         // 先入左子区间和右子区间都无所谓
		if (keyi + 1 < right)
		{
             // 先入右再入左
			StackPush(&st, right);
			StackPush(&st,keyi + 1);
		}

		if (left < keyi - 1)
		{
             // 先入右再入左
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}

	StackDestroy(&st);
}

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题 。

递归版本

void _MergeSort(int* a, int begin, int end, int* tmp)
{
    //递归出口
	if (begin >= end)
		return;
	//算中间位置，将区间分为两段
	int mid = (begin + end) / 2;
    // [begin, mid] [mid+1, end] 分治递归，让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);
		
    // 类似二叉树的后序遍历
    // 归并 [begin, mid] [mid+1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
    // i表示区间的最开始
	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++];
	}
	// 把归并数据拷贝回原数组
	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)
	{
		printf("malloc fail
");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

非递归版本

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		printf("malloc fail
");
		exit(-1);
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [i,i+gap-1][i+gap, i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// end1越界或者begin2越界，则可以不归并了
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int m = end2 - begin1 + 1;
			int j = begin1;
			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)* m);
		}
		gap *= 2;
	}
	free(tmp);
}

计数排序

计数排序是对哈希直接定址法的变形应用，先统计相同元素出现次数，再根据统计的结果将序列回收到原来的序列中。计数排序的缺点是：如果是浮点数、字符串无法解决，另外如果数据范围大，空间复杂度很高。计数排序只适合数据范围集中且重复数据量很大的情况。

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	// 统计次数的数组，采用相对映射的方式
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int)*range);
	if (count == NULL)
	{
		printf("malloc fail
");
		exit(-1);
	}
	memset(count, 0, sizeof(int)*range);

	// 统计次数
	for (int i = 0; i < n; ++i)
	{
        // 相对于最小值储存出现的次数
		count[a[i] - min]++;
	}

	// 按照出现的次数写回原数组
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		// 出现几次就会回写几个i+min
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

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

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