八种排序算法
将顺序表的八种常见排序算法总结实现如下。
目录
八种排序算法
声明
这里使用顺序表的常规定义，对元素类型进行封装，这里暂时使用int类型作为顺序表的元素，可以使用C++的语法将代码重用到任何数据类型，但是需要对数据元素的打印和比较进行重载。另外，所有排序默认为从小到达排列。
以下代码可以直接复制到一个cpp文件中进行测试和使用，请包含必要的头文件，比如：stdlib.h、ctime。
顺序表的定义
//顺序表的定义
#define LIST_INIT_SIZE 100 //顺序表的初始化大小
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<ctime>
typedef int Elem;
typedef struct list{ //定义顺序表结构体，包含一个数组的地址和数组中有效元素的个数
Elem *p; //顺序表空间起始地址
unsigned int len; //顺序表中元素个数
}SqList;
顺序表基本函数接口
//基本函数接口的实现
//初始化顺序表
void InitList(SqList &L){ //申请一定大小的数组空间，并把地址给p
L.p=(Elem*)malloc(sizeof(Elem)*LIST_INIT_SIZE);
L.len=0; //初始化大小为0
if(L.p==NULL){ //如果分配失败，输出失败提示
printf("List init failed. Error: Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
//在顺序表的下标i处插入新的数据元素,插入成功返回true，否则返回false
bool ListInsert(SqList &L,unsigned int i,Elem e){
//如果插入在顺寻表长度范围以外，或者顺序表已满
if(i>L.len||L.len==LIST_INIT_SIZE) return false;
for(int j=L.len;j>i;j--) //i之后的元素后移
L.p[j]=L.p[j-1];
L.p[i]=e; L.len++; //将e插入到下标i处，长度加一
return true;
}
//遍历输出顺序表的内容
void ListTraverse(SqList L){ //遍历并打印顺序表内容，访问方式可修改
for(int i=0;i<L.len;i++){
if(i) putchar(' ');
printf("%d",L.p[i]);
}
putchar('\n');
}
八种排序算法的代码实现
插入排序
//插入排序(从小到大),默认按照递增序列排序。
//空间复杂度O(1),时间复杂度O(n*n)
void InsertSort(SqList &L){
for(int i=1;i<L.len;i++){ //从下标1开始，将每一个元素插入到前面已经有序的序列中
int j;
if(L.p[i]<L.p[i-1]){ //如果当前元素小于前一个元素，则需要进行插入
Elem temp=L.p[i]; //保留当前需要插入的元素
for(j=i-1;j>=0&&L.p[j]>temp;j--){
L.p[j+1]=L.p[j]; //将需要插入的位置之后到i之间的元素都往后移位
}
L.p[j+1]=temp; //j在-1或在第一个小于等于需要插入的元素位置处停止，故插入在j+1的位置上
}
}
}
折半插入排序
//折半插入排序(从小到大)，在寻找插入位置时，使用折半查找，减少比较次数，以增加查找的速度。
//空间复杂度O(1),时间复杂度O(n*n)
void Binary_InsertSort(SqList &L){
for(int i=1;i<L.len;i++){ //从1开始进行插入排序
//如果当前元素大于等一前一个元素，则不需要插入，进行下一轮循环
if(L.p[i]>=L.p[i-1]) continue;
Elem temp=L.p[i]; //记录需要插入的元素
int low=0,high=i-1,mid; //low，hihg，mid为折半的参数
while(low<=high){ //边界处应该是low和high相等
mid=low+(high-low)/2; //防止相加溢出
if(L.p[mid]>temp) high=mid-1; //如果中间值大于要插入的值，则插入位置在左侧
else low=mid+1; //否则插入位置在右侧
}
//考虑如果插入元素为10，如果low==high的时候
//如果该位置是9或者10，循环结束的时候low会增加1，则插入位置是high+1；
//如果该位置为11，则插入位置应该就是这里，然而循环结束的时候，high会被-1，因此需要+1回到这个位置，即插入位置为high+1
//综上，插入位置为high+1
for(int j=i-1;j>=high+1;j--)
L.p[j+1]=L.p[j]; //将需要插入的位置之后到i之间的元素都往后移位
L.p[high+1]=temp; //在插入元素的位置放置元素
}
}
希尔排序
//希尔排序(从小到大)，当元素被划分到不同的子表时，可能顺序会法生相对变化，故不稳定。
//空间复杂度O(1),n在某个范围内，空间复杂度为O(n^1.3),最坏时间复杂度O(n*n)
void ShellSort(SqList &L){
for(int dk=L.len/2;dk>=1;dk/=2){ //dk为步长，初始值为表长，最小值为1，每次减半
for(int i=dk;i<L.len;i++){ //对顺序表进行分组，从每组的第一号元素开始进行插入排序，且各组的插入排序可以看作时并发执行的
if(L.p[i]<L.p[i-dk]){ //如果当前位置元素小于本组内的上一个元素，则需要插入
Elem temp=L.p[i]; //记录待插入的元素
int j; //用于移动元素的工作指针
for(j=i-dk;j>=0&&L.p[j]>temp;j-=dk) //j从该组上一个元素开始，即将从插入位置到j-dk位置的元素依次后移，其中每次j都要跨越dk的长度
L.p[j+dk]=L.p[j];
L.p[j+dk]=temp; //在插入位置放置需要插入的元素
}
}
}
}
冒泡排序
//冒泡排序(从小到大)
//空间复杂度O(1),时间复杂度O(n*n)
void BubbleSort(SqList &L){
int n=L.len-1;
for(int i=0;i<n;i++){ //冒泡，最多len-1次
bool flag=false; //用于标记本趟冒泡是否发生交换
for(int j=n;j>=1+i;j--){ //从后往前进行交换,每次确定一个元素位置，所以已有序的部分不用再比较
if(L.p[j]<L.p[j-1]){ //如果当前位置小于前一个位置的值，则进行交换
Elem temp=L.p[j]; //交换
L.p[j]=L.p[j-1];
L.p[j-1]=temp;
flag=true; //发生交换
}
}
if(flag==false) return; //如果本趟冒泡未发生交换，则表明已经有序，排序结束
}
}
快速排序
//快速排序的划分算法，选取一个枢轴进行划分,将小于枢轴的放在左侧，将大于枢轴的放在右侧
int Partition(SqList &L,int low,int high){ //对L，从low到high之间的部分进行划分
Elem pivot=L.p[low]; //选择枢轴
while(low<high){ //边界为low==high，此时的位置便是枢轴要安放的位置。
while(low<high&&L.p[high]>=pivot) high--;//从high侧找到一个小于枢轴的元素，放在低位，也就是枢轴的左侧
L.p[low]=L.p[high]; //因为low指针所指的位置上的元素已经被存储为piovt或者被上一次循环移枢轴右侧了，因此直接赋值
while(low<high&&L.p[low]<=pivot) low++; //从low侧找到一个大于枢轴的元素，放在高位，也就是枢轴的右侧
L.p[high]=L.p[low]; //因为high指针所指的位置上的元素已经被移到枢轴左侧了，因此可以直接赋值
}
L.p[low]=pivot; //当low==high时，便是枢轴所在的位置
return low; //返回枢轴所在的位置，完成一次划分
}
//快速排序的递归算法
//采用了递归，因此有栈的开销，空间复杂度最好为log(n+1)向上取整，最坏为O(n),平均为O(logn)；时间复杂度最坏为O(n*n)，平均为O(nlogn)
void UseQuickSort(SqList &L,int low,int high){
if(low<high){ //当排序区间不为0时进行排序
int pos=Partition(L,low,high); //进行划分
UseQuickSort(L,low,pos-1); //左侧递归排序
UseQuickSort(L,pos+1,high); //右侧递归排序
}
}
//快速排序对外函数接口
void QuickSort(SqList &L){
UseQuickSort(L,0,L.len-1);
}
简单选择排序
//简单选择排序，每次从i~len号元素中选取一个最小的与i进行交换
//比较次数与序列状态无关，比较次数为 n(n-1)/2 故时间复杂度为O(n*n)
void SelectSort(SqList &L){
for(int i=0;i<L.len-1;i++){ //最多执行n-1次
int min=i; //记录最小元素的下标，初始化为i
for(int j=i+1;j<L.len;j++) //从[i,len)中寻找最小元素，并记录下标
if(L.p[j]<L.p[min]) min=j;
if(min!=i){ //如果最小元素不是i处的元素，则于i进行交换
Elem temp=L.p[min];
L.p[min]=L.p[i];
L.p[i]=temp;
}
}
}
堆排序
//堆排序，建立大根堆，然后每次将堆顶元素和堆尾巴交换，并调整堆，则最终完成从小到达的排序
//这里的堆序列，下标从0开始
//向下调整的堆的函数，将如果根节点比较小，则向下交换，将[low,high]区间内的元素调整为堆
void AdjustDown(SqList &L,int low, int high){
int i=low,j=i*2+1; //i表示要调整子树的根结点，j表示i的左孩子
while(j<=high){ //如果j不超过数组的j限制，说明左孩子存在
if(j+1<=high&&L.p[j+1]>L.p[j]) //如果右孩子存在，并且右孩子比左孩子大，用j记录右孩子
j++; //这保证了i和孩子交换以后保持大根状态，即将i和左右孩子中较大的那个交换
if(L.p[j]>L.p[i]){ //如果根比较小，需要向下调整
Elem temp=L.p[i]; //将i和两个孩子中较大的那个交换
L.p[i]=L.p[j];
L.p[j]=temp;
i=j; j=2*i+1; //将i修改为与调整点，即下标j，然后将j改为i的左孩子，开始下一轮调整
}
else break; //如果不需要向下调整了，则调整完毕，结束循环
}
}
//建立大根堆的过程
void BuildMaxHeap(SqList &L){
for(int i=(L.len-1)/2;i>=0;i--) //从最有一个非叶子结点开始一次往上，对每一个结点做向下调整
AdjustDown(L,i,L.len-1); //将从[i,len-1]区间内调整成为大根堆
}
//堆排序算法，每次将堆尾部的元素和堆顶进行交换，再将上部分剩下的堆进行调整形成大根堆
//因此可以从大到小逆序的填充数组，形成从小到大的排序
void HeapSort(SqList &L){
BuildMaxHeap(L); //建立大根堆
for(int i=L.len-1;i>=0;i--){ //从堆尾部开始，依次弹出堆顶放在堆尾上
Elem temp=L.p[0]; //每次将堆尾和堆顶进行交换
L.p[0]=L.p[i];
L.p[i]=temp;
AdjustDown(L,0,i-1); //调整上部分的堆使其保持大根堆的形态
}
}
归并排序
归并排序可以通过递归方式实现，也可以通过非递归方式实现，这里暂时给出递归实现的代码。
归并排序的递归实现
//将顺序表L中从left~mid-1和mid~right之间的元素归并成一个有序序列，tempL为辅助数组，由调用函数申请并传入
void Merge(SqList &L,SqList &tempL,int left,int mid,int right){
int i=left,j=mid; //i为左半段的指针，j为右半段的指针
int tmp=left; //tmp为辅助数组的指针
while(i<=mid-1&&j<=right){ //将两段从小到大进行归并
if(L.p[i]<=L.p[j])
tempL.p[tmp++]=L.p[i++];
else
tempL.p[tmp++]=L.p[j++];
}
while(i<=mid-1) tempL.p[tmp++]=L.p[i++]; //如果有某一段仍有剩余，归并入临时数组中
while(j<=right) tempL.p[tmp++]=L.p[j++];
for(tmp=left;tmp<=right;tmp++) //将归并好的有序序列放回到原始顺序表中
L.p[tmp]=tempL.p[tmp];
}
//核心递归排序函数
void Msort(SqList &L,SqList &tempL,int left,int right){
if(left<right){ //如果归并段大于1进行归并
int mid=left+(right-left)/2; //取中间进行分段,防止相加溢出
Msort(L,tempL,left,mid); //对左边进行归并
Msort(L,tempL,mid+1,right); //对右边进行归并
Merge(L,tempL,left,mid+1,right); //合并两个有序段
}
}
//归并排序的接口函数
void MergeSort(SqList &L){
SqList tempL; //构建临时的辅助顺序表
tempL.p=(Elem*)malloc(L.len*sizeof(Elem)); //为临时数组开辟空间，这里没有用
if(tempL.p!=NULL){ //如果申请空间成功
Msort(L,tempL,0,L.len-1); //归并
free(tempL.p); //释放空间
}
else exit(EXIT_FAILURE); //如果申请失败则退出
}
归并排序的非递归实现
验证
用于验证排序有效性的main函数
//测试使用的主函数
int main(void){
int size=30; //顺序表中元素的个数
Elem temp;
SqList L[8]; //创建8个相同的顺序表
for(int i=0;i<8;i++) InitList(L[i]); //分别初始化
srand((int)time(NULL)); //随机数的种子
for(int i=0;i<size;i++){
temp=rand()%100; //产生100以内的随机数
for(int j=0;j<8;j++) ListInsert(L[j],0,temp);
}
printf("----------------------------------------------------------------------\n");
printf("八种排序算法的验证如下：\n");
printf("原始数组内容为：\n");
ListTraverse(L[0]);
printf("----------------------------------------------------------------------\n");
printf("插入排序结果如下：\n");
InsertSort(L[0]);
ListTraverse(L[0]);
printf("----------------------------------------------------------------------\n");
printf("折半插入排序结果如下：\n");
Binary_InsertSort(L[1]);
ListTraverse(L[1]);
printf("----------------------------------------------------------------------\n");
printf("希尔排序结果如下：\n");
ShellSort(L[2]);
ListTraverse(L[2]);
printf("----------------------------------------------------------------------\n");
printf("冒泡排序结果如下：\n");
BubbleSort(L[3]);
ListTraverse(L[3]);
printf("----------------------------------------------------------------------\n");
printf("快速排序结果如下：\n");
QuickSort(L[4]);
ListTraverse(L[4]);
printf("----------------------------------------------------------------------\n");
printf("简单选择排序结果如下：\n");
SelectSort(L[5]);
ListTraverse(L[5]);
printf("----------------------------------------------------------------------\n");
printf("堆排序结果如下：\n");
HeapSort(L[6]);
ListTraverse(L[6]);
printf("----------------------------------------------------------------------\n");
printf("归并排序结果如下：\n");
MergeSort(L[7]);
ListTraverse(L[7]);
printf("----------------------------------------------------------------------\n");
return 0;
}
某次测试的结果
----------------------------------------------------------------------
八种排序算法的验证如下：
原始数组内容为：
9 97 61 67 23 29 40 79 53 10 74 44 42 86 79 4 62 42 52 98 64 37 44 7 27 47 23 18 88 82
----------------------------------------------------------------------
插入排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
折半插入排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
希尔排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
冒泡排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
快速排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
简单选择排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
堆排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
归并排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------