这个小节来介绍一下下面几种常见常用的排序算法。
快排和归并排还会介绍一下他们的非递归实现。
开始前的准备由于部分排序需要涉及到交换元素，为了简洁代码，就可以把交换部分独立成一个函数。
void Swap(int* x1, int* x2)
{
int tmp = *x1;
*x1 = *x2;
*x2 = tmp;
}
我以前是很喜欢用 ^ 这种运算符来交换的，但是 ^ 有一个问题。如果是自己和自己交换，那自己就会变成0。
这是个坑啊。我当初调试了半天，都不知道为什么。所以如果是题目明确要求不允许创建中间变量，最好还是用创见中间变量的方法。
1. 插入排序 1.1 直接插入排序 1.1.1 思想直接插入排序这种思想其实在打扑克牌的时候有用到。
当插入第i个元素时，前面的arr[0],arr[1]......arr[i-1]都是有序的，只需要从最后一个开始，不断往前比较即可。我做了个动图，可以很简单的去理解这个过程。
1.1.2 代码实现插入排序的代码实现就是比较简单的，只需要去不断与前面比较即可，如果是升序，当遇到比他小的或到了前面边界时即可停下。
void InsertSort(int* a, int n)
{
assert(a);
// 从第一个开始 一个元素可以认为是有序的
for (int i = 0; i < n - 1; i++) // 注意这里的边界需要控制好
{
if (a[i + 1] < a[i])
{
for (int j = i; j >= 0 && a[j] > a[j + 1];j--)
Swap(a + j, a + j + 1);
}
}
}
1.1.3 直接插入排序的特性
1. 如果元素是比较接近于有序的，那么直接插入排序是非常快的。
2.时间复杂度为O(N²)。
3.空间复杂度为O(1)。
1.2 希尔排序 1.2.1 思想希尔排序是对直接插入排序的一种优化，希尔排序法又称为缩小增量法。他的思想是，先给定一个整数gap，把所有距离为这个整数的数单独分组，然后让所有的组单独进行插入排序。接着把这个整数减下，持续到1，重复上面操作。
那你可能就会问了，这算哪门子优化，最后一步还不是直接插入排序。
你还记得上面提到的吗，当数组比较趋近于有序时，插入排序是很快的。所以前面这些东西就是为了让数组趋近于有序，希尔排序整体是比直接插入排序快很多的。
1.2.2 代码实现void ShellSort(int* a, int n)
{
// 当 gap > 1 预排序
// 当gap == 1 直接插入排序
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1; // 保证最后一个gap一定为1
for (int i = 0; i < n - gap; i++)
{
// 对每个 begin 和 begin + gap 进行对比
// 这里是通过不断地改变 begin 来实现分组插入排序的
int begin = i;
int tmp = a[begin + gap];
while (begin >= 0)
{
if (tmp < a[begin])
{
a[begin + gap] = a[begin];
begin -= gap;
}
else
{
break;
}
}
a[begin + gap] = tmp;
}
}
}
1.2.3 希尔排序的特性
1.希尔排序是对直接插入排序的一种优化。
2.希尔排序的整体速度比直接插入要快很多。
3.希尔排序在面对海量数据排序时，表现比较优秀。
4.希尔排序的时间复杂度很难分析，Knuth进行了大量分析，得出结果是，O(n^1.25) ~ O(1.6 * n^1.25)。
5.希尔排序的空间复杂度为O(1)。
2.选择排序 2.1 直接选择排序 2.1.1 思想直接选择排序的思想是很好理解的，他就是从第一个开始，去寻找最小或最大的那个，然后放在开头/结尾，不断地重复即可。
我做了一个动图，可以很方便地了解选择排序的思想。
2.1.2 代码实现// 选择排序
void SelectSort(int* a, int n)
{
assert(a);
int maxi = 0;
for (int i = n; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (a[j] > a[maxi])
{
maxi = j;
}
}
Swap(a + maxi, a + i - 1);
maxi = 0;
}
}
2.1.3 选择排序的特性
1.选择排序的思想非常好理解，但是在实际中很少用到。
2.选择排序的时间复杂度为O(N²)。
3.选择排序的空间复杂度为O(1)。
2.2 堆排序堆排序其实在之前的博客中有讲到，这里就不重复了。
链接:学习C/C++系列（5）二叉树的顺序存储及堆排序_roseisbule的博客-CSDN博客
2.2.3 堆排序的特性1.堆排序是一个很快的算法，但是在面对海量数据时，略微有点力不从心。
2.堆排序的时间复杂度为:O(N*logN)。
3.堆排序的空间复杂度为:O(1)。
3.交换排序 3.1 冒泡排序 3.1.1 思想冒泡排序我叫他blueblue排序，是我学的第一个排序算法，当时觉得冒泡排序很厉害，现在就......。
但是如果不专心的话，可能也不能一次性写好冒泡。
冒泡的思想就是重复比较，从而每一次冒泡都把最大/最小的放在最后面。
一图顶千言，我做了下面这张动图，可以很简单地了解冒泡的思想。
3.1.2 代码实现// 冒泡排序
void BubbleSort(int* a, int n)
{
assert(a);
for (int j = 0; j < n; j++)
{
int flag = 1;
for (int i = 0; i < n - j - 1; i++)
{
if (a[i] > a[i + 1])
{
Swap(a + i, a + i + 1);
flag = 0;
}
}
if (flag)
{
return;
}
}
}
这里对冒泡进行了一点点优化，就是当一趟下来，没有发生交换，说明数组已经有序，就不需要再排了，但是这种优化太有限了，只有完全有序才起到作用。并不会像插入那样，只要趋近于有序，速度就很快。
3.1.3 冒泡排序的特性1.很容易理解，所以经常是初学者学到的第一个排序算法。
2.冒泡排序的时间复杂度为O(N²)。
3.冒泡排序的空间复杂度为O(1)。
4.很慢很慢很慢。
那是不是说交换排序都很low呢？不是的，快速排序也是交换排序的一种，但是很强的。
3.2 快速排序快速排序目前有三个版本，分别为:hoare版本,挖坑法,前后指针法。
逐个来讲哈。
3.2.1 hoare版快速排序hoare其实就是快排的发明者，他发明的那个版本被叫做hoare版。那hoare版快排是怎么操作的呢？看下面这个动图。
其实hoare快排就是任取待排序元素序列中的某元素作为基准值(一般选取最左边的元素，然后从右边开始)，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
就是保证key的左边都是小于他的，key的右边都是大于他的。那么key的位置就不会再变化，然后分治，把左端到key的区间和右端到key的区间继续快排。
代码实现:
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
assert(a);
if (left >= right)
return 0;
int key = left;
int tmp = right;
while (left < right)
{
while (left < right && a[right] >= a[key])
right--;
while (left < right && a[left] <= a[key])
left++;
Swap(a + left, a + right);
}
Swap(a + key, a + left);
return left;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >= right)
return;
int tmp = PartSort1(a, left, right);
QuickSort(a, left, tmp - 1);
QuickSort(a, tmp + 1, right);
}
3.2.2 挖坑法快排
我们通过下面这个动图来观察hoare方法和挖坑法的区别。
挖坑法，就是把key的位置变成一个坑，把key的值单独保存。从右边开始，当值小于key时，便把这个值放到坑里，然后把自己变成一个坑。接着从左边开始。重复这个过程。注意，如果是在左边挖坑，那就从右边开始，如果是在右边挖坑，就从左边开始。
代码实现:
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
assert(a);
int key = a[left];
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[keyi] = a[right];
keyi = right;
while (left < right && a[left] <= key)
{
left++;
}
a[keyi] = a[left] ;
keyi = left;
}
a[keyi] = key;
return keyi;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >= right)
return;
int tmp = PartSort2(a, left, right);
QuickSort(a, left, tmp - 1);
QuickSort(a, tmp + 1, right);
}
3.2.3 前后指针法快排
前后指针法是最新的快排优化方法，名字还没定，就叫前后指针法。
观看如下动图，我们可以看出前后指针法与前面两个方法的差别。
其实前后指针法，就是pre和cur一前一后两个指针，当cur的值小于key时，则把pre++，然后和cur交换，接着cur++。当cur的值大于key时，则只把cur++。当cur超出了边界时，则把key和pre交换一下。
代码实现:
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
assert(a);
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && a[++prev] != a[cur])
Swap(a + prev, a + cur);
cur++;
}
Swap(a + prev, a + keyi);
return prev;
}
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >= right)
return;
int tmp = PartSort2(a, left, right);
QuickSort(a, left, tmp - 1);
QuickSort(a, tmp + 1, right);
}
3.2.4 快排的非递归实现
为什么快排要区分非递归和递归呢？
我们知道，一个函数的调用是要压栈的，而一个栈一般只有8M左右。如果我要把一个倒序的数组排成升序，可以想象这需要调用非常多次快排函数，如果数组很大，那就会栈溢出。而非递归则没有这个危险。
既然要把递归设计成非递归，那应该是要用到循环来模拟递归。我用一块空间把访问区间的左右端给记录起来。其实这有点像前序遍历。先排序好自身区间，然后去排序右子区间和左子区间。那我们就可以用一个栈来保存这些访问顺序。
因为栈是后进先出，假设现在在访问一个区间[left,right]。那么我们把[left,key-1],[key+1,right]压入栈中，这样如果你在访问完这个区间后接着去访问下一个区间的话，就只能取出[key+1,right],也就是右子区间，而当你访问完右子区间时，你又只能去访问右子区间的右子区间。那你可能会问，左子区间呢？左子区间在这个时候根本就不会访问到，因为你最后压入栈的是右子区间的右子区间，你只能访问你取出来的区间，也就是你只能访问右子区间的右子区间。这样就是达到了递归的效果。很奇妙，对吧。
代码实现:
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
assert(a);
Stack ST;
StackInit(&ST);
StackPush(&ST, left);
StackPush(&ST, right);
while (!StackEmpty(&ST))
{
right = StackTop(&ST);
StackPop(&ST);
left = StackTop(&ST);
StackPop(&ST);
if (left >= right)
continue;
int key = PartSort3(a, left, right);
StackPush(&ST, left);
StackPush(&ST, key - 1);
StackPush(&ST, key + 1);
StackPush(&ST, right);
}
StackDestroy(&ST);
}
3.2.5 快排的三数取中优化
三数取中优化是什么？
在上面的非递归中，我们说到，如果我要把一个倒序的数组排成升序，可以想象这需要调用非常多次快排函数，如果数组很大，那就会栈溢出。这是很危险的。那有没有一种不用非递归也能解决的办法呢？有的，就是三数取中。我们来分析一下为什么会出现栈溢出，主要是区间的左边和右边就是区间的最大值和最小值，所以出现这种情况。那么如果，我不把key放在区间的最左边和最右边。而是在这个区间内部找一个点，让他和最左边和最右边的值比较一下，取介于中间的值作为key不就能解决问题了吗。
代码实现(以hoare快排为例):
int PartSort1(int* a, int left, int right)
{
assert(a);
if (left >= right)
return 0;
int midi = FindOneInThree(a, left, right);
Swap(a + midi, a + left);
int key = left;
int tmp = right;
while (left < right)
{
while (left < right && a[right] >= a[key])
right--;
while (left < right && a[left] <= a[key])
left++;
Swap(a + left, a + right);
}
Swap(a + key, a + left);
return left;
}
3.2.6 小子区间的优化
我们看这个快排呀，其实他调用函数就和树的分布一样，越小的区间调用的函数就越多，对栈的开销也就越大。那可不可以对这个问题进行优化呢？可以的，我们可以当区间很小的时候，使用别的排序方法，比如插入排序，来优化快排。
代码实现:
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >= right)
return;
if (right - left + 1 > 5)
{
InsertSort(a + left, right - left + 1);
}
else
{
int tmp = PartSort1(a, left, right);
QuickSort(a, left, tmp - 1);
QuickSort(a, tmp + 1, right);
}
}
4.归并排序
4.1 递归版归并排序
4.1.1 思想
归并排序的思想还得从两个有序数组合并开始讲起。
是这样的，如果有两个有序数组，那么合成一个有序数组就是很简单的，只需要把两个数组都遍历一遍即可。如下面我做的动图。
那么如果能把需要排序的数组变成两个有序的数组合并问题，那么排序不就很简单了吗？那如何变成两个有序的数组呢？这又是一个分治的问题。那分治的尽头是什么呢？就是这个数组只有一个元素了，那就可以直接认为有序。
归并排序的思想如下面动图。
4.1.2 代码实现void CombineTwoArray(int* a,int begin1,int end1,int begin2,int end2,int* tmp)
{
assert(a && tmp);
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++];
}
}
void _MergeSort(int* a, int begin,int end,int* tmp)
{
assert(a);
if (begin >= end)
return;
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1 , end, tmp);
CombineTwoArray(a, begin, mid, mid + 1, end, tmp);
//printf("Merge : [%d,%d] [%d,%d]n", begin, mid, mid + 1 , end);
if (mid == 4)
{
int num = 0;
}
memmove(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("Malloc Fail In MergeSort!n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
}
4.1.3 归并排序的特性
1.归并排序的唯一缺点就是O(N*logN)的时间复杂度，归并排序十分适合排序磁盘中的文件。
2.归并排序的时间复杂度为:O(N)
4.2 非递归归并排序 4.2.1 思想上面讲到了递归实现归并排序，其实非递归也是可以实现的。有两中思想，一种是完全按照上面的不断分割，往下循环，一种是从最底层开始，不断扩大，往上循环。这里讲第二种。
首先对于一个如下的数组，先假设已经被分为一个一个的小数组，每个数组只有一个元素，那每个数组都可以看出是有序的。然后我们两个两个的把他们合并为大一点的数组，每个数组都有2个元素。然后我们接着把这些数组合并，合并为4个元素的数组，接着不断往上进行此操作，直到只剩下一个数组，这个数组就是有序的。
这样看起来好像是可以的，但是我们来思考这样一个问题，如果数组个数不是2的次方数呢？
像下面这个。
如果强行配对，这就会越界。那我们来分析有几种越界情况。
我们给出下面数组的坐标，便于分析。
1.begin1会不会越界？ 这个我们应该分析不到，如果begin1越界，说明这里两个数组不存在，不需要合并，之前的end就已经到了数据的末尾，已经结束了配对，不会配对到这里来。
2.end1会不会越界？ 这个是可能的。
像上图，当前面的数据都已经分好了之后，最后一个不够凑一个数组了，就会出现这种情况，那这种情况怎么办呢？那我们就可以让 end1 赋值为这个末尾，让 begin2 和 end2 变成一对特殊下标，这对下标表示的数组不存在(begin2 > end2)。这样前面的那个数组就是在和一个空数组合并，得到的还是前面那个数组。这样就用为这种特殊情况单独写一个合并。
3.begin2会不会越界？很显然，这是有可能的。那么像我们之前分析begin1越界的情况，既然begin2越界了，而end1又没有越界，说明了end1就是数据末尾，我们就可以直接让后面这个数组不存在，即begin2 > end2。这样又是一个数组与空数组合并。
4.end2会不会越界？很有可能，而且概率很大。但是这种情况很简单，和前面的end1越界是一模一样，直接让end2赋值为数据末尾即可。
好了，越界情况我们已经分析完了。
4.2.2 代码实现// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("Malloc Fail In MergeSortNonRn");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int begin2 = i + gap;
int end1 = i + gap - 1;
int end2 = i + gap * 2 - 1;
int num = end2;
// 1.end1 越界
// 2.begin2 越界
// 3.end2 越界
if (end1 >= n)
{
end1 = n - 1;
begin2 = 1;
end2 = 0;
num = n - 1;
}
else if (begin2 >= n)
{
begin2 = 1;
end2 = 0;
num = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
num = n - 1;
}
CombineTwoArray(a, begin1, end1, begin2, end2, tmp);
memmove(a + begin1, tmp + begin1, sizeof(int) * (num - begin1 + 1));
}
gap *= 2;
}
}
4.2.3 非递归归并排序的特性
1.非递归，其实没有了爆栈的风险，比较安全。
2.非递归的时间复杂度为:O(N*logN)。
3.非递归的空间复杂度为:O(N)。
5.排序的比较 5.1 排序的综合比较这里解释一下稳定性是什么，稳定就是排序之后不改变之前被排序数据的相对位次。
比如下面这个数组
里面有两个相同的数，都是1，但是他们颜色不一样。那么在排序的过程中，有些算法，可能会无视这种颜色，可能在给出的结果中把红色的1反而放前面了。但是在原数据中，红色1是在蓝色1后面的。这就是不稳定的表现。
有一些地方，可能写希尔排序是稳定的，但是希尔排序其实不稳定，下面这个数组就是一个反例。
5.2 各排序实机测试这里我用我的电脑试一下上面所讲的排序算法。测试代码如下:
void test()
{
int num = 100000;
int* x = (int*)malloc(sizeof(int) * num);
int* x1 = (int*)malloc(sizeof(int) * num);
int* x2 = (int*)malloc(sizeof(int) * num);
int* x3 = (int*)malloc(sizeof(int) * num);
int* x4 = (int*)malloc(sizeof(int) * num);
int* x5 = (int*)malloc(sizeof(int) * num);
int* x6 = (int*)malloc(sizeof(int) * num);
assert(x && x1 && x2 && x3 && x4 && x5 && x6);
srand((unsigned)time(NULL));
for (int i = 0; i < num; i++)
{
x[i] = rand() % 100;
x1[i] = x[i];
x2[i] = x[i];
x3[i] = x[i];
x4[i] = x[i];
x5[i] = x[i];
x6[i] = x[i];
printf("r装填数据中:%.2f%c", (i + 1) * 1.0 / num * 100, '%');
}
printf("n");
int begin[7] = { 0 };
int end[7] = { 0 };
begin[0] = clock();
BubbleSort(x, num);
end[0] = clock();
printf("BubbleSort Endn");
begin[1] = clock();
InsertSort(x1, num);
end[1] = clock();
printf("InsertSort Endn");
begin[2] = clock();
ShellSort(x2, num);
end[2] = clock();
printf("ShellSort Endn");
begin[3] = clock();
HeapSort(x3, num);
end[3] = clock();
printf("HeapSort Endn");
begin[4] = clock();
QuickSort(x4, 0, num - 1);
end[4] = clock();
printf("QuickSort Endn");
begin[5] = clock();
MergeSort(x5, num);
end[5] = clock();
begin[6] = clock();
SelectSort(x6, num);
end[6] = clock();
printf("SelectSort Endn");
printf("n");
printf("BubbleSort : %lf秒n", (end[0] - begin[0])/1000.0);
printf("InsertSort : %lf秒n", (end[1] - begin[1]) / 1000.0);
printf("ShellSort : %lf秒n", (end[2] - begin[2]) / 1000.0);
printf("HeapSort : %lf秒n", (end[3] - begin[3]) / 1000.0);
printf("QuickSort : %lf秒n", (end[4] - begin[4]) / 1000.0);
printf("MergeSort : %lf秒n", (end[5] - begin[5]) / 1000.0);
printf("SelectSort : %lf秒n", (end[6] - begin[6]) / 1000.0);
}
测试结果如下:
最后这篇文章有几个动图，都是我第一次画的，之后的博客会有更多的动图。
