轻松理解 七大排序算法 （C语言实现）
目录
? ? ? ??通过动画可视化数据结构和算法<br> - VisuAlgo?这里先给大家推荐个网站，在这个网站上，你可以看到数据结构及算法各种实现的动图，方便你更好的学习。
? ? ? ? 为了更简单的描述和理解，我们都是用数组来实现八中算法。
1. 冒泡排序
? ?基本思想：
????????两两比较相邻记录的关键字，如果反序就交换，知道没有反序的记录为止。简单理解就是，我们一次排序，都是将较大/小的数据往后移，直到数组末尾，就向可乐中的气泡一样，往上冒。
? ? ? ? 对于冒泡排序，我们也只是在学习过程中会用到，在实际应用中，我们很少会运用，因为它的效率是在太低了。
排序（冒泡排序，选择排序，插入排序，归并排序，快速排序，计数排序，基数排序） - VisuAlgo
? ?时间复杂度：
? ? ? ? 最坏情况：O(N^2)? 。如果数组是反序的，那么每次排序都需要执行N-1次，一共有N个数，所以这是一个等差数列相加，得出结果就是O(N^2)
? ? ? ? 平均情况：O(N^2)
? ? ? ? 最好情况：O(N) 。如果数组基本有序，那么每次排序只需要执行O(1)次，遍历一遍数组就能将数组排好序。这里的基本有序是指，小的数据元素基本放在前面，大的数据元素基本在后面，不大不小的基本在中间。
? ?优化：
????????如果我们排完一趟之后，发现没有交换，说有数组已经有序了，就没必要往交换了，结束排序就可以了。
? ?代码展示：
void BubbleSort(int* a, int size)
{
for (int i = 0;i < size - 1;i++)
{
bool change = false;
for (int j = 0;j < size - 1 - i;j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
change = true;
}
}
if (change == false)
{
break;
}
}
}? ?特性总结：????????
2. 直接插入排序
????????
基本思想：
????????将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录增1的有序表。我们将第一个元素看做是一个排好序的有序表，将第1个与第2个进行比较，将两个元素组成一个新的升/降序有序表，以此类推...
时间复杂度：
? ? ? ? 最坏情况：O(N ^ 2) ，如果这个数组反序的，那么每一次都需将将有序表后一个元素，插入到最前面，这是一个等差数列相加，得出结果为 N^2.
? ? ? ? 平均情况：O(N ^ 2)
? ? ? ? 最好情况：O(N)，若果数组是基本有序的，那么每次排序只需要O(1),一共执行N次 ，得出结果为N
代码实现：
void InsertSort(int* a, int size)
{
for (int i = 1;i < size-1;i++)
{
int end = i - 1;
int temp = a[end+1];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = temp;
}
}特性总结：
3. 简单选择排序
基本思想：
????????每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
时间复杂度：
????????最坏情况;? ?O(N ^ 2)
? ? ? ? 平均情况：O(N ^ 2)
? ? ? ? 最好情况：O(N ^ 2) , 对于选择排序来说每一次排序就是从N个数中选择最小/大的数放在第一个位置，再选出第二小/大的数放在第一个位置，以此类推，总共执行N-1次。所以对于选择排序，不管什么情况都是 O(n ^ 2)
? ? ? ? 这里可能有人会觉得，简单选择排序不管什么情况都是N^2 ,所以它的时间复杂度是最高的，其实，在实际排序中，冒泡是最慢的，这里它们时间复杂度都是O(N ^2)只能说明它们属于同一个量级的，并不能直接代表孰优孰劣。
代码实现：
void SelectSort(int* a, int size)
{
for (int i = 0;i < size-1;i++)
{
int mini = i;
for (int j = i + 1;j < size;j++)
{
if (a[mini] > a[j])
{
mini = j;
}
}
Swap(&a[mini], &a[i]);
}
}
//优化
void SelectSort(int* a, int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin;i <= end;i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}? ? ? ? 上述代码，我们将选择排序进行了优化，即一次排序过程中，我们既选出最大值，也选出最小值，将最大值放在后面，最小值放在前面。
特性总结：
4. 希尔排序(缩小增量排序)
void ShellSort(int* a, int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0;i < size - gap;i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}基本思想：
????????先选定一个整数，把待排序数组中所有记录分成组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后， 重复上述分组和排序的工 作。当到达N =1 时，所有记录在统一组内排好序 。
时间复杂度：
? ? ? ? 希尔排序的时间复杂度并不好计算，因为gap的取值目前并没有得出最优结果，许多业内大佬也没有计算出，因为我们的gap是由Knuth踢出的方式取值的，而且Knuth进行了大量的实验统计，所以本文就咱是按照：O(N ^ 1.25) 到 O(1.6 * N^ 1.25)来计算。
代码展示：
void ShellSort(int* a, int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0;i < size - gap;i++)
{
int end = i;
int temp = a[end + gap];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}特性总结：
5. 堆排序
二叉树——堆（C语言，配图，例题详解，TopK问题+堆排序）-CSDN博客
? ? ? ? 堆排序是基于数据结构中堆的概念来实现的，如果 你对堆不太熟悉，可以从这篇文章中学习了解什么是堆。
? ? ? ? 简单来说，堆就是上图所示的二叉树（每个节点最多有两个孩子节点），其父节点总是大于/小于孩子节点。
? ? ? ? 根据堆的概念，我们可以得出，第一层节点（根节点）总是最大的，我们只需要将根节点与最后一个节点交换，调整根节点至合适位置，这就是调堆的过程，再将堆的大小-1，直到堆中没有节点。
基本思想：
????????将待排序的序列构造成一个打定对，此时，整个序列的最大值就是堆顶的根节点。将它移动走（其实就是与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的N-1个序列重新构造成一个堆，这样就会得到N个元素中的次大值。如此反复进行，便能得到一个有序序列。
时间复杂度：
? ? ? ? 最坏情况：O(N*logN)
? ? ? ? 平均情况：O(N*logN)
? ? ? ? 最好情况：O(N*logN) ，堆排序就是一个建堆，并不断调堆的过程，即便对有重复数据的序列排序时，依然具有不错的效率。
代码实现：
void HeapSort(int* a, int size)
{
//建堆
for (int i = (size - 2) / 2;i >= 0;i--)
{
AdjustDown(a, i, size);
}
int end = size-1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, 0, end);
end--;
}
}特性总结：
1. 堆排序使用堆来
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
6. 快速排序
6.1 递归版
????????快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。它的方法就是，每次选出来一个数，都将这个数放在排完序后应该在的位置。
? ? ? ? 例如：6? 3? 9? 7进行排序，我们选择6，进行一次排序后，序列为，?3 , 6 , 9 ,?7，此时6所在的位置就是排完序后应该在的位置。
基本思想：
? ? ? ? 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别堆这两部分记录继续进行排序，以达到整个序列有序的目的。
? ? ? ? 即每次选出一个数据?，以它为中介 key，小于key的数据放在左面，大于key的放在右面，在分别对两边进行快速排序，以做到整体有序。
时间复杂度：
? ? ? ? 最坏情况：O(N^2)，对于整个序列基本有序，每次分割只比上一次少一个，仍要执行N-1次，所以时间复杂度达到N^2, 所以快速排序不适合对于有重复项的序列进行排。
? ? ? ? 平均情况：O(N?* log N)
????????最好情况：O(N * logN)，对于最好情况，我们每次选出来的key都是中位数，即左右两边的数据个数相等，一共有logN层，每层我们都简单认为是N个数，所以时间复杂度是 N * logN。这也是快速排序的一种优化，即选择中位数。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key = _PartSort(a,begin,end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}? ? ? ? 这里_PartSort函数的意思是进行一趟排序，返回中位数的小标，在对中位数的两边进行递归，进行排序，知道只有1个数或者没有数据时，结束递归。
? ? ? ? 这里_Partsort函数有三种实现方法，首先我们来看一下创作者Hore的原始方法。
Hore法：
int _PartSort1(int* a, int left, int right)
{
//三位数取中位数
int mid = GetMiddle(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
? ? ? ? 对于Hore法，原理是，先从左边right开始，找出比key位置数据小的元素，再从左边left开始，找出比key位置数据大的元素，交换right 和 left 下标位置的元素。
????????当left >= right的时候结束循环，此时left 和 right 相遇 ，相遇点就是key位置数据应该在的位置。交换left下标和left下标位置的数据，此时key左边的元素都比key下标的位置元素小，右边都比它大。
? ? ? ? 这里有个你是否有个疑问？为什么要从右边开始：
? ? ? ? 这里先说个结论，如果使用Hore法，并且选择的数是在左边，一定要先从右边开始。如果你选择的数在右边，一定要在左边开始。
? ? ? 以第一种方法为例，选择的数在左边，从右边开始，会有两种情况：
? ? ? ? 1. right 遇到 left ，这里能保证left之后的数都是大于key下标的数据。
? ? ? ? 2. right 遇到 key，?结束循环。
? ? ? ? 如果先从左边开始，当left遇到right时，如果交换key 和 left下标位置数据，则将大于key下标位置数据的元素放在序列之前。
挖坑法：
? ? ? ? 如果你自己写了一遍Hore法的快速排序的话，你一定会发现，是在有太多要注意的了，例如为什么要先从左边或者右边开始等等。所以就有人想了个更好的解释方法，对Hore法进行改进，使得逻辑看起来更加合理，当然不管哪种方法，时间复杂度都是一样的，并没有什么本质的区别。
int _PartSort2(int* a, int left, int right)
{
//三位数取中位数
int mid = GetMiddle(a, left, right);
Swap(&a[left], &a[mid]);
int key = a[left];
int hore = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
Swap(&a[hore], &a[right]);
hore = right;
while (left < right && a[left] <= key)
{
left++;
}
Swap(&a[hore], &a[left]);
hore = left;
}
a[hore] = key;
return hore;
}? ? ? ? 挖坑法就是值，取出第一个位置的值key，挖个坑，从右边开始，找到比key小的，放在坑里面，再将坑放在后面；再从左边开始，找到比key大的，放在坑里面。以此类推，知道left和right相遇。??
双指针法：
? ? ? ? 双指针法，是我们平常使用最多的一种方法。当然如果你熟练掌握这三种方法，这对你来收并没有什么。
int _PartSort3(int* a, int left, int right)
{
//三位数取中位数
int mid = GetMiddle(a, left, right);
Swap(&a[left], &a[mid]);
int key = left;
int prev = key;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev <= right)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
return key;
}? ? ? ? cur下标从prev+1开始，找到比key下标位置数据大的就+1,比它小的就和prev+1位置的数据相互交换。知道cur找完序列，再将key下标位置的数据和prev数据交换，此时key下标数据找到最终位置。
6.2 非递归版
? ? ? ? 对于递归的实现，我们通常有另外两种方法：
? ? ? ? 1. 迭代
? ? ? ? 2. 数据结构中的 ——栈
? ? ? ? 因为栈的原理和递归原理相同，所以我们通常会用数据结构中的栈来模拟实现递归，如果你对栈没有详细的了解，可以参考下面这篇文章。
数据结构入门————栈和队列（C语言/零基础/小白/新手+模拟实现+例题讲解）-CSDN博客
? ? ? ? 因为篇幅的限制，所以下面代码涉及的栈的实现，初始化等操作都并没有展示，如果感兴趣，可以阅读上面这篇文章。
????????
void QuickSortNonR(int* a, int begin,int end)
{
ST stack;
//初始化
StackInit(&stack);
StackPush(&stack, end);
StackPush(&stack, begin);
//栈 不为 空
while (!StackEmpty(&stack))
{
int left = StackTop(&stack);
StackPop(&stack);
int right = StackTop(&stack);
StackPop(&stack);
int key = _PartSort3(a, left, right);
if (left < key - 1)
{
StackPush(&stack, key - 1);
StackPush(&stack, left);
}
if (key + 1 < right)
{
StackPush(&stack, right);
StackPush(&stack, key + 1);
}
}
//销毁
StackDestroy(&stack);
}
? ? ? ? 这里我们先将区间入栈，每次排序都将区间出栈，如果满足条件就将区间入栈，知道栈为空。
? ? ? ? 例如：3 , 5 , 6 , 1 , 2? 、
? ? ? ? 1）.? 第一次，将 5 和 0 入栈，注意这里是下标，即区间，然后排序，得出序列 2，1 , 3 , 6 , 5，得到中位数。
? ? ? ? 2）.?以此可以划分区间【0,1】和【3,4】。再次出栈，取出区间进行排序。
? ? ? ? 3）. 如果两端还能继续划分满足条件，就入栈，这里不满足条件。栈中剩下3 和 4 ，再次出栈，进行排序，直至栈为空。
7. 归并排序
基本思想：
??????归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
时间复杂度：
? ? ? ? 最坏情况：O(N * logN)
? ? ? ? 平均情况：O(N * logN)
? ? ? ? 最坏情况：O(N * logN)
? ? ? ? 对于归并排序，每次都需要递归值logN层，每层总共有N个节点，所以时间复杂度为N * logN
代码展示：
void _MergeSort(int* a, int begin, int end,int* temp)
{
if (begin >= end)
{
return;
}
//分割
int mid = begin + (end - begin) / 2;
_MergeSort(a, begin, mid,temp);
_MergeSort(a, mid + 1, end,temp);
//合并
int i = begin;
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
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 size)
{
//创建辅助空间
int* temp = (int*)malloc(sizeof(int) * size);
//排序
_MergeSort(a, 0, size - 1, temp);
free(temp);
}特性总结：
排序算法复杂度分析 及 稳定性分析：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！