排序算法
目录
前言
一、排序的概念
1.1排序的概念
1.2 常见的排序算法
二、常见排序算法的实现
2.1 插入排序
2.2 希尔排序
2.3 选择排序
2.4 堆排序
2.5 冒泡排序
2.6 快速排序
2.6.1 hoare版本
2.6.2 前后指针版本
2.6.3 非递归版本
2.7 归并排序
归并排序
2.8 计数排序
三、算法性能
总结
前言
今天为我们来通过C语言来实现常见排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、堆排序，了解算法的具体实现和算法的性能。
一、排序的概念
1.1排序的概念
1.2 常见的排序算法
二、常见排序算法的实现
2.1 插入排序
动画图解如下：
//插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end=i;
int temp = a[end + 1];
while (end >= 0)
{
//比较与end位置元素大小
if (temp < a[end])
{
a[end + 1] = a[end];
end--;
}
//大于end位置元素，跳出
else
{
break;
}
}
//1.end大于零，temp放在end元素后一个
//2.end小于零，temp也是放在end元素后，只不过此时为第一个元素
a[end + 1] = temp;
}
}直接插入排序
时间复杂度：O(N^2)空间复杂度：O(1)
稳定性：稳定
最坏情况：逆序
最好情况是多少：顺序有序或者接近有序 O(N)
2.2 希尔排序
，先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序，重复上述步骤。然后排序就变得简单了。
//希尔排序
void ShellSort(int* a, int n) {
int gap=n;
while (gap > 1)
{
gap/=2;
//循环到n-gap-1元素
for (int i = 0; i < n-gap; i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (temp < a[end])
{
a[end + gap] = a[end];
//end移动距离为gap
end -= gap;
}
else
{
break;
}
}
//各自插入到每组元素
a[end + gap] = temp;
}
}
}希尔排序时间复杂度：O(N^1.3)
空间复杂度：O(1)
稳定性：不稳定
2.3 选择排序
//选择排序
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = 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 (begin == maxi)
maxi = mini;
Swap(&a[end], &a[maxi]);
//缩小范围
begin++;
end--;
}
}直接选择排序时间复杂度： O(N^2)空间复杂度： O(1)稳定性：不稳定
2.4 堆排序
//堆排序
//向下调整
void AdjustDown(int* a, int n, int parent) {
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
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--;
}
}堆排序时间复杂度： O(N*logN)空间复杂度： O(1)稳定性：不稳定
2.5 冒泡排序
//冒泡排序
void BubbleSort(int* a, int n) {
for (int i = 0; i < n - 1; i++)
{
int exchang = 0;
for (int j = 1; j < n - i; j++)
{
//前一个比后一个大就交换
if (a[j] < a[j - 1])
{
Swap(&a[j], &a[j - 1]);
exchang = 1;
}
}
if (exchang == 0)
break;
}
}冒泡排序
时间复杂度： O(N^2)空间复杂度： O(1)稳定性：稳定
2.6 快速排序
思路：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
选择基准值有多种方法：
1.直接选择头或者尾为基准值(但是序列为有序或者接近有序时间复杂度大)
2.随机数取基准值
//随机取基准值
int randi = rand() % (right - left + 1);
randi += left;
Swap(&a[left], &a[randi]);//基准值放到序列头3.三位数取中
取序列头尾和中间三个数，让不是最大的，也不是最小的作为基准值。
//三位数取中
int midi = GetMidi(a, left, right);//取中间值函数
Swap(&a[midi], &a[left]);//基准值放到序列头将区间按照基准值划分为左右两半部分的常见方式有：
2.6.1 hoare版本
思路：选择key(基准值),从尾向头开始找比key小的，然后再从头找比key大的，交换两者，然后继续整个步骤，直到它们两个相遇，交换key位置到相遇位置处，这样key前面就全为比key小的，后面全为比key大的，此时key为正确位置，然后分割序列，分为key前面的和key后面，重复上面所有步骤。
我们这直接选择最左边为key
步骤：1.最左边为key，定义left，right代表key下一个位置，序列尾
2.让right向前走，找到比key小的，找到了停止
3.让left向后走，找到比key大的，找到了停止
4.交换此时righ和left的位置上的元素，重复2，3步骤
5.直到相遇，交换此时相遇位置和key的。
6.分割序列，分为keyi前面的序列和keyi后面的位置，重复以上所有步骤。
动画图解如下：
//快速排序 hoare版本
void QuickSort1(int* a, int left, int right) {
//当只有一个元素和为空序列返回空
if (left >= right)
return;
int begin = left, end = right;
//取序列开头为key
int keyi = left;
while (left < right)
{
//找比key小的
while (left < right && a[keyi] <= a[right])
{
right--;
}
//找比key大的
while (left < right && a[keyi] >= a[left])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
//递归[begin,keyi-1] 和 [keyi+1,end]
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi+1, end);
}2.6.2 前后指针版本
思路：选择最左或者最右为key，定义两个指针prev和cur分别指向序列开头，prev下一个位置。然后向后走，如果遇到比key小的cur走，prev也向后走。直到遇到比key大的，只有cur走，prev不走，当再次遇到比key小的，prev先走，然后交换此时cur和prev的值，cur再走。重复上面步骤，直到cur走到序列尾,然后交换prev和key的值。通过上面操作我们可以让cur和prev中间的值为比key大的，此方法就是把比key大的往后推，小的往前移。
步骤：1.选择最左key，prev和cur分别指向序列开头，开头下一个
2.cur先走，prev后走
3.遇到比key大的，只有cur走
4.再遇到key小的，prev先走，然后交换此时prev和cur的值，cur在走
5.cur走到序列尾，交换prev和key的值
6..分割序列，分为keyi前面的序列和keyi后面的位置，重复以上所有步骤。
动画图解如下：
//快速排序
//前后指针法
void QuickSort2(int* a, int left, int right) {
if (left >= right)
return;
int prev = left, cur = left+1;
int keyi = left;
while (cur <= right)
{
//如果遇到比key小的才交换
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
//分割[left,keyi-1] [keyi+1,right]
QuickSort2(a, left, keyi - 1);
QuickSort2(a, keyi+1, right);
}2.6.3 非递归版本
思路：之前我们都是通过递归来解决的，我们需要的是排序的左右子区间，所以我们可以通过一个栈来存储排序的左右子空间，根据栈先进后出的特性。左右子区间依次进栈出栈从而达到递归的效果。
void QuickSortNonR(int* a, int left, int right) {
ST st;
StackInit(&st);
//左右下标入栈
//右边先进 左边后进
StackPush(&st,right);
StackPush(&st,left);
while (!StackEmpty(&st))
{
left = StackTop(&st);
StackPop(&st);
right = StackTop(&st);
StackPop(&st);
//单趟
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
//[left,key-1] && [key+1,right]
//进左右子区间
if (keyi + 1 < right)
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > left)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}
快速排序时间复杂度： O(N*logN)空间复杂度： O(logN)稳定性：不稳定
2.7 归并排序
思路：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
//归并排序
void _MergeSort(int* a, int begin, int end, int* temp) {
//只有一个元素就返回
if (begin == end)
return;
//从中间开始分割
int mini = (begin + end) / 2;
//指向两个序列起始位置
int begin1 = begin, end1 = mini;
int begin2 = mini + 1, end2 = end;
_MergeSort(a, begin1, end1, temp);
_MergeSort(a, begin2, end2, temp);
//单趟
//选下的插入到新的序列中
int i = begin;//插入位置要保持相对位置
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
//插入没有插入完的
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//拷贝位置也要保持相对位置
memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n) {
//开辟新的序列
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0, n-1, temp);
free(temp);
temp = NULL;
}非递归版本
我们之前是用递归先进行单个排序，在到组排。我们也可以不通过递归，通过回溯的思想，先定义一个gap，gap从1开始，即先单个为一组，然后两两排序，然后进行循环gap×2来进行gap数量为一组在进行归并。
void MergeSortNonR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int j = 0; j < n; j += gap * 2)
{
//两个区间的起始位置
int begin1 = j, end1 = j + gap - 1;
int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
//判断是否有越界
if (end1 >= n || begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
int i = j;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//相对位置
memcpy(a + j, temp + j, sizeof(int) * (end2 - j + 1));
}
gap *= 2;
}
free(temp);
temp = NULL;
}归并排序
时间复杂度：O(N*long N)
空间复杂度：O(N)
稳定性：稳定
2.8 计数排序
//计数排序
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* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
return;
}
memset(count, 0, sizeof(int) * range);
//计数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//排序
int j = 0;
for (int i = 0; i < n; i++)
{
while (count[i]--)
{
a[i] = i + min;
}
}
}计数排序
时间复杂度：O(N+range)
空间复杂度：O(range)
三、算法性能
总结
上述文章，我们介绍了各种排序算法，希望对你有所帮助。
