排序算法-总结（c语言）

排序算法有很多种，但是我看网络上大多数都是十大经典排序算法，分别有：

冒泡排序

1. 算法步骤

2.代码

选择排序

1. 算法步骤

2.代码

插入排序

1. 算法步骤

2.图解（源自我主页文章）

3.代码

希尔排序

1.算法步骤

2.图解编辑

3.代码

归并排序

1.算法步骤（参考菜鸟）

2.图解

堆排序

1. 算法步骤（参考菜鸟）

2.图解（动图源于菜鸟）

3.代码（第一段为自己写的更方便理解，第二段源于菜鸟更简洁）

快速排序

思路

图解

基数排序

图解

代码：

桶排序和计数排序

名称	时间复杂度	稳定性
冒泡排序	O( $n^2$ )	稳定
选择排序	O( $n^2$ )	不稳定
插入排序	O( $n^2$ )	稳定
希尔排序	O( $n^2$ )	不稳定
归并排序	O( $n*logn$ )	稳定
堆排序	O( $n*logn$ )	不稳定
快速排序	O( $n*logn$ )	不稳定
计数排序	O( $n+k$ )	稳定
基数排序	O( $n+k$ )	稳定
桶排序	O( $n+k$ )	稳定

时间复杂度我看网上说法不一也不一定准确。

稳定性是指例如6 8 9 0 5 5 7 这种有重复数字的数组进行排序时能不能分辨哪个5排在前面。

这十种排序算法并没有都完全学习，但是大概内部分为了几种分类想法，

1.冒泡排序，选择排序，堆排序，这三种排序方法比较相像，其具体思想就是找到最大值然后将最大值（最小值)放在特定的位置，然后再寻找剩余数中的最大值最小值。

2.桶排序，计数排序，基数排序，这三种算法是比较相像，其具体思想都超脱于一种桶的构型。就是将符合一定条件的数放在一起。但对桶的使用方法上有明显差异。

2.1基数排序：根据键值的每位数字来分配桶；

2.2计数排序：每个桶只存储单一键值；

2.3桶排序：每个桶存储一定范围的数值；

然后快排，希尔，归并，插入这四种算法的处理方式都比较特别

快排和归并排序都是一种基于分治思想的排序算法。

有的文章说希尔算法是插入排序的一种改进版，确实比较像。下面我来具体总结，不是所有的我都会总结。有的算法我会略过。

另外顺便一提，这几种算法中，只有堆排序，归并排序，快排算法这三种到达nlogn级别的排序算法，其中只有归并排序最稳定。但是平均最快的还是快排算法，当然可能快排不是最快的，可能有其他更优秀的算法，但是目前为止我没接触到。

我会从简至难来分析。

冒泡排序

冒泡排序是一种很简单的排序算法，是一种比较排序算法。

具体思想就是利用双循环，大循环为循环数据，小循环为筛选数据，每一个大循环都回将一个剩余最大数，或剩余最小数归位。

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。（因为前面的都排好了，所以最后一个不用排了。）

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.代码

#include <stdio.h>
#include <string.h>
void bubble_sort(int a[], int len)
{int i, j, temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (a[j] > a[j + 1]){temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}
}
int main()
{int a[] = { 20,40,32,67,40,20,89,300,400,15 };int len=sizeof(a)/sizeof(a[0]);bubble_sort(a, len);int i;for (i = 0; i < len; i++)printf("%d ", a[i]);return 0;
}

选择排序

选择排序也是一种比较排序算法。

其具体思路就是，每次找到对应的最大的（最小的）数据放在合适的位置。

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

2.代码

#include <stdio.h>
#include <string.h>
void swap(int *a,int *b)
{int temp = *a;*a = *b;*b = temp;
}
void selection_sort(int a[], int len)
{int i,j;for (i = 0 ; i < len - 1 ; i++){int min = i;//设定对应位置for (j = i + 1; j < len; j++)if (a[j] < a[min]){min = j;}swap(&a[min], &a[i]);//交换元素}
}
int main()
{int n;scanf("%d",&n);int i,j;int a[n];for (i=0;i<n;i++){scanf("%d",&a[i]);}selection_sort(a,n);for (i=0;i<n;i++){printf("%d ",a[i]);}return 0;
}

插入排序

插入排序也是一种比较排序算法。

其具体思想就是将数组分为两个部分，一部分为有序数组，一部分为无序数组，具体做法就是不断的从无序数组中取出数据插入有序数组中。

1. 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2.图解（源自我主页文章）

3.代码

#include <stdio.h>
#include <string.h>
void inser_sort(int a[], int len)
{//因为我们将第一个元素视为已经排好顺序的元素所以i应该从1开始//j=i-1  i从左往右移动，j从右往左移动.//i指向未排序数组，j指向已排序数组的最后一个位置int i,j,key;//key用于暂时存储数值for (i=1; i<len; i++){key = a[i];j=i-1;while((j>=0) && (a[j]>key)){a[j+1] = a[j];//已排序数组后移j--;}a[j+1] = key;}
}
int main()
{int n;scanf("%d",&n);int i,j;int a[n];for (i=0;i<n;i++){scanf("%d",&a[i]);}inser_sort(a,n);for (i=0;i<n;i++){printf("%d ",a[i]);}return 0;
}

希尔排序

希尔排序，类似于插入排序，可以说是插入排序的一个升级版。

其基本思想有点类似于 '分治' ，我的理解是这样的，希尔排序会从最开始以数组之间两两对比进行分组，先分出len/2个分组，每个分组只对比两个数，有点像分治的分而治之的思想，然后再依次每次分组对半折，每次排序的增量开始增加，一直到最后增量为1时，就完成了排序。

1.算法步骤

初始时，有一个大小为 10 的无序序列。

（1）在第一趟排序中，我们不妨设分组 gap= N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

（2）接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap1 = gap / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

（3）按照直接插入排序的方法对每个组进行排序。

（4）在第三趟排序中，再次把 gap 缩小一半，即gap2 = gap1 / 2 = 1。这样相隔距离为 1 的元素组成一组，即只有一组。

（5）按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

2.图解

3.代码

#include <stdio.h>
#include <malloc.h>void shellSort(int *a, int len); int main(void)
{int i, len, * a;printf("请输入要排序的数的个数：");scanf("%d",&len);a = (int *)malloc(len * sizeof(int)); printf("请输入要排序的数：\n");for (i = 0; i < len; i++)   {scanf("%d",&a[i]);}shellSort(a, len); printf("希尔排列后为（升序）：\n");for (i = 0; i < len; i++) {printf("%d ",a[i]);}free(a);printf("\n");return 0;
}void shellSort(int *a, int len)
{int i, j, k, tmp, gap;  // gap 为步长for (gap = len / 2; gap > 0; gap /= 2)   {for (i = 0; i < gap; ++i)  {for (j = i + gap; j < len; j += gap)   {tmp = a[j];  k = j - gap; while (k >= 0 && a[k] > tmp){a[k + gap] = a[k]; k -= gap;}a[k + gap] = tmp;}}}
}

归并排序

归并排序是一种基于分治思想的排序算法，归并排序主要有两个操作，分别是归和并这两种操作，归就是递归，并就是合并的意思。

其具体思想就时不断对半分数组，一直到每个数据都是一个单独的节点（类比说法）。然后再由节点不停合并排序，一直到最后又重新合并成一个数组，是不是跟上面的希尔排序很像。

1.算法步骤（参考菜鸟）

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

2.图解

第一二张图均为整体解释，图三为递归分析。

#include<stdio.h>
void merge(int a[],int l,int r,int mid)
{int aux[r-l+1],i,j,k;for(k=l; k<=r; k++)aux[k-l]=a[k];i=l;//i指向左边数组的第一个位置j=mid+1;//j指向右边数组的第一个位置for(k=l; k<=r; k++){if(i>mid)//判断一下左边数组优先于右边数组排序完的情况{a[k]=aux[j-l];j++;}else if(j>r)//判断右边数组优先左边数组排序完的情况{a[k]=aux[i-l];i++;}//下面的判断语句就是判断谁小就先排。else if(aux[i-l]>aux[j-l]){a[k]=aux[j-l];j++;}else{a[k]=aux[i-l];i++;}}
}void merge_sort(int a[],int l,int r)
{if(l>=r)return ;int mid=(l+r)/2;//mid为数组的中间那个序号merge_sort(a,l,mid);merge_sort(a,mid+1,r);merge(a,l,r,mid);}int main()
{int n,i;scanf("%d",&n);int a[n+1];for(i=0; i<n; i++)scanf("%d",&a[i]);//此处的n-1是为了对应数组的序号，比如排序10个数,10/2=5，但是计算机中数组计数从0开始//所以序号应该是4才对merge_sort(a,0,n-1);for(i=0; i<n; i++)printf("%d ",a[i]);return 0;
}

堆排序

堆排序是一种基于完全二叉树的排序算法，同时利用了堆的概念，顾叫堆排序。

其基本思想就是借助大顶堆和小顶堆的特性，不断的将数组中最大值或最小值抽出，然后重构堆。

如果想看详解我的主页有。传送门：https://blog.csdn.net/weixin_53020123/article/details/127343689?spm=1001.2014.3001.5502

1. 算法步骤（参考菜鸟）

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

2.图解（动图源于菜鸟）

3.代码（第一段为自己写的更方便理解，第二段源于菜鸟更简洁）

我将菜鸟的代码重新注释了一下。

自创

#include<stdio.h>void pile(int *a,int len)
{int i=0,j=0,temp=0;for (i=len;i>0;i--)//堆排序结构（通过i做减法让每次交换后的最后节点不进入重构）{maxtree(a,i);//构建大顶堆结构Swap(a,i);//交换数据}
}
void Swap(int *a,int len)//交换根节点和每次重构后树的最后一个节点的值
{int temp=0;temp=a[0];a[0]=a[len-1];a[len-1]=temp;
}
void maxtree(int *a,int len)//构建大顶堆
{int i=0,temp=0;for (i=len/2-1;i>=0;i--)//从最后一个非叶子节点开始判断是否符合大顶堆特点{if((2*i+1)<len && a[i]<a[2*i+1])//左子树大于根节点{temp=a[i];a[i]=a[2*i+1];a[2*i+1]=temp;//根节点与左子树交换值//这个if语句进行判断交换后的左子树的子节点是否符合大顶堆标准//不符合则进行重构if((2*(2*i+1)+1<len && a[2*i+1]<a[2*(2*i+1)+1]) || (2*(2*i+1)+2<len && a[2*i+1]<a[2*(2*i+1)+2])){maxtree(a,len);}}if((2*i+2)<len && a[i]<a[2*i+2])//右子树大于根节点{temp=a[i];a[i]=a[2*i+2];a[2*i+2]=temp;//根节点与右子树交换值//这个if语句进行判断交换后的右子树的子节点是否符合大顶堆标准//不符合则进行重构if((2*(2*i+2)+1<len && a[2*i+2]<a[2*(2*i+2)+1]) || (2*(2*i+2)+2<len && a[2*i+2]<a[2*(2*i+2)+2])){maxtree(a,len);}}}
}
int main()
{int n,i;scanf("%d",&n);int a[n+1];for(i=0; i<n; i++)scanf("%d",&a[i]);pile(a,n);//调用堆排序函数for (i=0;i<n;i++){printf("%d ",a[i]);}return 0;
}

菜鸟

#include <stdio.h>
#include <stdlib.h>void swap(int *a, int *b) {int temp = *b;*b = *a;*a = temp;
}void max_heapify(int arr[], int start, int end) {int dad = start;//指向对应的节点int son = dad * 2 + 1;//指向对应节点的左子节点while (son <= end) { // 子节点存在才进行判断if (son + 1 <= end && arr[son] < arr[son + 1])//判断左子节点大还是右子节点大，son指向的是左子节点，所以右子节点就是son+1son++;if (arr[dad] > arr[son]) //判断父节点是否比子节点大，父节点大则跳出return;else {//若是子节点大，则交换数据并且判断其对应的子分支是否符合大顶堆标准swap(&arr[dad], &arr[son]);dad = son;//父节点变换为交换元素的子节点位置son = dad * 2 + 1;//对应更新子节点位置}}
}void heap_sort(int arr[], int len) {int i;// 初始化，i从最后一个非叶子节点开始调整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完成for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len = (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

快速排序

快速排序是我写过两次的排序(且我写过两种代码，文中将会出现我写的第三种，我感觉第三种即文中代码更容易记忆)，但是总感觉都没写好也许是我文采的问题，总感觉有些表达不到位。快排也是和归并一样，均为递归和分治思想的产物。

思路

快排的思想很简单，就是在数组中设定一个基准数，并且设定基准数的左边是比基准数小的数，右边是比基准数大的数。然后找到基准数左边比基准数大的和基准数换位置，然后从基准数右边找到比基准数小的和基准数换位置，然后一直找完后，将基准数的左右两边分别送入递归，重复操作。

因为快排的过程比较多，所以不方便作图，所以图解是从菜鸟上找的。

图解

代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void sort(int *aim,int low,int high)
{int i,j,guard;i=low;j=high;guard=aim[low];if(i>j){return ;}while(i<j){while(i<j && aim[j]>=guard)//找基准数右边比基准数小的数{j--;}if(i<j && aim[j]<guard)//与基准数交换位置{int temp;temp=aim[i];aim[i]=aim[j];aim[j]=temp;i++;}while(i<j && aim[i]<=guard)//找基准数左边比基准数大的数{i++;}if(i<j && aim[i]>guard)//交换位置{int temp;temp=aim[i];aim[i]=aim[j];aim[j]=temp;j--;}sort(aim,low,i-1);sort(aim,i+1,high);}
}
int main()
{int i,j,t;
//读入数据int a[10000];int n;int num=0;for (i=0;i<=10000;i++){a[i]=0;}scanf("%d",&n);for(i=1; i<=n; i++)scanf("%d",&a[i]);sort(a,0,n);
//输出排序后的结果for(i=1; i<=n; i++){if(a[i]!=a[i-1]){num=num+1;}}printf("%d\n",num);for(i=1; i<=n; i++){if(a[i]!=a[i-1]){printf("%d ",a[i]);}}return 0;
}

当然C语言中，很多语言中都含有快排的调用包。见下面代码中

#include <stdio.h>
#include <string.h>
#include <stdlib.h>int s[10000], n, i;
//从小到大
int cmp(const void *a, const void *b)
{return (*(int *)a - *(int *)b);
}
//从大到小
int cmp1(const void *a, const void *b)
{return (*(int *)b-*(int *)a );
}
int main()
{scanf("%d", &n);for(i = 0; i < n; i++)scanf("%d", &s[i]);qsort(s, n, sizeof(s[0]), cmp);printf("从小到大排列");for(i = 0; i < n; i++)printf("%d ", s[i]);printf("\n");qsort(s, n, sizeof(s[0]), cmp1);printf("从大到小排列");for(i = 0; i < n; i++)printf("%d ", s[i]);return 0;
}

基数排序

基数排序是一种基于桶构型的算法。

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序有两种思路，从高位往低位排，和从低位往高位排，本文主要是从低位往高位排。

图解

代码：

#include <stdio.h>
#include <string.h>//取整数M的第i位数
int GetDigit(int M, int i)
{while(i > 1){M /= 10;i--;}return M % 10;
}
//获取最大数位值
int GetMaxNumber(int *num,int len)
{int i=0,max=0;for (i=0; i<len; i++)//查找最大数{if(num[i]>max){max=num[i];}}int number=0;while(max>0)//获取最大数位数{max=max/10;number++;}return number;
}
// 基数排序
void cardinalSort(int *num, int len)
{int i, j, k, l, digit;int D;D=GetMaxNumber(num,len);int allot[10][len];//0-9十个数为10个桶。// 初始化memset(allot, 0, sizeof(allot));// 遍历每个数位for (i = 1; i <= D; i++){// 遍历每个数for (j = 0; j < len; j++){// 获取当前数据 num[j] 的 第i位数digit = GetDigit(num[j], i);k = 0;while (allot[digit][k]!=0)//确保当前位置没有数再确定存储位置{k++;}// 将num[j]存储到二维数组中对应的位置allot[digit][k] = num[j];}// 将分配数组的数据收集到原数组中//就是排序l = 0;for (j = 0; j < 10; j++){k = 0;// 获取数组allot的每一行的数据 到 原数组中while (allot[j][k]!=0){num[l++] = allot[j][k++];}}printf("对第%d位排序:\n",i);for(l=0;l<10;l++){printf("数位为%d   ",l);for(j=0;j<len;j++){printf("%-5d  ", allot[l][j]);}printf("\n");}printf("\n");printf("排序第%d位后的数组为:\n",i);for(l=0;l<len;l++){printf("%d ",num[l]);}printf("\n");printf("\n");memset(allot, 0, sizeof(allot));}
}int main()
{int N,i=0;scanf("%d",&N);int num[N];for (i=0; i<N; i++){scanf("%d",&num[i]);}printf("原始数组为: ");for (i=0; i<N; i++){printf("%d  ",num[i]);}printf("\n");cardinalSort(num, N);printf("排序完成后数组为：\n");for (i = 0; i < N; i++){printf("%d ", num[i]);}printf("\n");return 0;
}

桶排序和计数排序

桶排序和计数排序，我查阅资料之下发现网上对这两种排序说法不一但是主要就是两种做法。

一种就是找到数组中的最大值，然后创建一个最大值这么长的数组，然后将数据依次存入对应的序号中，就像一个数组中初见了两次5，那么新创建的数组中的序号为5的数组值就为2.

另一种就是像上文的基数排序一样，将在一定范围内的数据放进同一个数组，进行排序操作，然后依次输出就完成了排序。我只做了第一种思想的程序。如下

#include <stdio.h>
#include <stdlib.h>int main()
{int num,t,i;int count = 0;scanf("%d",&num);int a[num];int max=0;for(i=0;i<num;i++){scanf("%d",&a[i]);if(a[i]>max){max=a[i];//找最大值}}int aim[max];//创建数组for (i=0;i<=max;i++){aim[i]=0;}for(i=0;i<num;i++){t=a[i];if(aim[t]==0){aim[t] = t;count++;//将数对应的序号里的数据加1}}printf("%d\n",count);for(i=0;i<=max;i++){if(aim[i]!=0){printf("%d ",aim[i]);//输出排序}}return 0;
}

注：文中的大部分内容均可在我的主页中的文章中找到。

并且非我做的图我在原文章中以标注。

大部分是引用的菜鸟中的

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html