Lesson6–排序

---

一、.排序的概念及其应用

1.1排序的概念

  排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录 的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
  内部排序：数据元素全部放在内存中的排序。
  外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2常见的排序算法

各种排序的接口：

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)

在这里给大家附一个力扣的链接，这个题目可以跑上述的任意排序：力扣oj链接

二、.常见排序算法的实现

2.1插入排序

2.1.1插入排序的基本思想：

  直接插入排序是一种简单的插入排序法，其基本思想是：
  把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
  举一个形象的例子：打扑克牌，每发一张牌我们都要把他按照顺序插入到指定的位置，到最后发牌结束你的牌就会有序。

2.1.2直接插入排序：

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

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2) （最坏的情况，每个元素都要向后移动n次）
3. 空间复杂度：O(1)
4. 稳定性：稳定，它是一种稳定的排序算法
   分析一下两种情况：
   最好的情况：
   顺序有序（接近顺序有序）：每插入一个元素都是当前最大的元素直接插在末尾，时间复杂度 是O(n).
   最坏的情况：
   逆序：每插入一个元素都是当前最小的，之前的元素都要向后移动一位，一共需要插入n个元素，所以这n个元素每个都要向后移动n次，所以时间复杂度是O(n^2)

2.1.3 直接插入排序代码实现

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; ++i) //这里i<n-1是因为从0开始所以最大是n-1，//这里i表示插入前的最后一个元素的下标，如果i=n-1，//那么插入一个新的元素放入变量tmp中就越界了{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;}
}

2.1.4希尔排序（缩小增量排序）

  希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数放在gap内，把待排序文件中所有记录分成多个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定
   
   4.稳定性：不稳定
   其实我们可以把希尔排序看成是插入排序的一种优化算法：
   插入排序我们每插入一个数就要将他与前面的数进行比较排序，效率很慢。
   在这里我们的希尔排序可以划分为两部分：
   1.预排序
   将要排的序列按照我们指定的gap来分组，然后每个小组内先进行排序，gap不断变小， gap>1都属于预排序
   2.插入排序
   当gap等于1时我们就可以看作是插入排序

2.1.5希尔排序代码实现：

void ShellSort(int* a, int n)
{/*int gap = 3;for (int j = 0; j < gap; ++j){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;}else{break;}}a[end + gap] = tmp;}}*/

// gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){// gap = gap / 2; gap = gap / 3 + 1;for (int i = 0; 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;}else{break;}}a[end + gap] = tmp;}}
}

我们来分析一下希尔排序的代码：

2.2选择排序

2.2.1基本思想

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

2.2.2堆排序

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

2.2.3堆排序代码实现

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 确认child指向大的那个孩子if (child + 1 < n && a[child + 1] > a[child]){++child;}// 1、孩子大于父亲，交换，继续向下调整// 2、孩子小于父亲，则调整结束if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
// O(N*logN)
void HeapSort(int* a, int n)
{// 向下调整建堆 -- O(N)// 升序：建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O（N*logN）int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

2.2.4直接选择排序

1.在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3.在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

2.2.5直接选择排序代码实现：

// O(N^2)
// 跟直接插入排序比较，谁更好 -- 插入
// 插入适应性很强，对于有序，局部有序，都能效率提升，也就是说插入排序有的情况下效率会大幅度提升
// 但是直接选择排序任何情况都是O(N^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]);if (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);++begin;--end;}
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.3.交换排序

2.3.1基本思想

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

2.3.2冒泡排序

2.3.3冒泡排序代码实现

// O(N^2)
// 插入  选择  冒泡
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; ++j){int exchange = 0;for (int i = 1; i < n-j; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理if (exchange == 0){break;}}
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

2.3.4快速排序

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

2.3.5 hore版本快速排序

  对于hore版本的快速排序，就是我们先选定最左边的一个值作为key，然后让最右边的指针先向左走，找比ket小的值，找到了就停止，然后让左边的指针向右走，找比key大的值，找到了就停下，当两个指针都停下的时候我们交换两个位置的值，然后继续右边先走，停下后左边再走，最终两个相遇的位置和key交换，这个情况下我们就可以保证key的位置时正确的，并且key左边的所有元素都比key小，右边的所有元素都比key大，然后我们就可以把区间分为三个部分，一个部分是key左边的部分，一个部分是 key，另外一个部分是key右边的部分，我们继续对于左右两个部分重复操作，类似递归，最终划分成一个个细小的有序的区间，最终成功排序。

2.3.6hore代码实现

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

2.3.7三数取中法

  我们发现快速排序对于一些有序的情况处理的效率会非常的低，比如我们要排序的序列本身就是有序的，我们取到最左边的数作为key，每次都有一个指针从头走到尾，也就是找一个数需要遍历n次。n个数排好序就需要n^2次，效率很低，所以我们要控制不能取到最大或者最小这种特别极端的情况，所以我们采用三数取中的办法，也就是最左边的数，最右边的数和中间的数，我们比较它们三个的大小，取大小最中间的那个数作为我们的key值，这样就可以尽可能地避免最坏的情况的出现。

2.3.8三数取中代码实现

// 三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] > a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}

  通过三数取中的优化，快速排序基本不会出现最坏的情况，由最坏的算法变成了最好的算法，时间复杂度可以达到O(n*logn)

2.3.9三数取中后hore代码实现

int PartSort1(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);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[left], &a[keyi]);keyi = left;return keyi;
}

2.3.10小区间优化

2.3.11小区间优化后的代码

//void QuickSort(int* a, int begin, int end)
//{
//	if (begin >= end)
//	{
//		return;
//	}
//
//	if ((end - begin + 1) < 15)
//	{
//		// 小区间用直接插入替代，减少递归调用次数
//		InsertSort(a+begin, end - begin + 1);
//	}
//	else
//	{
//		int mid = GetMidIndex(a, begin, end);
//		Swap(&a[begin], &a[mid]);
//
//		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[left], &a[keyi]);
//		keyi = left;
//
//		// [begin, keyi-1]  keyi [keyi+1, end]
//		QuickSort(a, begin, keyi - 1);
//		QuickSort(a, keyi + 1, end);
//	}
//}

2.3.12挖坑法快速排序

2.3.13挖坑法快速排序代码实现

int PartSort2(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = a[left];int hole = left;while (left < right){// 右边找小，填到左边坑里面while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边找大，填到右边坑里面while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

2.3.14前后指针版本

实现的思路就是cur找比key小的，找到后停下来然后++prev，然后交换prev和cur位置的值。

代码实现：

int PartSort3(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int keyi = begin;int prev = begin, cur = begin + 1;while (cur <= end){// 找到比key小的值时，跟++prev位置交换，小的往前翻，大的往后翻if (a[cur] < a[keyi] && ++prev != cur)//++prev！=cur是为了避免一种特殊的情况：cur本身指向的数比key小，//++prev就指向了和cur同一个位置，//这个位置交换没有意义而且还会有开销，所以这样就可以避免Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

2.3.15快速排序非递归实现

代码实现如下：

void QuickSortNonR(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);int key = PartSort3(a, left, right);if (key+1 <right)    //这里判断key右边的区间是否还需要继续入栈{Stackpush(&st, key + 1);Stackpush(&st, right);}if (key - 1 > left) //这里判断key左边的区间是否还需要继续入栈{StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st);
}

2.4归并排序

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

我们先从基础的来看一下什么是归并排序：

  就是找出中点然后分成左右两个区间，让着两个区间都有序，然后比较两个有序的区间元素，谁小就将谁尾插进去，最终就完成了排序。
  但是我们要面临的第一个问题就是怎么让左右区间变得有序呢？
  我们这里采用分治的思想，分而治之，同时我们之前学了二叉树的和快速排序，我们就有了一个思想就是递归，我们的做法就是将大的区间不断地划分，划分成一个个很小的区间，然后对他们进行处理，最终递归的结果就是左右区间都会变得有序，我们就可以采用双路归并的方法完成归并排序。
  但是我们要注意的一点就是我们需要借助一个临时数组tmp，我们从原数组中取出数据然后在tmp中完成排序，完成之后就将tmp数组中完成排序的部分拷贝进入原数组，然后继续从原数组中读取数据，完成一个小的排序就拷贝回去。
代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
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;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (begin1 < 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, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

这样就完成了归并排序的递归实现，那么它的时间复杂度和空间复杂度是多少呢？
归并排序递归实现
时间复杂度：O(N*logN)
空间复杂度：O(N) 创建了tmp数组
  我们都知道递归的话需要建立函数的栈帧，建立栈帧就会有消耗，比如快速排序我们就将递归的算法进一步改进变成了用栈实现的非递归实现，那么我们这个归并排序是否可以采用非递归实现呢？如果可以采用非递归实现那么我们该使用什么样的数据结构才可以做到呢？
首先要说明的是我们不能用栈去实现归并排序的非递归。
我们已经有了递归的思想作为铺垫，就是需要将大区间划分为一个个小区间处理，那么我们采用逆向思维，是不是可以利用循环控制每个比较区间的大小从小区间到大区间排序呢？

  我们定义一个变量rangeN，让rangeN先从1开始取值，意思就是我们每个区间内只有一个元素，然后两个区间进行归并排序，就得到了一个有序的区间，然后我们每次改变rangeN的大小，就可以完成所有元素的归并排序。
  但是我们非递归的实现难点在于如何处理数组越界的问题，比如下图：

  这里就可以明显看出我们的begin2和end2越界了，我们的下标是0~9，但是这里出现了10和11，所以这才是我们应该考虑的难点问题。那么只有begin2和end2有越界的风险吗？
  我们打印出来每个归并的区间来看看那几个变量可能越界：

  我们发现begin1是不可能出现越界的这种情况的，但是end1，begin2和end2是都可能会出现越界导致程序崩溃的，所以我们分为三种情况来进行分析处理：
1，end1，begin2和end2同时越界

2.begin2和end2越界

3.end2越界

对于上述三种情况我们有两个处理的办法：

2.4.1 修正区间法

  第一种就是修正区间，最后一个区间会出现越界我们就单独修正该区间，避免出现越界的情况。
  对于第一种情况，end1，begin2和end2同时越界，我们做出以下修正：

if (end1 >= n){end1 = n - 1;// 不存在区间begin2 = n;end2 = n - 1;}

  也就是将end1改成最后一个元素，然后begin2到end2这个区间改成一个不存在即不合法的区间。然后begin1到end1这个区间就没有进行归并排序，直接将数组拷贝进入tmp数组，我们将前面的区间在tmp数组中完成归并然后整体拷贝回原数组中即可完成有序。
对于第二种情况，begin2和end2越界，我们只需要将这个区间修正成一个不存在的空间即可。

if (begin2 >= n){// 不存在区间begin2 = n;end2 = n - 1;}

对于第三种情况，即end2越界，这个时候我们就将end2改成最后一个元素即可。

if (end2 >= n){end2 = n - 1;}

代码实现：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并int rangeN = 1;while (rangeN < n){for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);int j = i;// end1 begin2 end2 越界// 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝if (end1 >= n){end1 = n - 1;// 不存在区间begin2 = n;end2 = n - 1;}else if (begin2 >= n){// 不存在区间begin2 = n;end2 = n - 1;}else if (end2 >= n){end2 = n - 1;}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, tmp, sizeof(int)*(n));rangeN *= 2;}free(tmp);tmp = NULL;
}

2.4.2 break法

  第二种方法就是出现越界这种情况直接break跳出循环。
  代码如下：

  end1 begin2 end2 越界if (end1 >= n){break;}else if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}

  这个方法我们是归并一部分拷贝一部分，我们一旦出现越界就break结束循环，合理的区间放在tmp中去归并但是不存在的区间我们就还是放在原来的数组里面，我们将tmp中排好序的元素拷贝回原来的数组即可完成排序。

#define _CRT_SECURE_NO_WARNINGS
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并int rangeN = 1;while (rangeN < n){for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);int j = i;// end1 begin2 end2 越界if (end1 >= n){break;}else if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}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)*(end2 - i + 1));}rangeN *= 2;}free(tmp);tmp = NULL;
}

三、总结

  本篇博客针对排序的算法首先分为四大类：插入排序，选择排序，交换排序，归并排序，对每一类排序的思想都进行了说明，同时每一类排序下又细化出很多排序，如直接插入排序，希尔排序，快速排序等等，这些算法都有动图演示和画图思路详解，还附有每种算法的源代码实现，最重要的知识点快速排序的非递归实现和归并排序的非递归实现放在最后面详细讲解，有了前面各种算法思想的铺垫对于后面实现非递归也有一定的帮助，希望可以帮助到大家~ 接下来会持续跟新博客，分享自己的心得，欢迎大家交流~