数据结构排序算法可以分为几大类：插入排序
1.插入排序（Insertion Sort）
插入排序又可以分为
- 直接插入排序
- 折半插入排序
- 希尔排序
1.直接插入排序(Straight Insertion Sort)
算法基本思想：从第二个记录起，逐个将每个未排序记录直接插入前面已排好序的子序列。
基于该算法思想的流程图
这里以一个具有10个元素的整型数组为例，给出直接插入排序算法的C语言实现代码，首个存储结点不存储记录，作为哨兵使用(相当于起交换作用的temp变量)，比如以数组A[n]为例，n个待排序记录用size为n+1的数组来存储，A[0]不存储记录，A[1]--A[n]存储记录元素
#include<stdio.h>
int main(){
int i,j;
int A[11]={0,34,5,3,65,24,46,1,7,83,17}; //n为10，需要设置size为n+1的数组来存储，这里默认设置初始时哨兵A[0]为0
for(i=2;i<=10;i++){ //从第一个待插入记录开始遍历，进行n-1次插入
if(A[i]<A[i-1]){ //A[i]为每次待插入的记录，A[i-1]为已排序记录的最末位元素，按升序排序时，若A[i]大于A[i+1],则说明此时不需要插入，最大元素刚好是此时的待插入记录
A[0]=A[i]; //但满足上面一行if条件时，说明需要插入，才将需要插入的记录值复制给哨兵
for(j=i-1;A[j]>A[0];--j){ //j从已排序记录最末位开始，逐次往前，当已排序记录关键字大于哨兵A[0]时，将其右移一位
A[j+1]=A[j]; //关键字大于哨兵A[0]的记录右移一位
}
A[j+1]=A[0]; //将哨兵也就是待插入记录插入该插入的位置，此时的A[j]是小于等于哨兵的且A[j+1]大于哨兵，所以需要插入在A[j+1]位置
}
}
for(i=1;i<=10;i++){
printf("%d ",A[i]);
}
return 0;
}
这里在移动元素时对 j 使用 --j 前置自减，结果和 j--其实相同，只不过在处理大量数据时，前置自增自减要比后置自增自减性能表现好一些，先对待插入记录和已排序列表最后一个记录比较关键字大小，然后满足if条件后才复制值给哨兵，而不是进入for循环后直接先复制值给哨兵
程序运行结果如下图
性能分析
空间复杂度: 该算法使用的辅助单元为常数个，所以空间复杂度为O(1);
最好情况下，待排序序列为已排好序序列，总的比较次数C为n-1，不需要移动元素，时间复杂度为O(n)
这里的移动次数包含每个待排序元素A[i]复制给哨兵A[0]的移动和哨兵A[0]插入到A[j+1]的移动，所以
最差情况下，待排序序列为逆序，总的比较的次数C为2+3+...+n，需要移动的次数C为3+4+...+(n+1)，时间复杂度为O(n^2);
该算法平均比较次数和移动次数都约为 (n^2)/4 ，所以算法的时间复杂度为O(n^2)
稳定性：由于每次插入时总是在排序子序列中从后往前先比较再移动，所以不会出现关键字相同的记录相对位置发生变化，直接插入排序算法是稳定的排序算法。
适用性：直接插入排序既适用于顺序存储的线性表，也适用于链式存储的线性表。 （大部分排序算法都仅使用于顺序存储的线性表）
2.二分插入排序 (Binary Insert Sort)
算法基本思想：每次插入先利用二分查找确定应当插入的位置，然后再移动该位置及之后所有元素。
这里以一个有10个记录的一维整型数组为例，C语言实现代码如下：
#include<stdio.h>
int main(){
int i,j,low,high,mid;
int A[11]={0,12,5,35,24,3,7,65,1,47,54};
for(i=2;i<=10;i++){
A[0]=A[i]; //先将待插入的元素复制给哨兵
low=1; //低位指针从下标1开始，也就是第一个记录元素
high=i-1; //高位指针从已排序序列最末位，也就是当前待插入元素A[i]前一个记录，所以为i-1；
while(low<=high){ //while循环开始进行二分查找过程，当满足low<=high时才进行二分查找
mid=(low+high)/2; //mid只有在二分查找过程中赋值
if(A[0]<A[mid]){ //哨兵A[0]与A[mid]中值不断比较大小，若小于A[mid],说明A[mid]右边所有元素都比哨兵大，此时更换high指针为mid-1；
high=mid-1;
}else{
low=mid+1;
}
}
for(j=i-1;j>=high+1;--j){ //此时已经从二分查找的while循环里面推出来，说明已经找到应该插入的位置，下标为high+1，所有high+1及其右边元素都右移1位
A[j+1]=A[j];
}
A[high+1]=A[0]; //哨兵插入，一趟插入排序完成，i代表的for循环继续下一趟
}
for(i=1;i<=10;i++){
printf("%d ",A[i]);
}
return 0;
}
和直接插入排序不同的是，二分插入排序没有对待插入记录和已排序序列中任何记录进行比较，也就是没有用到 if 语句，进入for循环后 直接先将待插入记录值复制给哨兵，然后开始二分查找过程，二分查找过程首先初始化low high指针，先有了high low指针值，才能开始二分查找插入位置过程，才能有mid指针值，有了mid指针值，就可以对哨兵和mid对应的值进行比较，根据比较结果对high low指针进行调整，反复以此便可以找到插入位置然后退出while循环，此时的插入位置为high+1。找到了插入位置后然后干什么呢？当然是移动插入位置及其右边所有元素了，这时利用 j的 for 循环移动，移动完所有元素后，与直接插入排序不同的是，将哨兵A[0]插入high+1处，而不是j+1 位置处，一趟插入完成。
程序运行结果如图：
性能分析
二分插入排序也是稳定的排序算法，与直接插入排序所不同的是，二分插入排序的比较次数减少，n个元素大约需要比较O(nlog2n) 次。比较的次数与元素初始序列状态无关，仅取决于元素个数n，元素移动的次数与初始序列状态有关，时间复杂度也为O(n^2)，对于数据量不是很大的序列，二分插入排序性能表现很好。
3.希尔排序（Hill Sort）
算法基本思想：通过设置gap 间隔值，来将待排序序列分成若干组子序列，每个子序列中前后相邻两个元素之间有gap-1个元素，一般设置gap初始值为n/2， n为待排序列总记录个数，对每个子序列进行直接插入排序，然后所有子序列 直接插入排序 执行完之后gap取半向下取整进行下一趟，直到gap值变为1，此时对整个序列进行不用再划分子序列，而是直接插入排序
如下图所示，一个n为15的整型数组，初始时gap=15/2=7，然后依次取半向下取整为3，1，当gap为7时，分成了8个子序列，每个子序列直接排序后的8个子序列为 {55，99} {5, 77} {48, 69} {12, 33} {56，88} {2, 13} {22, 69} {99, 99}, 然后gap折半向下取整为3，按照间隔元素数为2可以用3个子序列包含全部元素，然后对这3个子序列各自依次使用直接插入排序，得到如下图的第二圈排列结果，这时候gap再次折半向下取整为1，gap为1时对整个序列使用 直接插入排序 算法，便可得到最终的排序序列。
这里以一个具有10个记录的一维整型数组为例，size为11，A[0]最终不存储记录，作为temp交换变量使用 ，给出一个C语言实现：
#include<stdio.h>
int main(){
int i,j,gap;
int A[11]={0,17,5,48,32,26,1,7,89,61,52}; // A[0]默认设置为0
for(gap=5;gap>0;gap/=2){ //判断条件也可以写成gap>=1,
for(i=gap+1;i<11;++i){ //类比地看，此处开始直接插入排序的实现过程，直接插入排序即gap为1 i=2，gap之所以要+1是因为记录从A[1]开始，所以 gap+1 - 1= gap 中间有 gap-1个元素，++i 和 i++在这里最终的结果相同，只不过 ++i性能表现更好一些
if(A[i]<A[i-gap]){ // 待插入记录小于已排序序列最末位记录时才需要移动插入元素
A[0]=A[i]; // 满足if条件进入这里说明需要插入, 那先把待插入记录复制给‘哨兵’A[0]了
for(j=i-gap;j>0&&A[j]>A[0];j-=gap){ //开始插入， 需要满足j>0是因为A[0]最终不存储记录，所以需要移动的元素下标至少为1，子序列中上一个元素的位置要减去gap而不是1;
A[j+gap]=A[j]; //移动子序列元素
}
A[j+gap]=A[0]; //插入‘哨兵’
}
}
}
for(i=1;i<11;i++){
printf("%d ",A[i]);
}
return 0;
}
++i 和 i++在这里最终的结果相同，只不过 ++i性能表现更好一些
程序执行结果如下图：
性能分析
空间复杂度：希尔排序使用了常数个辅助单元，所以空间复杂度为O(1);
时间复杂度：最坏时间复杂度为O(n^2), 其时间复杂度范围在O(n^1.3)到 O(n^2)之间
稳定性：由于子序列的直接插入排序使得关键字相同的记录排序后相对位置可能发生改变，所以希尔排序是不稳定的排序算法
适用性：希尔排序只适用于顺序存储的线性表
2.交换排序(Swap Sort)
交换排序主要有两类
- 冒泡排序（Bubble Sort）
- 快速排序（Quick Sort）
1.冒泡排序 (Bubble Sort)
算法基本思想：从首个记录开始，像是有一个有两个托盘的天平在未排序序列下端，这两个托盘托住两个紧紧相邻的未排序列元素，从一侧(未排序侧)起始元素开始往另一侧一步一步前进，每一步对比托盘上的两个元素大小，按照升序或降序的要求，若需要则交换这两个元素，直至天平走到 其中一侧托盘与已排序序列相邻，这时与已排序序列相邻的托盘上的元素加入到已排序序列中，开始下一趟冒泡。
算法的原理动画如下图展示
以n为10的一维整型数组为例，按照升序排序，C语言简单实现如下：
include<stdio.h>
int main(){
int i,j,temp;
int A[10]={14,5,3,78,64,59,41,87,1,33};
for(i=0;i<9;i++){ //需要冒泡 n-1趟，i从0开始，所以 i< n-1
for(j=0;j<9-i;j++) {// 天平右侧的托盘指针j+1要小于 n-i, 所以 j< n-i-1, 这里n为10 ，所以j < 9-i
if(A[j]>A[j+1]){ //天平左边的元素大于右边的元素，需要交换
temp=A[j]; //用temp辅助变量交换 A[j]与A[j+1]
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
for(i=0;i<10;i++){
printf("%d ", A[i]);
}
return 0;
}
程序运行结果如下图：
性能分析
空间复杂度：使用常数个辅助单元，故空间复杂度为O(1)
时间复杂度：最好时间复杂度O(n),最差时间复杂度和平均时间复杂度都为O(n^2)
稳定性：只有当天平左侧大于右侧才交换，相等不交换，所以冒泡排序是稳定的排序算法
2.快速排序 (QuickSort)
算法基本思想：用一个称为基准的 pivot，一般取待排序列首个记录或者最末位记录，将所有小于pivot的记录划分到左侧，所有大于等于pivot的记录划分到右侧，划分成两个独立的子块，这个过程称为1趟快排或1次划分，然后分别对这两个子块递归,直至每个子块仅包含1个或0个记录，此时排序结束。
一个简单的实例过程如图：
快速排序有递归实现和非递归实现，这里主要讲递归实现方法，非递归实现的方法需要用到栈
递归实现，主要有两个关键函数，功能如下
-
partition(int array[], int low, int high)
划分函数，通过low high指针不断搜索交换记录实现划分，并最终定位到当前pivot最终位置插入并返回值（此时low == high，因为low high指针相向而行，步长为1） -
quickSort(int array[], int low, int high),
调用partition()函数获取每一趟划分最终得到的基准位置，然后利用基准位置前后相邻两个位置的下标和low ，high指针搭配作为参数递归调用自身
这里以n = 10的一维整型数组为例，一个C语言的简单实现：
#include<stdio.h>
#include<stdlib.h>
int partition(int array[], int low, int high){
int pivot = array[low]; //这里基准取第一位
while(low < high){ //当low == high 时，说明已经找到了pivot最终位置，不需要再进行划分了
while(low < high && array[high] >= pivot){ //从high开始，与基准pivot比较，若大于等于pivot，则不需要交换，此时将high指针左移持续搜索，直至找到小于pivot的记录
--high; // 因为右半部分记录都大于等于pivot，满足条件，所以high指针左移
}
array[low] = array[high]; //退出上面这个循环，执行到这里，说明high找到了小于pivot的记录，需要将其交换到low位置处,执行玩这一步后，high处的位置相当于“空下来”了, 实际上有记录，但其可被覆盖，毫无影响
while(low < high && array[low] < pivot){ //当高位high找到小于pivot的记录并交换后，程序顺序执行到这里，从low低位开始右移查找，直至找到大于等于pivot的记录
++low; // 因为左半部分记录都小于pivot，满足条件，所以low指针左移
}
array[high] = array [low]; //low找到了左半部分大于等于pivot的记录，需要交换到high的“空位”上，
} //while循环退出来，说明一次划分已经完成，找到了pivot最终位置，即low的位置，此时low == high，
array[low] = pivot;
return low;
}
void quickSort(int array[], int low, int high){ //数组第一次调用时，low为0，high为n-1
if(low < high){ //low小于high时才需要递归划分
int pivotpos = partition(array, low, high); //获取上一趟划分pivot基准最终位置
quickSort(array, low, pivotpos-1); //根据上一趟的pivot位置，划分的左半部分，low始终是0，high变成pivotpos-1，因为上一趟划分pivot在中间将序列切割成两部分，
quickSort(array, pivotpos+1, high);//根据上一趟pivot的位置，划分的右半部分，high始终是n-1；因为数组第一次调用时，low为0，high为n-1，而low变成pivotpos+1
}
}
int main(){
int i;
int A[] = {24,7,63,51,5,1,23,46,38,14};
int n = sizeof(A) / sizeof(A[0]); //计算数组长度
quickSort(A, 0, n-1);
for(i=0; i<n; i++){
printf("%d ", A[i]);
}
return 0;
}
程序运行结果如下图：
1.简单选择排序
- 算法基本思想：从未排序元素中选取一个最小值 ，放到已排序序列的末端，反复以此。
这里以一个具有10个元素的整型数组为例，给出简单选择排序算法的C语言实现代码，
#include<stdio.h>
int main(){
int i,j,min,temp;
int A[10]={12,3,7,25,68,54,36,98,1,2};
for(i=0;i<9;i++){ //i小于数组长度减1，因为需要排n-1趟，选n-1个最小值，那么剩下那一个必然是最大值，位于排序序列最后
min=i; //用整型数据min作为指针来记录最小值元素的下标，初始时指向未排序序列首个元素
for(j=i+1;j<10;j++){ //j是从未排序序列元素第二个元素开始循环遍历的，所以j从i+1开始，因为对i而言，每一趟都会确定一个最小值放在已排序序列最后，所以j最多可以等于数组长度减1
if(A[j]<A[min]){
min=j; //min指针指向此时最小的元素
} //至此，j循环用min指针确定了未排序序列中最小值的下标
}
if(min!=i){ //若未排序序列最小值元素不在未排序序列首位，就用temp辅助变量交换未排序序列最小值元素和未排序序列首个元素的位置
temp=A[i];
A[i]=A[min];
A[min]=temp;
}
}
for(i=0;i<10;i++){ //依次打印排序后所有元素的值
printf("%d ",A[i]);
}
return 0;
}
程序运行结果如下图
性能分析
