【内部排序八大排序算法】C语言详解 -- 稳定不稳定区分，最好最坏时间复杂度

• 概述
• • 算法优劣术语
  • • 稳定性与不稳定性
    • 时空复杂度
  • 时间空间复杂度总结对比
• 插入排序—直接插入排序(Straight Insertion Sort)
• 插入排序—希尔排序（Shell`s Sort）
• 选择排序—简单选择排序（Simple Selection Sort）
• 选择排序—堆排序（Heap Sort）
• 参考博客

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

算法优劣术语

稳定性与不稳定性

稳定：若果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：若果a原本在b前面，而a=b，排序之后a可能会出现在b的后面。
稳定性意义的探讨

• 如果只是简单的进行数字的排序，那么稳定性将毫无意义。

• 如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）

• 如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。

• 除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）

时空复杂度

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行一个程序所需要内存的大小。
一般情况下，当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

时间空间复杂度总结对比

插入排序—直接插入排序(Straight Insertion Sort)

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 算法描述：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

• 要点：设立哨兵，作为临时存储和判断数组边界之用。
  直接插入排序示例:
  

• 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

• 代码

void insert_sort(int array[],unsigned int n){    int i,j;    int temp;    for(i = 1;i < n;i++)    { temp = array[i]; for(j = i;j > 0&& array[j - 1] > temp;j--) {     array[j]= array[j - 1]; } array[j] = temp;    }}

• 算法复杂度
  
  其他的插入排序有二分插入排序，2-路插入排序。

插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序，但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
  基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序”时 ，再对全体记录进行依次直接插入排序。

• 算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

  • 按增量序列个数k，对序列进行k 趟排序；

  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

• 示例：
  

• 要点：
  我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数
  即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，
  然后再用一个**较小的增量（d/2）**对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

• 代码

#include#include #define MAXNUM 10 void main(){    void shellSort(int array[],int n,int t);//t为排序趟数    int array[MAXNUM],i;    for(i = 0;i < MAXNUM;i++) scanf("%d",&array[i]);    shellSort(array,MAXNUM,int(log(MAXNUM + 1) / log(2)));//排序趟数应为log2(n+1)的整数部分    for(i = 0;i < MAXNUM;i++) printf("%d ",array[i]);    printf("\n");} //根据当前增量进行插入排序void shellInsert(int array[],int n,int dk){    int i,j,temp;    for(i = dk;i < n;i++)//分别向每组的有序区域插入    { temp = array[i]; for(j = i-dk;(j >= i % dk) && array[j] > temp;j -= dk)//比较与记录后移同时进行     array[j + dk] = array[j]; if(j != i - dk)     array[j + dk] = temp;//插入    }} //计算Hibbard增量int dkHibbard(int t,int k){    return int(pow(2,t - k + 1) - 1);} //希尔排序void shellSort(int array[],int n,int t){    void shellInsert(int array[],int n,int dk);    int i;    for(i = 1;i <= t;i++) shellInsert(array,n,dkHibbard(t,i));} //此写法便于理解，实际应用时应将上述三个函数写成一个函数。

增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

• 算法复杂度
  

选择排序—简单选择排序（Simple Selection Sort）

• 算法描述：
  首先，找到数组中最小（大）的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小（大）元素那么它就和自己交换）。再次，在剩下的元素中找到最小（大）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

• 要点：
  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  重复第二步，直到所有元素均排序完毕。

• 示例：
  

• 代码：

void select_sort(int *a,int n){    register int i,j,min,t;    for(i = 0;i < n-1;i++)    { min = i;//查找最小值 for(j = i + 1;j < n;j++)     if(a[min] > a[j])  min = j;//交换 if(min != i) {     t = a[min];     a[min] = a[i];     a[i] = t; }    }}

• 算法复杂度:
  

选择排序—堆排序（Heap Sort）

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

• 基本思想：堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足
  

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，**根结点（堆顶元素）的值是最小(或最大)**的。如：

大顶堆序列：（96, 83,27,38,11,09)小顶堆序列：（12，36，24，85，47，30，53，91）

• 算法描述：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

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

• 代码：

//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度//本函数功能是：根据数组array构建大根堆void HeapAdjust(int array[],int i,int nLength){    int nChild;    int nTemp;    for(; 2 * i + 1 < nLength;i = nChild)    { //子结点的位置=2*（父结点位置）+1 nChild = 2 * i + 1; //得到子结点中较大的结点 if(nChild < nLength - 1 && array[nChild + 1] > array[nChild]) ++nChild; //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if(array[i] < array[nChild]) {     nTemp = array[i];     array[i] = array[nChild];     array[nChild] = nTemp;  } else break; //否则退出循环    }}//堆排序算法void HeapSort(int array[],int length){    int i;    //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素    //length/2-1是最后一个非叶节点，此处"/"为整除    for(i = length / 2 - 1;i >= 0;--i)    HeapAdjust(array,i,length);    //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素    for(i = length - 1;i > 0;--i)    { //把第一个元素和当前的最后一个元素交换， //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的 array[i] = array[0] ^ array[i]; array[0] = array[0] ^ array[i]; array[i] = array[0] ^ array[i]; //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 HeapAdjust(array,0,i);    }}int main(){    int i;    int num[]={9,8,7,6,5,4,3,2,1,0};    HeapSort(num,sizeof(num)/sizeof(int));    for(i = 0;i < sizeof(num) / sizeof(int);i++)    { printf("%d ",num[i]);    }    printf("\nok\n");    return 0;}

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式： 

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

• 算法复杂度:
  

参考博客

稳定排序和不稳定排序
八大排序算法总结
八大排序算法
数据结构（排序算法总结）（C语言）