数据结构详解——排序
目录
- 排序的概念
- 常见的几种排序
- 直接插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 原版（霍尔发明）
- 挖坑法
- 前后指针法
- 非递归实现快速排序
- 快速排序的优化
- 顺序数组排序问题
- 随机选key
- 三数取中
- 小部分区间计算的优化
- 归并排序
- 递归实现
- 非递归实现
- 计数排序
- 常见排序的性能
- 时间复杂度
- 空间复杂度
- 稳定性
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
常见的几种排序
常见的几种排序按照类型分类如下：
直接插入排序
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
// 插入排序
void InsertSort(int* a, int n);
#include"Shell_sort.h"
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[i + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
直接插入排序的本质是将数组中的元素看作等待插入的元素，从第一个元素开始往后逐个插入，插入时从排序好的元素末端开始比较，这里为了讲清楚我假设我想要排从小到大数组，当我要排从小到大时，我就要从末端向前比较，比我大的数就将我位置上的数赋值为它，直到找到比我小的数，将与他比较之前比较的数的位置（他已经向后赋值了一次，所以就是有两个位置都为它，我们选它原来的位置，因为他比我们大）赋值为插入的数。tmp变量为要插入的数，end为要比较的元素的指示器，初始化为排好序的元素的末端，逐次递减。可能教的讲得比较难懂，我这里画了一张图。
希尔排序
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
// 希尔排序
void ShellSort(int* a, int n);
#include"Shell_sort.h"
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
for (int j = 0; j < n - gap; j++)
{
int end = j;
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，表示这次排序的间隔元素数量，之后将从第一个开始相隔gap个的元素视为一个数组进行插入排序，之后将从第二个开始相隔gap个的元素视为一个数组进行插入排序，直到第gap个元素。下面是单趟希尔排序的示意图。
如果我们按照从第一个元素到第gap个元素，每个元素走相隔gap的插入排序的单趟，那么应当是双层嵌套如下所示：
for (int j = 0; j < gap; ++j)
{
for (int i = j; i < n - 1; i += gap)
{
}
}
我在这单独列出来的理由是这两个for循环可以合并成一个for循环，仔细想想的话这两个循环遍历了除最后gap个元素（最后gap个元素是留给插排中的最后一个tmp用的）之外的所有元素，并且这些元素都只执行插排这个相同的操作，所以完全可以优化合并成：
for (int j = 0; j < n - gap; j++)
{
}
单趟间隔为gap的排序结束之后就要将gap变为更小的gap进行更为精细的排序，常见的gap缩小方式有好几种，本质大差不差，我选择将gap除以2。如此一来，通过一趟趟的单趟gap排序，gap不断除以2，最终gap会变成1，这时进行的就是普通的插入排序，但这时的数组已经极为接近有序，所以运算时间会大大减小，之后gap不符合条件，退出循环，函数结束，数组也就排序完成了。
选择排序
#define _CRT_SECURE_NO_WARNINGS 1
// 选择排序
void SelectSort(int* a, int n);
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int max = left;
int min = left;
for (int i = left; i <= right; ++i)
{
if (a[max] < a[i])
{
max = i;
continue;
}
if (a[min] > a[i])
{
min = i;
}
}
swap(&a[left++], &a[min]);
swap(&a[right--], &a[max]);
}
}
选择排序就是从左边第一个元素开始，将后面的元素与之比较，比他小就与之交换(按从大到小排)，之后是第二个元素，以此类推……我在此基础之上优化了一下，单趟同时找最大的和最小的数，为此设置了两个变量max和min。
堆排序
#define _CRT_SECURE_NO_WARNINGS 1
// 堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);
void swap(int* a, int* b)
{
int c = *a;
*a = *b;
*b = c;
}
void down(int* a, int n, int start)//向下调整算法
{
int parents = start;//or start = 0 -> child = parents * 2 + 1
int child = parents * 2;
while (child <= n)
{
if (child + 1 <= n && a[child - 1] < a[child])
{
++child;
}
if (a[child - 1] > a[parents - 1])
{
swap(&(a[child - 1]), &(a[parents - 1]));
parents = child;
child = parents * 2;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
int num = n / 2;
while (num)
{
down(a, n, num--);
}
int end = n;
while (end > 0)
{
swap(&a[--end], &a[0]);//数组序号本身就要减一位且交换完后也恰好要将end减一缩小范围保护交换完的元素
down(a, end, 1);
//--end;
}
}
堆排序就是利用堆来对数组进行排序的排序，对堆排序时离不开的就是向上或者向下调整算法，这里我们只需要用向下调整算法。首先我们要建堆（排顺序建大堆，排逆序建小堆），这时需要注意的是我们并不是从根结点向下调整，而是从最后一个有子节点的结点开始逐步递减，原因是从根结点向下调整，换上来的并不一定就是最小的数（小堆），只有从最下面一层层排上来才能保证堆有序。理解了原理后就非常简单了，先定义变量num表示向下调整的节点，初始化为n / 2(最后一个元素的父节点，也就是最后一个有节点的结点)，之后循环向下调整就行。建好堆之后我们将首尾元素交换，这样最大的元素就到了最下面，之后我们单独对换上来的首元素再次进行向下调整，注意调整传给向下调整算法的范围要减一，不然可能把换下去的最大数又换上来了，如此往复就完成了排序。
冒泡排序
#define _CRT_SECURE_NO_WARNINGS 1
// 冒泡排序
void BubbleSort(int* a, int n);
#define _CRT_SECURE_NO_WARNINGS 1
void swap(int* a, int* b)//交换算法
{
int ex = *a;
*a = *b;
*b = ex;
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
}
}
}
}
冒泡排序的原理是不断地从数组第一个元素开始，先比较第一和第二个元素，第一个元素大于第二个元素就交换，之后比较第二和第三，以此类推，最后最大的元素会来到数组的最末尾，像浮起来的泡泡一样，之后不断重复上述过程就完成了排序。
快速排序
#define _CRT_SECURE_NO_WARNINGS 1
// 快速排序递归实现
// 快速排序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);
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
--right;
while (left < right && a[left] <= a[keyi])
++left;
if (left = right)
break;
swap(&a[left], &a[right]);
}
swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int ret = PartSort3(a, left, right);
QuickSort(a, left, ret - 1);
QuickSort(a, ret + 1, right);
}
int PartSort2(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
while (left < right && a[right] > key)
--right;
a[left] = a[right];
while (left < right && a[left] < key)
++left;
a[right] = a[left];
}
a[left] = key;
return left;
}
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int curr = left + 1;
int prev = left;
while (curr <= right)
{
if (a[curr] < a[keyi])
{
++prev;
swap(&a[prev], &a[curr]);
}
++curr;
}
swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void QuickSortNonR(int* a, int left, int right)
{
if (left >= right)
return;
Stack* ptr = (Stack*)calloc(1, sizeof(Stack));
if (ptr == NULL)
{
perror("QuickSortNonR:calloc");
return;
}
Stack* tmp = ptr;
StackInit(tmp);
StackPush(tmp, right);
StackPush(tmp, left);
while (StackEmpty(tmp) != 1)
{
int begin = StackTop(tmp);
StackPop(tmp);
int end = StackTop(tmp);
StackPop(tmp);
int ret = PartSort3(a, begin, end);
if (ret + 1 < end)
{
StackPush(tmp, end);
StackPush(tmp, ret + 1);
}
if (begin < ret - 1)
{
StackPush(tmp, ret - 1);
StackPush(tmp, begin);
}
}
}
快速排序是这些算法中效率最高的排序算法，大致思路是通过选定key值来对数组中的其他数进行比较最后使得比key小的在左边，比key大的在右边（从大到小排），在对左边边和右半边再次进行如此操作，最后使数组有序。快速排序也有着不同的版本，虽然有着相同的思路，但实现方式各不相同。
原版（霍尔发明）
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
--right;
while (left < right && a[left] <= a[keyi])
++left;
if (left = right)
break;
swap(&a[left], &a[right]);
}
swap(&a[keyi], &a[left]);
keyi = left;
return keyi;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int ret = PartSort1(a, left, right);
QuickSort(a, left, ret - 1);
QuickSort(a, ret + 1, right);
}
原版实现的具体思路是传参left和right表示数组的最左边和最右边(如果是写成一个函数则还要定义一组变量begin和end，复制left和right，因为后面是要移动这些变量来交换数，并使他们最终相遇，然后还要使用原本的left和right来传参实现二路归并，我这里为了方便跑各种版本的快速排序，将这些版本不同的地方封装成了一个个函数，在原函数调用那些函数，传参过去使用后回来参数销毁不会影响原本的left和right，所以没有创建)，将left设置成key。(不要因为left初始是key认为没有比较的必要就将left向后移动一位，会出问题，比如right先动后，直接撞上了left，left此时位置上如果正好是大于key的数，与key交换的话就将大于key的数换到左边去了，这就出bug了)，之后right先向后移动寻找比key大的数，找到后停止移动；left再向前移动寻找比key小的数，找到后停止移动(要右边先动也是有说法的，因为left和right相遇无非两种情况，一种是left撞right，一种是right撞left。先说left撞right,因为right先动且right遇到比key小的数就停止等着交换left动完停止后交换，所以right位置上只会是比key小的数，left撞上后与key交换时是将比key小的数换到了左边，这是没问题的；之后是right撞left，因为right先动，动完left动，之后再交换，所以left要么是还在起点没动，此时left就是key，相遇交换没问题，要么是刚交换完的left，此时left位置上是比key小的数，相遇交换是也是没有问题的。如果left为key且还让left先动，情况就截然相反，所以不行)。之后交换left和right位置上的数。如此往复直到left和right相遇，之后交换left(或者right，毕竟两者现在相等)和key的位置，再将key的位置也赋值成left的位置。如此就完成单趟快速排序，之后因为key此时已经处在了他应该处在的位置上(比它大的都在它右边，比它小的都在它左边)，key的位置已经不用动了，我们将数组以key为界限分为左右两边(左右两边都不含key)，引用自己对左右两边再次进行单趟快排，形成二路归并，递归结束就完成了排序。
挖坑法
int PartSort2(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
while (left < right && a[right] > key)
--right;
a[left] = a[right];
while (left < right && a[left] < key)
++left;
a[right] = a[left];
}
a[left] = key;
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int ret = PartSort3(a, left, right);
QuickSort(a, left, ret - 1);
QuickSort(a, ret + 1, right);
}
挖坑法相较于原版理解起来更加的容易，它的具体实现思路是先将left设置成key，之后将key挖出来，形成一个坑，规定left和right谁有坑谁就不动，等left移动找大于key的元素或者right移动找小于key的元素来填坑，直到left和right相遇，相遇后将之前挖出来的key填到相遇的那个坑上。这种方法用挖坑的方式简单易懂的规避了原版会出现的难以理解的地方，比如left初始要和key一样都设置在开头，以及key在左一定要让右先动，方法本身在理解了原版后就很好实现了。
前后指针法
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int curr = left + 1;
int prev = left;
while (curr <= right)
{
if (a[curr] < a[keyi] && ++prev != curr)
{
swap(&a[prev], &a[curr]);
}
++curr;
}
swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int ret = PartSort3(a, left, right);
QuickSort(a, left, ret - 1);
QuickSort(a, ret + 1, right);
}
前后指针法虽然本质是快排，但实现思路已与上述两者有着较大不同，它的具体实现思路是定义两个指针prev和curr，依旧将key设置成最左边的元素，将prev设置成key的位置，curr指针为prev后一个。curr先动，如果遇到比key小的元素，先prev++，再交换prev和curr的位置，之后curr++。如果curr遇到比key大的元素，只让curr++。其实这样操作的目的就是让prev以及prev后面的元素都比key小，而prev到curr之间的元素都比key大。如此往复操作直到curr到达数组末尾，此时交换key和prev位置的数就完成了快排的单趟排序。
非递归实现快速排序
void QuickSortNonR(int* a, int left, int right)
{
if (left >= right)
return;
Stack* ptr = (Stack*)calloc(1, sizeof(Stack));
if (ptr == NULL)
{
perror("QuickSortNonR:calloc");
return;
}
Stack* tmp = ptr;
StackInit(tmp);
StackPush(tmp, right);
StackPush(tmp, left);
while (StackEmpty(tmp) != 1)
{
int begin = StackTop(tmp);
StackPop(tmp);
int end = StackTop(tmp);
StackPop(tmp);
int ret = PartSort3(a, begin, end);
if (ret + 1 < end)
{
StackPush(tmp, end);
StackPush(tmp, ret + 1);
}
if (begin < ret - 1)
{
StackPush(tmp, ret - 1);
StackPush(tmp, begin);
}
}
}
非递归实现递归函数，必然要使用循环，在此之上，快速排序一分为二，二分为四这种的类似于二叉树前序遍历的两路归并要如何实现是个难题，这里有个巧妙的方法就是使用栈。因为栈有着先进后出的特性，我们将最初的left和right入栈，每出栈一组left和right就将这组left和right分裂的两组left和right入栈，这样就保证了运算的永远是最新分裂的left和right，这样就模拟了类似二叉树前序遍历的递归效果。我按照思路引入栈，设置循环，先出栈，排序，再将分裂的两组left和right入栈，如此往复直到栈为空就完成了排序。
快速排序的优化
顺序数组排序问题
快速排序在对已经按顺序(或者逆序)排列好或者接近排列好的元素效率会变得非常差，因为每次从最左边选key,而顺序或者逆序时最左边的数过于靠边，排完序后会出现按key分裂时一边元素非常多，而另一边元素非常少甚至没有，理想快速排序效率高的原因就是每次将数组等分，因为指数爆炸，所以即使是很大的数分裂二三十次也能分完，如果每次都像这样极其不均等的分裂，对于较大的数组就会分裂几十万次甚至更多，极其耗费时间的同时由于函数递归不断地创建栈帧，会出现栈溢出的情况，这种情况是需要极力避免的。下面是一些常用的方法。
随机选key
顾名思义，随机选key就是在数组的左右边界范围内生成随机数，将其作为key。
int randi = left + (rand() % (right - left));
swap(&a[left], &a[randi]);//随机取key
这是直接写在函数内的版本，也可以单独封装成函数。
三数取中
我们选用数组的前中后元素，比较他们的大小，处于中间的数作为key。(对顺序函数特化，直接是理想效率)
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
swap(&a[left], &a[mid]);
}
else if(a[left] < a[right])
{
swap(&a[left], &a[right]);
}
}
else
{
if (a[right] < a[mid])
{
swap(&a[left], &a[mid]);
}
else if(a[right] < a[left])
{
swap(&a[left], &a[right]);
}
}//三数取中
小部分区间计算的优化
快速排序在计算到区间较小时就可以考虑不再使用快速排序了，因为快速排序归根结底还是要进行递归，对栈帧进行开辟的，如果此时的区间很小了，却还要不断二分直到最后分的只剩一个，这其实是很亏的。且学过二叉树的都知道，二叉树的一半的元素都在最后一层，仅仅对最后一层进行优化就可以减少一般的递归，这会对算法性能提升不少。所以我们让数组的左右区间小于10时就停止递归，改用插入排序直接进行排序。会使用插入排序的原因是插入排序不用递归且对有一定顺序的数组排序会减少运算。
if (n < 10)
{
InsertSort(a, right - left + 1);
return;
}
归并排序
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
#include<stdlib.h>
// 归并排序递归实现
void MergeSort(int* a, int n);
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
// 计数排序
void CountSort(int* a, int n);
#include"Merge_sort.h"
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[i + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void MergeSort(int* a, int n)
{
if (n < 10)
{
InsertSort(a, n);
return;
}
int* arr = (int*)calloc(n, sizeof(int));
if (arr == NULL)
{
perror("MergeSort:calloc");
return;
}
int left = 0;
int right = n / 2;
MergeSort(a + left, n / 2);
MergeSort(a + right, n - n / 2);
int i = 0;
while (left < n / 2 && right < n)
{
if (a[left] < a[right])
{
arr[i++] = a[left++];
}
else
{
arr[i++] = a[right++];
}
}
while (left < n / 2)
{
arr[i++] = a[left++];
}
while (right < n)
{
arr[i++] = a[right++];
}
for (int j = 0; j < n; ++j)
{
a[j] = arr[j];
}
free(arr);
arr = NULL;
}
void MergeSortNonR(int* a, int n)
{
int* arr = (int*)calloc(n, sizeof(int));
if (arr == NULL)
{
perror("MergeSortNonR:calloc");
}
int gap = 1;
while (gap <= n)//控制间隔
{
for (int i = 0; i < n; i += gap)//单趟
{
int num = 0;
int left = i + 0;
int leftend = i + gap / 2 - 1;
int right = i + gap / 2;
int rightend = i + gap - 1;
//printf("[%d, %d] [%d, %d]\n", left, leftend, right, rightend);//观察用
if (leftend < n - 1 && rightend > n - 1)
{
rightend = n - 1;
}
else if(leftend >= n - 1)
{
break;
}
while (left <= leftend && right <= rightend)//一个间隔内的比较
{
if (a[left] <= a[right])
{
arr[num++] = a[left++];
}
else
{
arr[num++] = a[right++];
}
}
while (left <= leftend)
{
arr[num++] = a[left++];
}
while (right <= rightend)
{
arr[num++] = a[right++];
}
memcpy(a + i, arr, num * sizeof(int));
}
gap *= 2;
}
free(arr);
arr = NULL;
}
void CountSort(int* a, int n)
{
int min = 0;
int max = 0;//千万别用地址，坑死人!
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int size = max - min + 1;
int* arr = (int*)calloc(1, sizeof(int) * size);
if (arr == NULL)
{
perror("CountSort:calloc");
return;
}
for (int i = 0; i < n; ++i)
{
++arr[a[i] - min];
}
int j = 0;
for (int i = 0; i < size; ++i)
{
int num = arr[i];
while (num > 0)
{
a[j++] = i + min;
--num;
}
}
free(arr);
arr = NULL;
}
递归实现
void MergeSort(int* a, int n)
{
if (n < 10)
{
InsertSort(a, n);
return;
}
int* arr = (int*)calloc(n, sizeof(int));
if (arr == NULL)
{
perror("MergeSort:calloc");
return;
}
int left = 0;
int right = n / 2;
MergeSort(a + left, n / 2);
MergeSort(a + right, n - n / 2);
int i = 0;
while (left < n / 2 && right < n)
{
if (a[left] < a[right])
{
arr[i++] = a[left++];
}
else
{
arr[i++] = a[right++];
}
}
while (left < n / 2)
{
arr[i++] = a[left++];
}
while (right < n)
{
arr[i++] = a[right++];
}
for (int j = 0; j < n; ++j)
{
a[j] = arr[j];
}
free(arr);
arr = NULL;
}
归并排序的原理是先将数组不断地二分至一个指定的最小单元，再对这些最小单元进行排序，再在两两合并时将这些小单元元素进行排序合并，最后排序完成。具体来说，首先我们要设置递归结束的条件，我们当然可以将数组二分成最小单元，直接对最小单元进行合并排序，但设置一个最小区间，在最小区间内进行插入排序会减少大量的函数递归。之后要创建一个数组，方便在小单元数组合并时进行排序。在创建变量left和right，将left初始化为数组开头，right初始化为数组正中间。以left和right为基准将数组一分为二，先引用自己对左右两半部分进行排序，之后再进行合并排序，这与二叉树的后序遍历类似。在进行合并排序时，由于左右两个部分都已经排好了序，所以我们从左右两部分的开头开始比较，谁小谁就先插入提前创建好的数组，之后++，如此循环往复，直到一方跑到了末尾就停止。之后由于一方跑到了末尾，另一方所剩的元素就可以直接顺次排入提前创建好的数组了。书写过程中运用了后置++先使用再++的特点优化了代码的书写，不易理解的话可以在运算完后再++。
非递归实现
void MergeSortNonR(int* a, int n)
{
int* arr = (int*)calloc(n, sizeof(int));
if (arr == NULL)
{
perror("MergeSortNonR:calloc");
}
int gap = 1;
while (gap <= n)//控制间隔
{
for (int i = 0; i < n; i += gap)//单趟
{
int num = 0;
int left = i + 0;
int leftend = i + gap / 2 - 1;
int right = i + gap / 2;
int rightend = i + gap - 1;
//printf("[%d, %d] [%d, %d]\n", left, leftend, right, rightend);//观察用
if (leftend < n - 1 && rightend > n - 1)
{
rightend = n - 1;
}
else if(leftend >= n - 1)
{
break;
}
while (left <= leftend && right <= rightend)//一个间隔内的比较
{
if (a[left] <= a[right])
{
arr[num++] = a[left++];
}
else
{
arr[num++] = a[right++];
}
}
while (left <= leftend)
{
arr[num++] = a[left++];
}
while (right <= rightend)
{
arr[num++] = a[right++];
}
memcpy(a + i, arr, num * sizeof(int));
}
gap *= 2;
}
free(arr);
arr = NULL;
}
非递归实现归并排序还是具有一定的难度的，对范围的把控是很有挑战性的。首先我们要明确自己的基本思路，对于归并排序来说，他最终会把数组切割成一个个小块，每个小块就是一个数，所以我们不妨从最后算起，将数组的每个元素看成一个个小块，两两配对进行合并排序，如此往上最后排序完成。具体来说，我们先创建一个gap，就是当前小块的大小，初始化成2因为是从最底下开始。给出一个for循环，遍历所有的小块，所以是+=gap。对于每个小块内，我们也要将其分成两部分，我们定义四个变量left、leftend、right、rightend，分别用来记录左区间的开头结尾和右区间的开头结尾，这是处于方便控制的缘故，笔者尝试过只设两个变量left和right，结果是不好控制区间导致bug频出调试调得我吐血，借鉴网上大佬思路后换成四个变量就好多了。之后我们要对合并过程中会出现特例做出相应的调整，这些特例都是前面的元素合并之后最后剩下的元素不足以合并成gap大小的小块所导致的。元素不足也要分为两种情况：一种是左半部分可以填满，而右半部分不行，这时将rightend改为数组末尾就行；一种是左半部分刚好填满或者填不满，此时右半部分压根没有，左半部分本身就是有序的，不用再排了，直接结束这次单趟进一层。后面一个间隔内的比较与递归实现时一摸一样，不做解释，最后说一下外层while循环的条件，因为即使gap与n相等也还是要进行最后一次合并排序，所以以gap / 2为判断条件，在最后一次合并排序之后再结束循环。
计数排序
void CountSort(int* a, int n)
{
int min = 0;
int max = 0;//千万别用地址，坑死人!
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int size = max - min + 1;
int* arr = (int*)calloc(1, sizeof(int) * size);
if (arr == NULL)
{
perror("CountSort:calloc");
return;
}
for (int i = 0; i < n; ++i)
{
++arr[a[i] - min];
}
int j = 0;
for (int i = 0; i < size; ++i)
{
int num = arr[i];
while (num > 0)
{
a[j++] = i + min;
--num;
}
}
free(arr);
arr = NULL;
}
计数排序的原理是额外创建一个数组记录原数组中各个元素的数目，最后根据记录数组的数据将原数组进行排序。具体来说我们先要定义两个变量max和min来记录数组的最大值与最小值，以此来确定创建的数组大小。这里就有两种数组创建方式：一种是绝对位置映射计数，即最大数为多大就创建多大的数组；一种是相对位置映射计数，即只创建最大值与最小值之间的区间范围内的数组。毫无疑问，相对位置映射更节省空间，且相对映射可以对包含负数的数组进行排序。我选择相对位置映射，创建好数组之后，就要对原数组的数据进行计数了，由于是相对位置，计数时要减去最小值。最后根据计数数组对原数组进行赋值，由于是相对位置映射，要注意加上最小值。对计数排序充分了解之后可以明白计数排序适合范围小数据集中的整形排序，不适合范围大数据分散的浮点数字符串排序。
常见排序的性能
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
时间复杂度
冒泡排序：冒泡排序最坏情况就是完整跑完排序，每个单趟选出最大的一个，跑n - 1次。其实是n还是n - 1都无所谓，终究是在n这个量级，时间复杂度算的是量级，不需要算的很精确，只要了解思想模拟运算的过程就行。冒泡排序的单趟由于要每次都剔除排好的最大数，会逐渐减少元素，但还是在n这个量级，所以最坏是O(n^2)，冒泡排序的最好情况是在特别优化后可以实现的，即加上一个判断条件第一个单趟跑完没有发生交换，即数组已经排好了顺序就停止排序，所以是O(n)，但这种情况过于理想，无实际意义。
简单选择排序：选择排序不论最坏还是最好都要跑完n量级的单趟，每次单趟都要比较n量级次，所以是O(n^2).
直接插入排序：直接插入最好情况是O(n)，但与冒泡不同的是，它在遇到已经排好顺序的数组是，每个单趟只运算一次就完成了，跑了n个单趟，所以是O(n)，一般情况还是n次单趟，每次单趟n个元素，时间复杂度为O(n^2)。
希尔排序:希尔排序的时间复杂度是不好估计的，具有很大的随机性，它的每个单趟都由之前单趟跑完后所让数组变得有序的程度所决定，可以知道的是，希尔最好情况就是遇到已经排好顺序的数组，因为希尔的排序还是用的插排，遇到有序时只用运算一次，最后跑的单趟数还是在n这个量级，所以是O(n)。最坏时就是每个gap单趟都计算完，n量级的单趟跑n量级的元素，时间复杂度为O(n^2)， 而最好和最坏都不会是一般情况，经过复杂的数学计算，希尔排序的平均时间复杂度大概是O(n^1.3)。
堆排序：堆排序需要交换n量级次元素，再分别对其进行向下调整排序，也就是n次单趟，每次单趟是logn，时间复杂度为O(nlogn)。
归并排序：归并排序把数组不断分割，我们可以将其看作一颗二叉树，这样的二叉树有logn层，每层都进行合并排序，量级是n，所以时间复杂度是nlogn。
快速排序：与归并类似，可以将其看作一棵二叉树，logn层，每层做n量级的运算，所以是nlogn。需要注意的是，当快速排序遇到特殊情况如顺序排序时，层数可以达到n量级，所以最差的时间复杂度是n^2。但这种情况是可以被优化的，所以平均时间复杂度还是nlogn。
空间复杂度
空间复杂度为O(1)的不做过多介绍，不用额外创建数组也不使用递归，空间复杂度就为O(1)。
归并排序：归并排序的空间复杂度来源于递归时压栈的数据和创建的临时数组，递归最多有logn层，而每次递归都要创建数组，空间复杂度就是logn+n,化简之后就是O(n)。
快速排序：快速排序也要递归，但不用和归并排序一样创建数组，所以理想情况下就是logn的时间复杂度，而最差情况递归了n层，空间复杂度就是n。
稳定性
冒泡排序：冒泡是稳定的，因为冒泡可以上两数比较相等时不交换来维持稳定性。
简单选择排序：选择排序再交换两数时无法控制min和max上的数的相对位置不发生变化，所以不稳定。
直接插入排序：插入排序可以控制两数在相等时不停止来保持稳定。
希尔排序:希尔的间隔排序完全无法控制相同数之间的相对位置，所以不稳定。
堆排序：堆排在建好队之后将数组变相转化成了二叉树，数组关系变成了二叉树的父子节点关系，相同数之间的相对位置无法保持，所以不稳定。
归并排序：归并可以通过在合并排序时让左半边(相对位置在前面的数)的数先进入数组来保持稳定性。
快速排序：快排的交换完全无法对交换数的相对位置进行控制，所以不行。