C语言 八大排序算法的过程图解及实现代码
目录
- 前言
- 一、插入排序
- 时间复杂度
- 空间复杂度
- 代码实现（升序）
- 二、希尔排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 三、选择排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 四、堆排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 五、冒泡排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 六、快排排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 七、归并排序
- 时间复杂度
- 空间复杂度
- 代码实现
- 八、计数排序
- 时间复杂度
- 空间复杂度
- 九、各种排序总结比较
前言
排序是数据结构中很重要的一章，先介绍几个基本概念。
- 排序稳定性：多个具有相同的关键字的记录，若经过排序，这些记录的相对次
- 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
一、插入排序
时间复杂度
最坏：-----------O(N^2)
最好：-----------O(N)
平均：-----------O(N^2)
空间复杂度
O(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 x = a[end+1];//x为待排序的值
int end = i;//从end开始往前和x依次比较
while (end >= 0)
{
if (a[end] > x)//只要当前的值大于x继续往前找
{
a[end+1] = a[end];
end--;
}
else
{
break;//跳出循环说明a[end] <= x
}
}
a[end + 1] = x;//跳出循环说明a[end] <= x，需要把x插入到end前边
}
}
那么我们可以看到，越是接近有序的数组，插入排序的效率越高（有序时对于任何一个数只需要和前边的数比较一次）。
二、希尔排序
时间复杂度
O(n^（1.3—2）)
空间复杂度
O(1)
稳定性：稳定
『 希尔排序 』(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
该方法实质上是一种『 分组插入 』方法,因为插入排序对于接近有序的数组排序效率非常高，那么希尔提出：
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
并且插入排序可以看成分组是1的希尔排序。动图如下：
因为插入排序可以看做gap==1的希尔排序，因此只需要改变插入排序中for循环的增量控制排序即可。
代码实现
void ShellSort(int* a, int n)
{
//按gap分组进行预排序
int gap = n;
while (gap>1)
{
//gap = gap / 2;
gap = gap / 3 + 1;//这里分组选每次折半或者/3都可以
for (int j = 0; j < gap; j++)//gap个组
for (int i = j; i < n - gap; i+=gap)//每个组从j开始每个增量gap
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
关于希尔排序时间复杂度证明比较复杂，取决于gap怎么取，如果按照Knuth提出的/3，来取是O(n^（1.25）- 1.6*O(n^1.25).
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
三、选择排序
时间复杂度
最坏：-----------O(N^2)
最好：-----------O(N^2)
平均：-----------O(N^2)
空间复杂度
O(1)
稳定性：不稳定
『 基本思想 』：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始（末尾）位置，直到全部待排序的数据元素排完 。如图：
代码实现
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
int mini = begin;//记录最小值下标
while (begin<end)
{
for (int i = begin; i < end; i++)
{
if (a[i] < a[mini])
{
mini = i;//更新最小值下标
}
}
Swap(&a[mini],&a[begin]);//把最小值放到左边
++begin;//左边对应起始位置++
}
}
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。
四、堆排序
时间复杂度
最坏：-----------O(N * logN)
最坏：-----------O(N * logN)
平均：-----------O(N*logN)
空间复杂度
O(1)
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
具体可见另一篇文章堆排序和TopK问题
动图：
代码实现
void Swap(int* px,int* py)
{
int t = (*px);
(*px) = (*py);
(*py)= t ;
}
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[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);
}
for (int i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
}
五、冒泡排序
时间复杂度
最坏：-----------O(N^2)
最好：-----------O(N)
平均：-----------O(N^2)
空间复杂度
O(1)
『 冒泡排序 』是大家最熟悉的也是最容易理解的排序,如下图：
『 冒泡排序基本思想 』就是每一次将相邻的数据进行『 两两比较 』，选出最大的依次比较送到右边，那么最右边就是最大值，而左边留下的自然就是小的（排升序）
-『 冒泡排序 』需要两层循环
『 内层循环 』表示一次冒泡，也就是两两比较先选出最大的放到最右边，同时注意每一次冒泡选出最大元素，那么两两比较次数-1（下一次不用比较选好的最右边）
『 外层循环 』控制的是冒泡的次数（假设数组N 个元素）也就是N-1次冒泡选出N-1个最大的元素
代码实现
初版代码如下：
//初版：
void Swap(int* px, int* py)
{
int t = (*px);
*px = (*py);
(*py) = t;
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)//外层循环
{
for (int j = 0; j < n-1-i; j++)
{
if(a[j]>a[j+1])
Swap(&a[j],& a[j + 1]);//交换
flag = 1;
}
}
}
时间复杂度分析：每一次比较次数是N-1,N-2,N-3***1.因此是N(N-1)/2
但是这种写法还是有缺陷，时间复杂度永远是O(N^2） ， 对于一个已经排好序的数组来说，还是需要N^2的复杂度，但对于有序的数组，每一次冒泡都不会进行交换因为有序，因此如果只要任何一次冒泡中没有数据交换就证明数组有序了。时间复杂度最好也可以达到0(N)。
代码优化如下：
//优化：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int flag = 0;
for (int j = 0; j < n-1-i; j++)
{
if(a[j]>a[j+1])
Swap(&a[j],& a[j + 1]);
flag = 1;
}
if (flag == 0)
break;
}
}
六、快排排序
时间复杂度
最坏：-----------O(N^2)
最好：-----------O(logN)
平均：-----------O(logN)
空间复杂度
O(logN)
『 快速排序 』是Hoare于1962年提出的一种二叉树结构的交换排序方法，其『 基本思想 』为：任取待排序元素序列中的某元素作为『 基准值 』，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。如图：
代码实现
递归写法：
// 假设按照升序对a数组中[left, right)区间中的元素进行排序
void QuickSort(int* a, int left, int right) {
if(right >= left )
return;//递归截止条件
// 按照基准值对a数组的 [left, right]区间中的元素进行划分
int keyi= partion(a, left, right);
// 划分成功后以keyi为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right]
// 递归排[left, keyi-1]
QuickSort(a, left, keyi-1);
// 递归排[keyi+1, right]
QuickSort(a, keyi+1, right);
}
递归框架写完了接下来就差partion函数的实现也就是快排的灵魂，去每一次找基准值。那么一共有三种写法如下：
hoare版本
1.首先就是要找基准值，这里你可以选最左边或最右边的值（图中是6）
2.两个指针指向头（这里选左为基准值，头指针指向第二个）和尾，基准值选左，则右指针先走，反之左指针先走。
3.左指针找到比基准值大的停下，右指针找比基准值小的停下，交换左右指针指向值
4.重复2.3动作，直到左右指针相遇，交换左指针值和基准值
左值为基准，右指针先走找比6小的：
左值为基准，右指针先走找比6小的：
交换：
最终效果：相遇交换左指针和基准值，保证了6的左边都比6小，右边比6大。
并且除此之外，由于我们看到这种算法类似于二叉树的思想排好中间再排左右子树，因此我要保证选取的随机值尽量位与中位数。所以我们采取三数取中的方法。（选取最左值最右最中间的数的中位数）效率是可以提升5%到10%的。
//三数取中
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
//int mid = left + (right - left) / 2;
int mid = left + ((right - left)>>1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int Partion(int* a, int left,int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
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]);
return left;
}
挖坑法
挖坑法就是对hoare版本的一种变形，过程如下：
初始如下：先保存基准值，基准值形成一个坑位！
左为基准，右指针先走，找到小的送到坑位，那么此刻右指针形成了新的坑位
左指针出动，找到大的继续送到坑位，左指针形成了新的坑位
指针相遇，把6写入。也保证左边比6小，右边比6大。代码如下：
//挖坑法
int Partion2(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int key = a[left];
int pivot = left;
while (left < right)
{
//右边先找小
while (left< right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
前后指针版本
顾名思义，使用两个指针，这里选取左为基准值为例，两个指针从左开始出发一个cur,一个prev。
要求：
cur指针先走，一旦找到比基准值小的就停下，++prev,并交换。
cur指针一直到头为止，最后交换prev指向值和基准值
1和2都比6小cur走一步停一步，prev++并交换，指向相等。
cur越过7和9去找小的3，此时停下，prev++指向7交换。（我们注意到prev和cur不等时prev永远是去找大的，cur是找小的，因此交换就做到把cur指向的小的往前扔，大的往后仍，）
整个过程如上，代码：
//前后指针法
int Partion3(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int prev = left, cur = left+1;
int keyi = left;
while (cur<=right)
{
if (a[cur] < a[keyi] && ++prev !=cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
小结
递归版本三种方法如上，但是递归毕竟有缺陷，就是需要不断开辟栈帧，当数据量超过10W以上时就会有栈溢出的风险。
并且递归类似二叉树的结构越往下递归调用越多，栈帧翻倍开辟，因此我们还可以去优化一下，就是当递归到左右区间比较小时，我们去控制剩下的排序用别的排序来代替它。
//优化：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if (right - left + 1 < 10)
{
//小区间优化
InsertSort(a + left , right - left + 1);
}
else
{
int keyi = Partion3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}
非递归：
非递归版本就是改变了快排的框架，用一个栈和循环来代替递归实现。依次将左右下标入栈出栈（出栈之前排序）来模拟递归。
void QuickSortNonR(int* a, int left, int right)
{
Stack st;//定义一个栈
StackInit(&st);//初始化
StackPush(&st, left);//左下标入栈
StackPush(&st, right);//右下标入栈
while (StackEmpty(&st)!=0)
{
int end = StackTop(&st);//获取栈顶元素即后入栈的右下标
StackPop(&st);//出栈
int begin = StackTop(&st);//获取栈顶元素即先入栈的左下标
StackPop(&st);//出栈
int keyi = Partion3(a, begin, end);
if (keyi + 1 < end)//相当于递归左半部分
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (keyi - 1 > begin)//相当于递归右半部分
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
}
七、归并排序
时间复杂度
最坏：-----------O(NlogN)
最好：-----------O(NlogN)
平均：-----------O(NlogN)
空间复杂度
O(N)
稳定性：稳定
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 动图演示：
归并的思想就是把先假设数组分成两个有序，对其进行筛选排序，如上图：
但是问题来了我们怎么保证数组是有序的？因此就要求我们从小区间开始对数组归并排序，对于上图中的数据，先对开始3和3归并，小的先进入到tmp数组，因此前两个就是有序，再对，5和6归并，5,6有序后，在归并3，3，5，6……以此类推
代码实现
递归写法
框架：
void MergeSort(int* a,int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);//开辟N个大小数组
if (tmp == NULL)
{
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);//进行归并操作
free(tmp);
tmp = NULL;
}
归并排序：
运用递归先不断缩小偏序区间，在递归层层退出时一遍退出，一边对不断回大的区间归并排序：
void _MergeSort(int* a, int left, int right,int* tmp)
{
if (left >= right)
{
return;//递归截止条件left >= right区间中数的个数<=0个
}
int mid = left + (right - left) / 2;//取中
_MergeSort(a, left, mid, tmp);//对左区间递归
_MergeSort(a, mid+1, right, tmp);//对右区间递归
int begin1 = left, end1 = mid;//左区间
int begin2 = mid+1, end2 = right;//右区间
int i = left;
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++];
}
for (size_t i = left; i <= right; i++)
{
a[i] = tmp[i];//把排好序[left,right]的tmp赋值给原数组
}
}
非递归
非递归的不同就是需要手动控制区间大小，也就是不断2倍扩大区间归并。
但是还需要注意就是当下标是奇数，无法分成整数个组的时候，需要考虑剩余的数，以及是否越界的问题
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i][i+gap-1] [i+gap][i+2*gap-1]
int begin1 = i, end1 = i + gap-1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int index = i;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
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++];
}
//控制越界问题三种情况
if (end1 >= n)
{
end1 = n - 1;
}
if (end1 >= n)
{
end1 = n - 1;
}
if (end1 >= n)
{
end1 = n - 1;
}
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
八、计数排序
时间复杂度
最坏：-----------O(MAX(N,范围))
最好：-----------O(MAX(N,范围))
平均：-----------O(MAX(N,范围))
空间复杂度
O(范围)
稳定性：不稳定
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
动图如下：
类似桶排序的思想，如上图，先开辟数组统计数组中某一个数出现的次数，比如2出现1次，3出现两次，那么我们直接按顺序读入开辟的数组，在原数组写1一个2，两个3以此类推……
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);
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 < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}
计数排序的特性总结：
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
九、各种排序总结比较
1. 复杂度总结
2. 性质分类
以上就是C语言 八大排序算法的过程图解及实现代码的详细内容，更多关于C语言八大排序算法的资料请关注我们其它相关文章！
相关推荐
-
c语言5个常用的排序算法实例代码
1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =
-
c语言实现的几种常用排序算法
概述 最近重新回顾了一下数据结构和算法的一些基本知识,对几种排序算法有了更多的理解,也趁此机会通过博客做一个总结. 1.选择排序-简单选择排序 选择排序是最简单的一种基于O(n2)时间复杂度的排序算法,基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小(大)值. 算法实现: void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue
-
C语言排序算法之插入排序
算法实现: 使用插入排序将下面的数字按照从小到大的顺序排列 步骤1:数组中已经排好的是{1},将9插入数组中 步骤2:数组中已经排好的是{2,9},将5插入数组中 步骤3:数组中已经排好的是{2,5,9},将4插入数组中 步骤4:数组中已经排好的是{2,4,,5,9},将8插入数组中 步骤5:数组中已经排好的是{2,4,,5,8,9},将1插入数组中 步骤6:数组中已经排好的是{1,2,4,,5,8,9},将6插入数组中 步骤7:排序完成 程序代码: #include <stdio.h> #i
-
C语言实现九大排序算法的实例代码
直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分.从无序部分中依次取出元素插入到有序部分中.过程就是遍历有序部分,实现起来比较简单. #include <stdio.h> void insertion_sort(int arr[], int array_length) { for (int i = 0; i < array_length; ++i) { int data = arr[i]; int j = 0; while (arr[j] < arr[i]) { j
-
C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)
目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第
-
C语言 八大排序算法的过程图解及实现代码
目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关
-
C语言 八大排序算法的过程图解及实现代码
目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 代码实现 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具
-
必须知道的C语言八大排序算法(收藏)
概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到
-
C/C++语言八大排序算法之桶排序全过程示例详解
基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕. 首先我们要求出一个数组的最大数然后求出他的最大位数 //求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++
-
python实现八大排序算法（2）
本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据a[1].a[2].--a[n],需将其按升序排列.首先任取数据a[x]作为基准.比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数
-
python实现八大排序算法（1）
排序 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程. 看图使理解更清晰深刻: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序
-
八大排序算法的Python实现
Python实现八大排序算法,具体内容如下 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def inser
-
C语言选择排序算法及实例代码
选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3 2 4 1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3 2 4 1(最初, m
-
C语言 奇偶排序算法详解及实例代码
C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交
-
c++ 快速排序算法【过程图解】
第一.算法描述 快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法, 快速排序算法是采用分治思想的算法,算法分三个步骤 1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个.最后一个元素或中间的元素 2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边 3.对左右两个分区重复以上步骤直到所有元素都是有排序好. 第二.算法实现 /*序列划分函数*/ int partition(int a[], int p