排序算法
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
（1） 直接插入排序
基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
比如当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
具体实现及解析：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
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;
}
}
对一组数据第一次认为第一个数是有序的，把第二个数往前插入根前面比，前两个数有序了再把第三个数插入…前n-1个有序了再把第n个插入，整体就有序了。具体分析分析如下：
1、假设用end指向末尾，把要插入的数（其实就是后一个数，本质上说把后一个数根据大小关系往前插入）保存到tmp变量中，因为一会要挪动数据，有的数据被覆盖。
2、有两种结束的情况，一种是我比你大就插入到你的后面break停止；第二种是end>=0停止。
3、如果tmp比end的值小，就挪动前面的数据，往后挪，否则停止，直到end<0结束。
4、最后不管是由于end停止的还是break停止的，都把tmp放到当前位置end的下一个。
直接插入排序的特性：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：最坏O(N^2) 最好O（N）
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
（2） 希尔排序
基本思想：希尔排序法又称缩小增量法。先选定一个整数，把待排序文件中所有记录分成gap个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。它其实是插入思想的变形。gap是间距，是几就被分为几组。
具体实现及解析：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2 ;
for (int i = 0; i < n - gap; i++)
{
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变成直接插入排序。
1、预排序，把1换成gap个间距进行预排序，gap这时候是大于1的，循环gap次。内循环是为每组挪动，外循环是走gap次，为了使代码简洁减少一个for循环，之前的i+=gap换成i++，实现的是gap组并排，这样一个for循环就能搞定。
2、终止条件是gap>1,>1是预排序，=1是直接插入排序，最初的gap是n，要保证最后一次是gap=1，需除2即可，如果除以奇数再加1。
希尔排序的特性总结：
1、希尔排序是对直接插入排序的优化。
2、当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3、时间复杂度：O(N^1.3)
4、空间复杂度：O（1）
5、稳定性： 不稳定
（3）选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
具体实现及解析：
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、给出左右区间begin和end，创建最小和最大变量，用for循环选出最小最大。
2、第一个位置不用比较，从第二个位置开始，比它小i给mini，比它大i给max，直到大于end结束。
3、再把最小的换到最左边的位置begin，这里如果最大的位置在begin这个位置时，需要做调整，不然会把最大的给换到mini这个位置上，会把最小的换到end这个位置上，把maxi更新成mini就可以解决。把最大的换到最右边的位置，相遇结束同时begin++，end–。
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
（4）堆排序
基本思想：堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。堆排序用堆删除思想，堆删除是在已经是大堆或小堆的条件下，把堆顶和尾进行交换，再把它删除。我们就利用这一思想，把大的或小的换到后面，不删除最后一个即保留它，到最后就形成了从小到大或从大到小的序列。而且它们都是用了向下调整。需要注意的是排升序要建大堆，排降序建小堆。
具体实现及解析：
void AdjustDown(int* a, int n, int parent)
{
assert(a);
int child = 2 * parent + 1;
while (child<n)
{
if (child + 1 < n&&a[child + 1] > a[child])
{
child++;
}
if (a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
向下调整整体思路是：假设是大堆，从根节点即父亲结点开始，和他两个孩子结点最大的比较，从上到下调整。我先假设左孩子child就是最大，之后再来个if函数进行比较，如果child + 1 < n，确保有右孩子，并且child+1如果大于child，说明右孩子大，就++。之后如果最大的孩子比父亲节点大，那就调整，并更新父亲结点，让父亲到孩子结点的位置，并求出它下一个孩子结点下标，如果小于就停止。
堆排序思路：首先用向下调整算法建堆，之后用变量end记录最后一个数的下标，交换之后，用向下调整算法恢复原来的大堆或小堆，最后需要保留最后一个数据，直接end–，即是把倒数第二个赋为end。相当于假删除。
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
（5）冒泡排序
基本思想：重复地走访要排序的元素列，依次比较两个相邻的元素，如果顺序不符合升序或降序要求就交换，直到没有相邻元素需要交换。
具体实现及解析：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j= 1; j < n-i; j++)
{
if (a[j - 1]>a[j])
{
Swap(&a[j - 1], &a[j]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}
用两个for循环，第一层循环表示趟数，第二层循环表示一趟交换的次数，如果每个位置小于前一个位置就交换，这里设置一个exchang变量，表示如果一趟冒泡的过程中没有发生交换说明已经有序，就直接break。
冒泡排序的特性总结：
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
（6）快速排序
基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。以下前三种为递归法，最后一种为非递归法。
（1）hoare法
int GetMidIndex(int* a, int begin, int end)
{
int mid = (end - begin) / 2;
if (a[begin] < a[end])
{
if (a[begin]>a[mid])
{
return begin;
}
else if (a[end] < a[mid])
{
return end;
}
else
{
return mid;
}
}
else
{
if (a[begin] < a[mid])
{
return begin;
}
else if (a[end]>a[mid])
{
return end;
}
else
{
return mid;
}
}
}
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 key = left;
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[left], &a[key]);
key = left;
return key;
}
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 keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
}
以最左边或最右边（不好控制）的值为key基准值。
如果选最左边，右边先走。只有右边先走才能保证相遇位置比key小，原因以下两点：
第一种是左边停住，右边遇到左边，相遇位置就是左边边停住的位置。左边停住之后需要交换，左边交换之后变成小的，右边继续走因为没有遇到小的直到遇到左边，此时的左边一定比key小。
第二种是右边停住，左边遇到右边，相遇位置就是右边停住的位置。右边停住的位置一定是比key小，左边因为没找到大的一直在走遇到右边，所以相遇位置一定比key小。
这里找小，找大的控制条件要加上等于，因为如果key右边所有值都大于key，right–减到负数会发生越界；还有左右两边都有和key相等的值会发生死循环。
代码解析：右边先找小，左边找大，找完之后交换它俩，当left等于right相等时，也就是相遇停止，把相遇的值和最左边的交换，更新key的位置。这是单趟，返回key，keyi接收，这样达到的目的是key到了正确的位置，左边的比它小，右边的比它大，而且划分了左右区间，要让左区间和右区间有序，整体就有序，这是子问题就得用递归解决，所以继续递归左右子区间直到begin小于end结束。
这里用到三数取中和小区间进行了优化：三数取中选出不是最大或最小的下标，防止最坏情况出现影响时间复杂度，这里的时间复杂度从N^2变成N*logN。
小区间优化是当快排分割到小区间时，用直接插入排序减少递归调用次数。
（2）挖坑法
具体实现及解析：
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] >= a[key])
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right&&a[left] <= a[key])
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
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 keyi = PartSort2(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
}
方法解析：第一次先在key那个位置挖上坑，从右边先找小，找到之后把小的填到原先那个坑上，在原来的位置重新形成坑，再从左边找大，找到之后把大的填到右边的那个坑上，在原处又形成坑位，相遇在坑位上停止，再把最初的key填到最后的坑上，并返回坑的下标，来分割区间继续递归左右区间直到begin小于end结束。
（3）前后指针法
具体实现解析：
int PartSort3(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int key = begin;
int pre = begin, cur = begin + 1;
while (cur <= end)
{
while (a[cur] < a[key] && ++pre != cur)
{
Swap(&a[pre], &a[cur]);
}
++cur;
}
Swap(&a[pre], &a[key]);
key = pre;
return key;
}
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 keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
}
方法解析：先用pre存放起始位置，cur存放起始位置的下一个位置，并选最左边的为key。cur位置和key比较，如果比它小且++pre不等于cur，就交换pre和cur的位置，正好大的往后调，下的往前调，因为pre是紧跟cur的，当cur比key大时，cur++才能和pre拉开差距，cur和pre中间的是比key大的值。当满足了第一个条件时++pre就到了比key大的位置，再交换等于把左边大的和右边小的交换了。直到cur>end结束，再pre位置的值和key交换，更新key的位置并返回。
（4）非递归法
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)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key-1);
}
}
StackDestroy(&st);
}
非递归用整体思路：它是用栈结构去实现，和递归过程（先递归左边再递归右边）是一样的，只是不是通过函数调用来完成，先把区间压到栈里去，选key单趟排，划分为子区间后，右边区间先压栈，左边区间再压栈，左边区间先出来选key单趟排…等子区间剩下一个值时或不存在，就不压了。它其实就是在模拟递归的过程，只是把递归过程里面存在栈帧的区间用数据结构栈存起来。
代码解析：先把begin和end整体区间入到栈里去，因为栈是后进先出，进入到while循环里面之后，取区间，右边先出，左边再出，同时用right和left保存起来，再进行单趟排被分割出三个部分【left，key-1】key 【key+1，right】，再继续入，想要像递归过程一样先处理左区间，则要保证左区间后入，这样才能先取到左区间。栈非空说明有区间还要排，反之则停止。最后释放栈。
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
（7）归并排序
**基本思想：**归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
（1）递归实现
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (end >= begin)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid -1, tmp);
_MergeSort(a, mid + 1, end, tmp);
int begin1 = begin, end1 = mid - 1;
int begin2 = mid + 1,end2 = end;
int i = begin;
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, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == 0)
{
perror("malloc fail ");
}
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
递归方法：先把区间分割最小，分割到只有一个值时停止，再进行往回归并，归回去就有序了，它是一个后序遍历的过程。
1、先申请一个临时数组，调用一个子函数，进入子函数里先进行分割区间，如果左区间和右区间有序就可以归并，这里递归左右区间直到不能再分割停止，认为只有一个值有序。
2、两段区间归并，进行尾插，如果begin1比begin2小，每次取小的就尾插到tmp数组里，这里结束条件只有一个为假，因为只有一个在走，再用两个while循环继续尾插没有走完的，最后进行拷贝到原数组里。
（2）非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == 0)
{
perror("malloc fail ");
}
_MergeSort(a, 0, n - 1, tmp);
int range = 1;
while (range < n)
{
for (int i = 0; i < n; i += 2 * range)
{
int begin1 = i, end1 = i + range - 1;
int begin2 = i + range, end2 = i + 2 * range -1;
int j = i;
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));
}
range *= 2;
}
}
快速排序是可以利用栈的性质来进行非递归改进，但归并不可以，（只借助栈搞不定得用其他一些辅助手段），它属于后序，前者属于前序。因为栈适合前序，处理完就pop掉了，递归左右子区间。后序，如果通过栈可以把区间分出来，但是返回去的时候，找不到上一个较大的区间进行归并。简言之，栈或者队列实现的递归方式划分后的区域只能取到一次，只能划分，归并排序需要一个归并回去的过程，如果使用，栈内已经空了。
非递归方法具体思路：只需要控制单个区间的大小去解决。给个range指的是一个区间的个数，range=1是一一归，之后再拷贝，range*=2,两个两个归，再拷贝，再*2等于4，四个归，当range<n停止。（归并的内容和递归中的归并一样）。
但上面思路存在一些问题，会有越界的可能，假如有10个数就有越界，因为begin1<n,它不可能越界，end1，begin2和end3都有可能越界。以下分3种越界：
1、end1，begin1和end2越界
第一种方法修正：把end1修正为n-1，把begin2和end2修改为不存在的区间即begin2=n，end2=n-1，使其满足不了下面的归并条件。
第二种方法修正：直接break。
如果选第二种方法，就必须得归并一部分，拷贝一部分，如果整体拷贝，end2>=n，break，不会进行下面的归并步骤，临时数组里的后半段没有归并会变成随机值，再拷贝回去把原来的值给覆盖掉。而归并一部分，拷贝一部分，break，不再进行后面的归并，后面未归并的在原数组里，而前面的已经拷贝回去了。
2、begin2越界，end2越界
同1。end1就不考虑了，begin2和end2改成不存在的区间即可。
3、end2越界
直接end2改为n-1，适合部分拷贝和整体拷贝。
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
（8）排序代码
（1）Stack.c
#include"Stack.h"
void StackInit(Stack* ps)
{
ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
ps->top = 0;
ps->capacity = 4;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a,ps->capacity*sizeof(STDataType)* 2);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps ->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->top] = data;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
（2）Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
bool StackEmpty(Stack* ps);
void StackDestroy(Stack* ps);
（3）Sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"Stack.h"
void Swap(int* e1, int* e2);
void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void SelectSort(int* a, int n);
void AdjustDown(int* a, int n, int parent);
void HeapSort(int* a, int n);
void BubbleSort(int* a, int n);
int GetMidIndex(int* a, int begin, int end);
int PartSort1(int* a, int begin, int end);
int PartSort2(int* a, int begin, int end);
int PartSort3(int* a, int begin, int end);
void QuickSort(int* a, int begin, int end);
void QuickSortNonR(int* a, int begin, int end);
void _MergeSort(int* a, int begin, int end, int* tmp);
void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
void CountSort(int* a, int n);
（4）test.c
#include"Sort.h"
void TestInsertSort()
{
int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestShellSort()
{
int a[] = { 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 15, 14};
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestSelectSort()
{
int a[] = { 29, 21, 22, 25, 27, 24, 28, 26, 23, 25 };
SelectSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestHeap1()
{
int array[] = { 26, 14, 17, 59, 29, 33, 99, 46, 22, 36 };
HeapSort(array, sizeof(array) / sizeof(int));
for (int i = 0; i < sizeof(array) / sizeof(int); ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}
void TestBubbleSort()
{
int a[] = { 39, 31, 32, 35,37, 34, 38, 36, 33, 35 };
BubbleSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuickSort()
{
int a[] = { 46, 41, 42, 47, 49, 43, 44, 45, 48, 41, 48 };
QuickSortNonR(a, 0, sizeof(a) / sizeof(int)-1);
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestMergeSort()
{
int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 6, 8 };
MergeSortNonR(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestCountSort()
{
int a[] = { 3, 4, 6, 2, 8, 5, 2, 2, 9, 9, 10, 10 };
CountSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestHeap1();
}
（5）Sort.c
#include"Sort.h"
void Swap(int* e1, int* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
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;
}
}
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2 ;
for (int i = 0; i < n - gap; i++)
{
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;
}
}
}
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--;
}
}
void AdjustDown(int* a, int n, int parent)
{
assert(a);
int child = 2 * parent + 1;
while (child<n)
{
if (child + 1 < n&&a[child + 1] > a[child])
{
child++;
}
if (a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j= 1; j < n-i; j++)
{
if (a[j - 1]>a[j])
{
Swap(&a[j - 1], &a[j]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}
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 key = left;
while (begin < end)
{
while (left<right&&a[right] >= a[key])
{
right--;
}
while (left < right&&a[left] <= a[key])
{
left--;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
}
int GetMidIndex(int* a, int begin, int end)
{
int mid = (end - begin) / 2;
if (a[begin] < a[end])
{
if (a[begin]>a[mid])
{
return begin;
}
else if (a[end] < a[mid])
{
return end;
}
else
{
return mid;
}
}
else
{
if (a[begin] < a[mid])
{
return begin;
}
else if (a[end]>a[mid])
{
return end;
}
else
{
return mid;
}
}
}
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 key = left;
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[left], &a[key]);
key = left;
return key;
}
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] >= a[key])
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right&&a[left] <= a[key])
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
int PartSort3(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int key = begin;
int pre = begin, cur = begin + 1;
while (cur <= end)
{
while (a[cur] < a[key] && ++pre != cur)
{
Swap(&a[pre], &a[cur]);
}
++cur;
}
Swap(&a[pre], &a[key]);
key = pre;
return key;
}
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 keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi+1, end);
}
}
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)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if (left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key-1);
}
}
StackDestroy(&st);
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (end >= begin)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid -1, tmp);
_MergeSort(a, mid + 1, end, tmp);
int begin1 = begin, end1 = mid - 1;
int begin2 = mid + 1,end2 = end;
int i = begin;
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, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == 0)
{
perror("malloc fail ");
}
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == 0)
{
perror("malloc fail ");
}
_MergeSort(a, 0, n - 1, tmp);
int range = 1;
while (range < n)
{
for (int i = 0; i < n; i += 2 * range)
{
int begin1 = i, end1 = i + range - 1;
int begin2 = i + range, end2 = i + 2 * range -1;
int j = i;
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));
}
range *= 2;
}
}
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* countArray = (int*)malloc(range*sizeof(int));
memset(countArray, 0, sizeof(int)*range);
for (int i = 0; i < n; ++i)
{
countArray[a[i] - min]++;
}
int index = 0;
for (int i = 0; i < range; ++i)
{
while (countArray[i]--)
{
a[index++] = i + min;
}
}
}
|