目录
一.插入类型的排序
1.插入排序
2.希尔排序
二.选择类型的排序
1.选择排序
2.堆排序
三.交换类型的排序
1.冒泡排序
2.快速排序
三数取中优化
①hoare法
②挖坑法
③前后指针法
（1）快速排序（递归版）
（2）快速排序（递归版）（优化：小区间直接插入排序）
（3）快速排序（非递归版）
四.归并类型的排序
1.归并排序
五.非比较类型的排序
1.计数排序
前言：这里将会实现插入排序、希尔排序，选择排序、堆排序，冒泡排序、快速排序，归并排序和计数排序。
注意：这里的排序都为升序。
一.插入类型的排序 1.插入排序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;
}
}插入排序主要是要用一个临时变量去记录当前值，并定义一个end遍历，然后和前面的值去比较，如果比前面值小，就让前面的值覆盖该值，然后--end，继续与前面的值比较，如果比前面值大，直接break，然后让这个位置插入这个值。
直接插入排序的特性总结： 1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定2.希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
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的记录分在同一个组，并对每一组内的记录进行排序。这里首先让gap = n每次循环让gap = gap / 3 + 1，直到gap = 1的时候，就排好序了。
希尔排序的特性总结： 1. 希尔排序是对直接插入排序的优化。 2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。 3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此 希尔排序的时间复杂度并不固定，在O(N * logN)左右，大致区间为O(N^1.25)到O(1.6 * N ^ 1.25) 4. 稳定性：不稳定。二.选择类型的排序 1.选择排序
void SelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
int mini = left, maxi = left;
for (int i = left; i <= right; ++i)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);
if (maxi == left)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
++left;
--right;
}
}选择排序就是每次选出一个最小（或最大）的元素，这里优化了，同时选择最小和最大的元素，分别放在序列的始位置和末位置，循环直到全部排序结束。
直接选择排序的特性总结： 1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：不稳定2.堆排序
void AdjustDown(int* a, size_t size, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
size_t end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}堆排序我在上一篇有详细的说明：C语言 二叉树实现堆及堆排序_糖果雨滴a的博客-CSDN博客
这里简单说一下：堆排序就是用树这种结构设计出的排序，排升序建大堆，排降序用小堆。
具体实现可以看我的上一篇。
堆排序的特性总结： 1. 堆排序使用堆来选数，效率高了很多。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(1) 4. 稳定性：不稳定三.交换类型的排序 1.冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; ++j)
{
int flag = 0;
//单趟
for (int i = 1; i < n - j; ++i)
{
if (a[i - 1] > a[i])
{
flag = 1;
Swap(&a[i - 1], &a[i]);
}
}
if (flag == 0)
{
break;
}
}
}冒泡排序就是交换，两个记录的相互比较，满足条件就交换，一直到结束。
升序就是让大的向尾部逐渐移动，小的向头部逐渐移动。
冒泡排序的特性总结： 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：稳定2.快速排序 三数取中优化
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}int PartSort1(int* a, int left, int right)
{
//三数取中优化
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
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[key], &a[left]);
return left;
}hoare法：先取一个元素作为基准值，这里我们取最左边的元素为基准值key，然后定义两个变量，一个从右走，一个从左走。
右边的找比key小的，找到停下，左边再找比key大的，找到停下，两个元素交换，然后继续走。
直到相遇时，让key和该相遇点交换。
②挖坑法int PartSort2(int* a, int left, int right)
{
//三数取中优化
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
//坑位
int pit = left;
while (left < right)
{
//右边先走，找小
while (left < right && a[right] >= key)
{
--right;
}
a[pit] = a[right];
pit = right;
//左边走，找大
while (left < right && a[left] <= key)
{
++left;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}挖坑法：先取一个元素作为基准值key，这里我们取最左边的元素，然后key保存该位置的值。
接下来我们让该位置为坑位，然后定义两个变量，一个从右走，一个从左走。
右边的找比key小的，找到停下，之后让该值变成坑位的值，再让该位置变成新的坑位，左边同理，找比key大的，找到停下之后让该值变成坑位的值，再让该位置变成新的坑位。
最后相遇的时候，让坑位变为保存的key的值。
③前后指针法int PartSort3(int* a, int left, int right)
{
//三数取中优化
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && a[++prev] != a[cur])
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;
}前后指针法：先取一个元素作为基准值key，这里我们取最左边的元素，然后定义两个变量prev和cur，这里我们从左边开始往右走，所以分别定义位left和left+1。
cur往右走，遇到比key小的之后，先让prev往后走一步，之后两个元素交换，如果是同一个就不用交换。如何cur遇到比key大的，就cur往后走，prev不动。
cur走到了最后的时候，让key和prev位置的值进行交换。
（1）快速排序（递归版）void QuickSort1(int* a, int begin, int end)
{
//子区间相等说明只有一个值，可以表明递归结束
//begin > end，说明子区间不存在
if (begin >= end)
return;
int keyi = PartSort3(a, begin, end);
//递归，分成两个区间分别再次进行快排
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}在进行一趟排序之后，最后返回的那个值就已经排好了位置，然后按照返回的位置，进行递归，分割成两个子序列， 重复进行。
这里采用了三数取中的方法进行了优化。
（2）快速排序（递归版）（优化：小区间直接插入排序）void QuickSort2(int* a, int begin, int end)
{
//子区间相等说明只有一个值，可以表明递归结束
//begin > end，说明子区间不存在
if (begin >= end)
return;
//优化：小区间采用直接插入排序控制有序，以减少递归调用，减少时间损耗
if (end - begin + 1 <= 13)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort3(a, begin, end);
//递归，分成两个区间分别再次进行快排
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}
}这个是当剩的元素不多的时候进行直接插入排序，为了减少递归调用，节省时间。
（3）快速排序（非递归版）void QuickSortNonR(int* a, int begin, int end)
{
ST 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 keyi = PartSort3(a, left, right);
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
}
StackDestory(&st);
}非递归版要利用栈，这里我们之前实现了栈：C语言栈与队列实现_糖果雨滴a的博客-CSDN博客
利用栈的特性去实现非递归版的快速排序。
快速排序的特性总结： 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(logN) 4. 稳定性：不稳定四.归并类型的排序 1.归并排序
（1）递归版
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int index = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
assert(tmp);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}归并排序是采用的分治法，通过递归，不断的往下缩小子区间，然后让每个小区间有序，再使子区间之间有序，最后全部有序。
（2）非递归版
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
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;
//end1越界，可修正
if (end1 >= n)
{
end1 = n - 1;
}
//begin2越界，第二个区间不存在
if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
//begin2不越界，end2越界，修正end2
if (begin2 < n && end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
}
memcpy(a, tmp, n * sizeof(int));
gap *= 2;
}
}非递归版，可直接利用循环去控制实现分治法。
这里要注意变量是否越界。
归并排序的特性总结： 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(N) 4. 稳定性：稳定五.非比较类型的排序 1.计数排序
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* countA = (int*)calloc(range, sizeof(int));
assert(countA);
//计数
for (int i = 0; i < n; ++i)
{
countA[a[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < range; ++i)
{
while (countA[i]--)
{
a[j++] = i + min;
}
}
}计数排序由叫鸽巢原理，是哈希的变形应用。
先创建一个数组去统计相同元素的出现次数，然后根据统计的结果将序列放入到原来的数组中。
计数排序的特性总结： 1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 2. 时间复杂度：O(MAX(N,范围)) 3. 空间复杂度：O(范围) 4. 稳定性：稳定
这些排序都是很重要的，我们要好好理解，并且可以通过理解自己写出来。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）