数据结构（七大排序）
前言
前话：排序在我们日常中很常见，但在不同的场合我们需要选择不同的排序，因为每个排序都有不同的使用场景，不同的时间复杂度和空间复杂度；常见的排序分为七种， 插入排序、选择排序、交换排序和归并排序；如下图可见：
1. 插入排序
1.1 直接插入排序
用end每次记录有序的数组位置，然后用temp记录end+1的位置，然后把temp插入有序的数组里，temp小于end位置的数据的话，则让end的数据往前挪一个位置，然后end--往后走，一直走到end位置的数据大于temp的时候，则让temp插入到end+1的位置处，单说有点难理解，我们来看图和代码，如下图和代码所示：
void InserSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int temp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > temp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = temp;
}
}特性总结：
1. 数组越有序，那么直接插入排序的效率越高；
2. 时间复杂度：O(N^2)
3. 空间复杂度为：O(1)
1.2 希尔排序
希尔排序就是对直接插入排序的完善，因为如果说数组完全没有序的话，直接插入排序的时间复杂度会为O(N^2)，但上面可以知道，数组越有序，直接插入排序的效率就越高，那么我们就可以对数组进行一个预排序，这样数组就没有那么乱，算是部分有序了，实现的思路就是：先选定⼀个整数（通常是gap = n/3+1），把待排序的数组所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进行排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。
如上图可见，gap = 3的时候就是每隔3个数据进行排序，如上就是下标为0和下标为3的数据进行排序，如果arr[0]>arr[3]那就让他们交换，然后再对arr[1]和arr[4]进行排序；如下图
最后当gap = gap / 3+1 = 1的时候就是直接插入排序了，但这会数组内的元素近似有序，那直接插入排序的效率就会变高了不少，代码实现如下所示：
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > temp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = temp;
}
}
}希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化；
2. 当gap>1的时候都是预排序，目的是让数组接近有序。当gap == 1的时候，数组已经接近有序了，而gap==1的时候直接把1代入代码发现其实就是直接插入排序；
3. 希尔排序的时间复杂度为O(N^1.3)；
2. 选择排序
选择排序的基本思想：其实就是选出最小和最大的值放到数组的最左边和最右边，直到全部待排序的数据元素排完即可；
2.1 直接选择排序
直接选择排序的思路：定义一个begin和end，再定义一个maxi和min位置begin的下标位置，然后遍历数组，找到最大的值就让max走到最大值下标处，找到最小的值就让min走到下标位置处遍历完之后直接交换max的值到begin处，min的值到end处；总结一句话：大的值放右边，小的值放左边，如下代码所示：
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int max = begin;
int min = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] > arr[max])
{
max = i;
}
if (arr[i] < arr[min])
{
min = i;
}
}
if (max == begin)
{
max = min;
}
Swap(&arr[begin], &arr[min]);
Swap(&arr[end], &arr[max]);
++begin;
--end;
}
}注意上面多了一段if(max==begin)的代码，原因是如果max在begin的位置会发生交换错误，这里给个图展示：
如果说直接交换begin和min的话是可以，但是再走到end和max交换的时候就会发生错误，会让最小值2走到end的位置处；
直接选择排序特性总结：
1. 直接选择排序很好理解，但是效率不好，很少使用；
2. 时间复杂度为O(N^2);
3. 空间复杂度为O(1)；
2.2 堆排序
小堆排序，首位交换，小的到最下面了然后再对堆顶元素进行向下调整，然后--end，再首位交换，一直循环到end<=0的时候，小数据就全部在后面，大数据就全部在前面得到一个降序的数组；如果想得到一个升序的则用大堆排序；如下代码所示：
void AdjustDown(int* arr, int parent,int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* arr, int n)
{
//建堆
//升序--大堆
//降序--小堆
向上建堆
//for (int i = 0; i < n; i++)
//{
// AdjustUp(arr, i);
//}
//向下建堆得从最下面开始建起
//因为向下调整必须他下面就是一个堆
//那么就从传入的数据开始，传入的i就是child
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
//i就是最后一个孩子的父母
AdjustDown(arr, i, n);
}
//建完堆后
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}堆排序的特性总结：
1. 时间复杂度为：O(nlogn)
2. 空间复杂度为：O（1）
3. 交换排序
3.1 冒泡排序
冒泡排序其实就是让相邻的两个数比较大小，如果左边比右边的大则交换，一直循环到最后就肯定把大的交换到最后的位置去，那最大的交换到最右边之后就不需要排那一个位置了，所以第二次遍历的时候就不需要遍历那一个已经排序过的位置了；如下图可见：
void BubbleSort(int* a, int n)
{
int exchange = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
exchange = 1;
Swap(&a[j], &a[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}这里加了个exchange的原因是，首先让其遍历一遍，如果说需要比较的话就让exchange = 1，这样就代表数组不是完全有序的，如果不写一个exchange的话数组有序还要两个循环走一遍，给一个有序的数组还要走一遍没有意义；
冒泡排序的特性总结：
1. 时间复杂度为：O(N^2);
2. 空间复杂度为：O(1);
3. 复杂度为N^2的时候很好实现，就是当排序是排升序的时候给一个已经排好降序的数组他进行排序，反之；这样就可以达到复杂度为N^2的时候了；
3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序法，其基本思想为：取一个基准值key，定义最左边的元素为begin，最右边的元素为end，然后再把数组从[begin，key-1]和[key+1, end] 分为左子序列和右子序列并且，左子序列的数是小于key值的， 右子序列是大于key值的，但这并不是说一定是有序的，只不过是大于key的值在右子序列，小于key的值在左子序列然后左右子序列接着重复这个过程直到所有元素都排到相应的位置为止
快速排序的框架：
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _QuickSort(arr, left, right);
//遍历左边找基准值
QuickSort(arr, left, keyi - 1);
//遍历右边找基准值
QuickSort(arr, keyi + 1, right);
}3.2.1 霍尔版本
首先说明left是数组内下标为0的位置，right是数组内下标为n-1的位置；然后定义一个key 位于left的位置上，begin 位于left的位置，end位于right的位置上，然后让end从右边往左边走找小于arr[key]的值，让begin从左往右走找大于arr[key]的值，如果找到了就让begin和end位置上的值交换，这样小于key的值就在左边，大于key的值就在右边了，但我们还要控制begin和end的走向，不可能让他们一直走，我们知道不可能让left>right的时候还继续走，但是等于需要我们讨论一下；我们先不讨论，我们先上个图看一下他是怎么走的，后面再来细致介绍一些需要等于号的地方；
void HoreSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
/
if ((right - left + 1) < 10)
{
InserSort(arr + left, right - left + 1);
}
else
{
//三数取中，找最左边和左右边还有中间的比较
int mid = GetMid(arr, left, right);
Swap(&arr[left], &arr[mid]);
int key = left;
int begin = left, end = right;
/
while (begin < end)
{
//end先走，end找小
while (begin < end && arr[end] >= arr[key])
{
--end;
}
//begin走， begin找大
while (begin < end && arr[begin] <= arr[key])
{
++begin;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[key], &arr[begin]);
key = begin;
HoreSort(arr, left, key - 1);
HoreSort(arr, key + 1, right);
}
}
最后的递归代码就是实现下图的操作，画的可能有点丑hhh：
由此看出其实就是和二叉树一样，所以上面的介绍提到二叉树结构；上图在“ / ”外的就是我解释的部分，在里面的是对这个快排进行优化，我们就先假装没看到。
1. 首先是第一个while循环需不需要等于号，答案是不需要。当begin走到end的位置时直接和key的位置的数据交换即可；
2. 可能有的人会想着说相遇的位置直接和key位置上的交换的话，那如果出现相遇位置的数据大于key位置上的数据怎么办，那是不是就让大于key的数据走到左边了？这时候只需要我们先让右边走就行，会出现下图的两种情况：
这个如果实在想不明白可以画一个图来看一下首先是L遇R的情况：
R遇L的情况：
无论怎么走最后相遇的值都肯定是小于key的，这也就是这个结构的魅力所在；
3. 第二个while循环（begin < end && arr[end] >= arr[key]）的begin<end是必须要加的，因为如果说数组内全部都是相同的数的时候，那可能end就直接遍历到最左边begin的位置了，会造成越界；
优化霍尔版本排序
（1）三数取中
三数取中顾名思义就是在最左边的数和左右边的数还有中间的数中取三者的中间值，这个是避免选到的key是最小值且在begin处，end要遍历完整个数组才找到的情况，然后取到中间值再让他换到最左边，这样我们下面的代码就不需要修改了，定义代码如下：
int GetMid(int* arr, int left, int right)
{
int midi = (left + right) / 2;
if (arr[left] < arr[midi])
{
if (arr[left] < arr[right])
{
return midi;
}
else if (arr[left] < arr[right])
{
return right;
}
else
{
return left;
}
}
else
{
if (arr[midi] > arr[right])
{
return midi;
}
else if (arr[left] < arr[right])
{
return left;
}
else
{
return right;
}
}
}（2）小区间优化
这个就是怕递归的层数太深，当right-left+1小于10的时候，也就是说里面的元素不超过11个的时候就调用直接插入排序；
if ((right - left + 1) < 10)
{
InserSort(arr + left, right - left + 1);
}快速排序特性总结：
1、时间复杂度为：O（nlogn）
2、空间复杂度为：O（logn）
3.2.2 双指针法
双指针法的具体思路其实和霍尔的快排一样，只不过是找key值的方法不同；具体实现是：定义两个指针一个prev指向left 一个cur指向prev+1处，让cur遍历整个数组，如果说cur处的值小于key处的值，那么++prev，然后交换prev和cur处的值，然后cur++，如果说cur处的值大于key处的值，则让cur++;如下图和代码所示：
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = QuickSortPrevPointer(arr, left, right);
//遍历左边找基准值
QuickSort(arr, left, keyi - 1);
//遍历右边找基准值
QuickSort(arr, keyi + 1, right);
}
int QuickSortPrevPointer(int* arr, int left, int right)
{
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
//原版
if (arr[cur] < arr[keyi])
{
++prev;
Swap(&arr[cur], &arr[prev]);
cur++;
}
else
{
cur++;
}
//化简版
//if (arr[cur] < arr[keyi] && ++prev != cur)
//{
// ++prev
// Swap(&arr[cur], &arr[prev]);
//}
//cur++;
}
Swap(&arr[prev], &arr[keyi]);
return prev;
}3.2.3 非递归版快排
说着非递归其实就是借助别的东西来模拟递归排序。实现非递归版快排就需要借助栈来实现，这里是按区间来入栈然后取出来进行排序；实现思路：首先把left和right入栈，但我们需要注意入栈的顺序，因为堆是先入后出的结构，入完数据后再取出来begin = 取出的第一个数据也就是left， end = right， 然后调用上面写过的找key值的代码，然后再把[begin, key-1]和[key+1, end]入栈，到时候取出来的begin和end就是[begin, key-1]这个区间，然后再找key值，其实这和递归的思路类似；如下图和代码所示：
栈的实现的代码可以去前面的博客找这里就不放出来了；
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = QuickSortPrevPointer(arr, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi+1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi-1);
StackPush(&st, begin);
}
}
STDestory(&st);
}
4. 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divide and Conquer）的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核步骤：
4.1递归版
void _MergeSort(int* arr, int* temp, int begin, int end)
{
//这个就是递归到只剩下最后一个数的时候，
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
//这里就要一直递归二分直到只剩一个数据为止
//[begin, mid][mid+1, end];
_MergeSort(arr, temp, begin, mid);
_MergeSort(arr, temp, mid+1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[i++] = arr[begin1++];
}
else
{
temp[i++] = arr[begin2++];
}
}
//给数据给到最后肯定还有一个数组不为空的
while (begin1 <= end1)
{
temp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = arr[begin2++];
}
memcpy(arr + begin, temp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* arr, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail!");
return;
}
_MergeSort(arr, temp, 0, n - 1);
free(temp);
temp = NULL;
}归并排序特性总结：
1、时间复杂度为：O（nlogn）
2、空间复杂度为：O（N）
4.2 非递归版归并排序
非递归版其实也就是想办法去模拟递归，递归版的是一直递归到有序的时候，也就是只有一个数的数组时候，然后比较两个数组内的元素大小排序放入temp数组里，然后归并再比较，直到最后一个数组都被比较完然后放入temp数组里结束；非递归版我们可以通过循环来模拟实现，
如下代码所示：
//非递归版归并排序
void MergeSortNonR(int* arr, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail!");
return;
}
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;
//有两种会越界的情况，
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
temp[j++] = arr[begin1++];
}
else
{
temp[j++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = arr[begin2++];
}
memcpy(arr + i, temp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(temp);
temp = NULL;
}这里上面有两种越界情况，
第一种就是begin2>=n的时候，也就类似8个元素的数组被分为了两个范围[0, 7][8, 15]这种我们就没必要再循环下去了，因为[0,7]的数据已经被排完放在temp数组里了，所以直接break；
第二种就是[0, 4][5,9]，这个是end2也就是9越界了，那就让end2等于数组内最后一个元素的下标也就是n-1 ，那就成了[0, 4][5, 7]再归并即可；
5. 非比较排序（计数排序）
其实就是拿一个数组来进行对应位置的映射，举个例子，比如说arr数组内存的是待排序的元素， 我再创建一个数组叫count， 例如arr数组内的元素是：4，3，5，2，1，4，6，2，那么我们就在count数组那对应的下标处++，例如1出现了一次，那就在下标为1处++一次，4出现了两次就在count下标为4处++两次，2出现了两次就在count下标为2处++两次，就达到了记录出现次数的效果，然后再把count内的元素按从左往右的顺序打印数据，如果下标为2处的元素为2那就打印两次2，就按着这个规律，这里就有点像哈希表一样，对应的数据映射到另一个数组里记录；如下代码所示：
void CountSort(int* arr, int n)
{
int min = arr[0], max = arr[0];
//遍历数组找到他们的差值，因为这里其实就是用到哈希表的映射概念
// 例如1 4 6 3 8 9 待排序，那就直接映射到下标去， 而且我们要开数组有内最大元素的空间
// 例如9，要映射到8处去，那就需要开0~8的空间
// 但是出现100 101 102的话不可能开100个空间，我们就会进行相对映射，就是让每个值都减掉数组内最小的元素
// 例如109 ， 109 - 100就放到第9个位置处，100就放到第0个位置处
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc fail!");
return;
}
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
free(count);
}
计数排序的特性总结：
1. 计数排序适合在数据范围集中处使用
2. 时间复杂度为：O（N+range）
3. 空间复杂度为：O（range）
排序复杂度及稳定性
稳定性就是说待排序数组中arr｛(1)2、4、9、3、(2)2、1、5｝中(1)2如果在排完序后是在(2)2的后面，说明相对位置发生变化，那就意味着这个排序不稳定；
END！