[零食时间]C语言 排序算法，详细版讲解，硬核推荐！！！
排序、就是根据排序码的递增或者递减序列把数据元素依次排列起来，使一组任意排列的元素变为一组按其排序码线性有序的元素。
排序是《数据结构》这门大学计算机必修课中非常基础但是非常重要的知识点
常见的排序之间关系如下：
排序相关描述
排序分类：若排序过程中，所有的文件都是放在内存中处理的，不涉及数据的内外存交换，则称该排序算法是内部排序算法; 若排序过程中涉及内外存交换，则是外部排序。内部排序适合小文间，外部排序适用于不能一次性把所有记录放入内存的大文件。常见的分类算法还可以根据排序方式分为两大类：比较排序和非比较排序。
排序算法的稳定性：若排序对象中存在多个关键字相同的记录，经过排序后，相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的，若次序发生变化(哪怕只有两条记录之间)，则该排序方法是不稳定的。关于哪些算法是稳定的，哪些不稳定，下面会详细介绍。
时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n) 的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)) ，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
空间复杂度：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，它是问题规模n nn的函数，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1)。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息，需要辅助空间的大小随着n的增大线性增大。
各大排序算法的时间复杂度、空间复杂度及稳定性见下表：
一、直接插入排序（Insertion Sort)
基本思想
将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列，将无序数列中的元素逐次插入到有序数列中，从而获得最终的有序数列。
算法流程
1. 初始时， a[0]自成一个有序区， 无序区为a[1,...,n−1] 令i=1;
2. 将a[i]并入当前的有序区a[0,...,i−1];
3. i+并重复步骤2，直到i=n−1, 排序完成。
详细描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2
复杂度分析：
第1个元素，需要进行 0 次比较;
第2个元素，需要进行 1 次比较;
第3个元素，需要进行 2 次比较;
第n个元素，需要进行n-1次比较;
所以插入排序的时间复杂度是O(n^2)，空间复杂度是O(1)，稳定。
算法代码：
//直接插入法一void InsertSort1(int a[], int n){int i, j;for(i=1; i<n; i++)if(a[i] < a[i-1]){int temp = a[i]; //保存要比较的值for(j=i-1; j>=0 && a[j]>temp; j--) //从后向前查找待插入位置a[j+1] = a[j]; //挪位a[j+1] = temp; //复制到插入位置}}//直接插入法二：用数据交换代替法一的数据后移(比较对象只考虑两个元素)void InsertSort2(int a[], int n){for(int i=1; i<n; i++)for(int j=i-1; j>=0 && a[j]>a[j+1]; j--)Swap(a[j], a[j+1]);}void Swap(int a,int b){int temp;temp=a;a=b;b=temp;}
拓展（折半插入排序）
仅适用于顺序存储的线性表
直接插入排序是边比较，边移动元素；
折半插入排序是先折半查找到插入位置，再统一移动元素
void ZhebanInsertSort(int a[],int n){int i,j,low,high,mid;for(i=1;i<n;i++){temp=a[i];low=1,high=i; //设置折半查找范围while(low<=high){mid=(low+high)/2;if(a[mid]>temp)high=mid-1; //查找左半部分elselow=mid+1; //查找右半部分}for(j=i;j>=high+1;--j)a[j+1]=a[j]; //统一后移元素，空出插入位置a[high+1]=temp; //插入}}
二、希尔排序（Shell' s Sort）
希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的优化，实质是分组的简单插入排序。它与插入排序的不同之处在于，它会优先比较距离较远的元素(每次取相隔一定间隔gap的元素作为一组，在组内执行简单插入排序)。希尔排序又叫缩小增量排序（不断减小间隔gap的数组，直到gap=1）。
基本思想
希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。
算法流程
时间复杂度为O(n^{1+e})(其中0<e<1)，空间复杂度O(1)，不稳定。
算法代码:
//希尔排序法一void shellSort1(int a[],int n){int i,j,gap,temp;for(gap = n/2;gap>0;gap/=2){for(i=gap;i<n;i+=gap){temp = a[i];for(j = i-gap;j>=0&&a[j]>temp;j-=gap){a[j+gap] = a[j];}a[j+gap] = temp;}}}//希尔排序法二，和上面的直接插入排序类似，用数据交换代替法一的数据后移(比较对象只考虑两个元素)void ShellSort2(int a[], int n){int i, j, gap;//分组for(gap=n/2; gap>0; gap/=2)//直接插入排序for(i=gap; i<n; i++)for(j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap)Swap(a[j], a[j+gap]);}
三、简单选择排序（Selection Sort）
基本思想
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n−1元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
算法流程
1. 初始时，数组全为无序区a[0,...,n−1], 令i=0;
2. 在无序区a[i,...,n−1]中选取一个最小的元素与a[i]交换，交换之后a[0,...,i]即为有序区；
3. 重复步骤2，直到i=n−1，排序完成。
复杂度分析：时间复杂度为O(n^2)，空间复杂度为O(1)，不稳定
算法代码：
//选择排序,以升序为例void SelectSort(int a[],int n){int i,j,min;for(i=0;i<n-1;i++){min=i;for(j=i+1;j<n;j++){if(a[j]<a[min)min=j;}if(min!=i)Swap(a[i],a[min]);}}void Swap(int a,int b){int temp;temp=a;a=b;b=temp;}
四、堆排序（Heap Sort）
算法思想：
堆：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆：
大顶堆要求节点的元素都要大于其孩子。
小顶堆要求节点元素都小于其左右孩子。
两者对左右孩子的大小关系不做任何要求。
利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，我们通过大顶堆来实现。
基本思想：堆排序可以按照以下步骤来完成：
1.首先将序列构建称为大顶堆；（这样满足了大顶堆那条性质：位于根节点的元素一定是当前序列的最大值）
2. 取出当前大顶堆的根节点，将其与序列末尾元素进行交换；（此时：序列末尾的元素为已排序的最大值；由于交换了元素，当前位于根节点的堆并不一定满足大顶堆的性质）
3. 对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质；
4. 重复2.3步骤，直至堆中只有1个元素为止
下面是基于大顶堆的堆排序算法代码：
//堆排序方法一，主要包含2部分:创建堆；输出堆顶元素后重新调整堆//交换函数void Swap(int array, int i, int j){int tmp;tmp = array[j];array[j] = array[i];array[i] = tmp;}//创建大根堆void MaxHeapCreat(int array[], int heapSize){int i;for(i = heapSize/2; i >= 0; i--){MaxHeapify(array, heapSize, i);}/*大根堆调整*/void MaxHeapify(int array[], int heapSize, int currentNode){int leftChild, rightChild, largest;leftChild = 2*currentNode + 1;rightChild = 2*currentNode + 2;largest = currentNode;if(leftChild < heapSize && array[leftChild] > array[currentNode])largest = leftChild;if(rightChild < heapSize && array[rightChild] > array[largest])largest = rightChild;if(largest != currentNode){Swap(array, largest, currentNode);MaxHeapify(array, heapSize, largest);}}//堆排序void HeapSort(int array[],int heapSize){MaxHeapCreat(array,heapSize);//直接输出for(i = 0; i < heapSize; i++){printf("%d\t", array[i]);}}-------------------------------------------------------------------------------------------//堆排序方法二//数据交换void Swap(int *a, int* b){int temp = *a;*a = *b;*b = temp;}//构造大顶堆void heap_down(int* arr,int i, int N){int child;int temp;for(temp=arr[i]; 2*i+1<N;i=child){ //temp是当前结点的值child = 2*i+1; //当前结点i的左孩子的位置（在数组中的下标）if(child!=N-1 && arr[child+1]>arr[child]){ //child+1是当前结点的右孩子的位置，判断右孩子是否大于左孩子child++;}if(temp<arr[child]){ //判断根结点是否小于它的左右两个跟结点，如果小于，则交换大的为根结点arr[i]=arr[child];arr[child]=temp;}else{break;}}}//堆排序void heap_Sort(int *arr, int length){int i;//从length/2到0依次遍历，最终得到的数组是一个大顶堆//最后叶子结点2×i+2=length,i=length/2-1是最后一个父节点for(i=length/2;i>=0;i--){heap_down(arr, i, length);}for(i=length-1;i>0;i--){Swap(&arr[0],&arr[i]); //交换最大值a[0]到队列末尾heap_down(arr,0,i); //执行去掉最大值的[0~n-1]个元素的大顶堆，}}//打印元素void printArr(int *arr,int length){for(int i=0;i<length;i++){printf("%d\n",arr[i]);}}int main(){int arr[]={3,5,2,10,8,9,6,4,7,19,5,43,56,3,24,98,76,123,456,76,432,987,12};int length = sizeof(arr)/sizeof(int);heap_Sort(arr,length);printArr(arr,length);return 0;}
五、冒泡排序（Bubble Sort）
基本思想
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。每一趟排序后的效果都是讲没有沉下去的元素给沉下去。
算法流程 （递增为例）
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
所以冒泡排序的时间复杂度是O(n^2)。空间复杂度是 O(1) ，稳定 。
算法代码：
//冒泡排序void BubbleSort(int a[], int n){int i, j;for(i=0; i<n; i++){bool flag=false; //表示本趟冒泡是否发生交换的标志for(j=1; j<n-i; j++){ //j的起始位置为1，终止位置为n-iif(a[j]<a[j-1]){Swap(a[j-1], a[j]);flag=true;}}if(flag==false) //未交换，说明已经有序，停止排序return;}}
拓展 （冒泡排序的改进 ---- 鸡尾酒排序）
鸡尾酒排序与冒泡排序的不同处在于排序时是以首尾双向在序列中进行排序。
先对数组从左到右进行升序的冒泡排序；
再对数组进行从右到左的降序的冒泡排序；
以此类推，持续的、依次的改变冒泡的方向，并不断缩小没有排序的数组范围；
鸡尾酒排序的优点是能够在特定条件下（如集合中大部分元素有序），减少排序的回合数。
实现鸡尾酒排序需要分别定义一个从最左边开始的index_left和从最右边开始的index_reight，当两个index相等的时候循环结束。
//鸡尾酒排序void CocktailSort(int a[], int n){int left = 0, right=n-1;while(left<right){for(int i=left;i<right-1;i++){ //从前往后排if(a[i]>a[i+1]){Swap(a[i],a[i+1]);}right-=1;for(int j=right;j>left;j--){ //从后往前排if(a[j]<a[j-1]){Swap(a[j],a[j-1]);}}left+=1;}}}
六、快速排序（Quick Sort）
快速排序是目前所有内部排序算法中平均性能最优的排序算法。
基本思想
快速排序算法的基本思想为分治思想。
1. 先从数列中取出一个数作轴值（基准数）pivot；
2. 根据基准数将数列进行分区，小于基准数的放左边，大于基准数的放右边；
3. 重复分区操作，知道各区间只有一个数为止。
算法流程（递归+挖坑填数）
1. i=L，j=R，将基准数挖出形成第一个坑a[i]；
2. j−−由后向前找出比它小的数，找到后挖出此数a[j]填到前一个坑a[i]中；
3. i++从前向后找出比它大的数，找到后也挖出此数填到前一个坑a[j] 中；
再重复2,3，直到i=j，将基准数填到a[i]。
复杂度分析：时间复杂度为 O(nlog_{2}^{n})，空间复杂度为O(log_2^n)，不稳定。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法代码：
//快速排序void QuickSort(int a[],int left,int right){if(left<right){int i=left,j=right；int base=a[left]; //基准while(i<j){while(i<j&&a[j]>=base) //从右往左找小于base的元素j--;if(i<j)a[i++]=a[j];while(i<j&&a[i]<base) //从左往右找大于base的值i++;if(i<j)a[j--]=a[i];}a[i]=base; //将基准base填入最后的坑中QuickSort(a,left,i-1); //递归调用，分治QuickSort(a,i+1,right);}}
七、归并排序（Merge Sort）
归并概念：将两个的有序数列合并成一个有序数列，我们称之为"归并"（二路归并）。
基本思想
归并（Merge）排序算法采用分治策略，将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
复杂度分析：时间复杂度为O(nlogn2) ，空间复杂度为O(n) ，稳定。
算法代码：
void print(int a[], int n){//归并排序思想ElemType *b = (ElemType *) malloc ((n+1)*sizeof(ElemType)); //带排序表有n个记录void Merge(ElemType a[],int low,int mid,int high){//表a中两段a[low,...,mid]和a[mid+1,...,high]各自有序，将其合并成一个有序表for(int k=low;k<=high;k++)b[k]=a[k]; //将a中元素复制到辅助数组b中for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){if(b[i]<=b[j]) //比较b的左右两段中的元素a[k]=b[i++]; //将较小值复制到a中elsea[k]=b[j++];}while(i<=mid) //若左半部分表未检测完，复制a[k++]=b[i++];while(j<=high) //若右半部分表未检测完，复制a[k++]=b[j++];}void MergeSort(ElemType a[],int low,int high){if(low<high){int mid=(low+high)/2; //从中间划分2个子序列MergeSort(a,low,mid); //对左侧子序列进行递归排序MergeSort(a,mid+1,high); //对右侧子序列进行递归排序Merge(a,low,mid,high); //归并}}-------------------------------------------------------------------------------------------//递归排序的完整实现//合并两个有序序列（即归并）// A：待合并的序列（含两个子序列，排在一起）// Temp：辅助空间// L: 左边序列起点下标// R: 右边序列起点下标，// RightEnd：右边序列终点下标void Merge(int A[], int Temp[], int L, int R, int RightEnd){int LeftEnd = R-1;int p=L,i;int num=RightEnd-L+1;//先合并最短序列的长度的个数个元素while(L<=LeftEnd&&R<=RightEnd){if(A[L]<=A[R])Temp[p++]=A[L++];elseTemp[p++]=A[R++];}//判断如果是左侧序列还有剩余while(L<=LeftEnd)Temp[p++]=A[L++];//判断如果是右侧序列还有剩余while(R<=RightEnd)Temp[p++]=A[R++];// 将辅助空间中的值拷贝到原列表中，完成排序for(i=0;i<num;i++,RightEnd--)A[RightEnd]=Temp[RightEnd];}//递归拆分，递归归并void m_sort(int* arr, int* temp, int L, int right_end){int center;if(L<right_end){center = (L+right_end)/2;m_sort(arr,temp,L,center);m_sort(arr,temp,center+1,right_end);Merge(arr,temp,L,center+1,right_end);}}//归并排序void merge_Sort(int* arr,int length){int *temp=(int* )malloc(length*sizeof(int)); //申请辅助空间if(temp==NULL){return;}m_sort(arr,temp,0,length-1);free(temp);temp=NULL;}//打印元素void printArr(int *arr,int length){for(int i=0;i<length;i++){printf("%d\n",arr[i]);}}int main(){int arr[10]={3,5,2,10,8,9,6,4,7,1};int length = sizeof(arr)/sizeof(int);length = 10;merge_Sort(arr,length);printArr(arr,length);return 0;}
八、基数排序(Radix Sort)
基数排序过程无须比较关键字，而是通过**“分配”和“收集”**过程来实现排序。
基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
复杂度分析 : 时间复杂度为O(d(n+r))，空间复杂度为O(r)，d 为位数，r为基数，稳定。
算法代码：
//求数字位数int bit_num(int num){if(num/10==0){return 1;}return 1+bit_num(num/10);}//求序列最大值int max_list(int *arr, int length){int max_num = arr[0];for(int i=1;i<length;i++){if(arr[i]>max_num){max_num = arr[i];}}return max_num;}//找到一个num从低位到高位的第pos位的数据，数据最右侧最低位pos=1int get_num_pos(int num, int pos){if(pos<=0){return -1;};int pow_num = 1;for(int i=0;i<pos-1;i++){pow_num*=10;}return (num/pow_num)%10;}//基数排序void base_Sort(int* arr, int length){int max_num, key_num;int *base_arr[10]; //十进制的10个桶max_num = max_list(arr,length);key_num = bit_num(max_num);for(int i=0; i<10;i++){base_arr[i]=(int *)malloc(sizeof(int)*(length+1));base_arr[i][0] = 0; //桶中第一个位置记录桶中元素的数量}for(int pos = 1; pos<= key_num;pos++){ //需要执行最大位数次for(int i=0;i<length;i++){int num = get_num_pos(arr[i],pos);int index = ++base_arr[num][0];base_arr[num][index]=arr[i];}for(int i=0,j=0;i<10;i++){for(int k=1; k<=base_arr[i][0];k++){arr[j++] = base_arr[i][k];}base_arr[i][0]=0;}}}//打印元素void printArr(int *arr,int length){for(int i=0;i<length;i++){printf("%d\n",arr[i]);}}int main(){int arr[] ={3,5,7,2,1,0,4,65,7,89,5,3,2,5,45,3,2,54,4,543,3,33,2,34,45,5};int length = sizeof(arr)/sizeof(int);base_Sort(arr,length);printArr(arr,length);return 0;}