八种排序算法
声明
这里使用顺序表的常规定义,对元素类型进行封装,这里暂时使用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){ |
| L.p=(Elem*)malloc(sizeof(Elem)*LIST_INIT_SIZE); |
| L.len=0; |
| if(L.p==NULL){ |
| printf("List init failed. Error: Memory allocation failed.\n"); |
| exit(EXIT_FAILURE); |
| } |
| } |
| |
| |
| 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--) |
| L.p[j]=L.p[j-1]; |
| L.p[i]=e; L.len++; |
| return true; |
| } |
| |
| |
| void ListTraverse(SqList L){ |
| for(int i=0;i<L.len;i++){ |
| if(i) putchar(' '); |
| printf("%d",L.p[i]); |
| } |
| putchar('\n'); |
| } |
八种排序算法的代码实现
插入排序
| |
| |
| void InsertSort(SqList &L){ |
| for(int i=1;i<L.len;i++){ |
| 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]; |
| } |
| L.p[j+1]=temp; |
| } |
| } |
| } |
折半插入排序
| |
| |
| void Binary_InsertSort(SqList &L){ |
| for(int i=1;i<L.len;i++){ |
| |
| if(L.p[i]>=L.p[i-1]) continue; |
| Elem temp=L.p[i]; |
| int low=0,high=i-1,mid; |
| while(low<=high){ |
| mid=low+(high-low)/2; |
| if(L.p[mid]>temp) high=mid-1; |
| else low=mid+1; |
| } |
| |
| |
| |
| |
| for(int j=i-1;j>=high+1;j--) |
| L.p[j+1]=L.p[j]; |
| L.p[high+1]=temp; |
| } |
| } |
希尔排序
| |
| |
| void ShellSort(SqList &L){ |
| for(int dk=L.len/2;dk>=1;dk/=2){ |
| 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) |
| L.p[j+dk]=L.p[j]; |
| L.p[j+dk]=temp; |
| } |
| } |
| } |
| } |
冒泡排序
| |
| |
| void BubbleSort(SqList &L){ |
| int n=L.len-1; |
| for(int i=0;i<n;i++){ |
| 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){ |
| Elem pivot=L.p[low]; |
| while(low<high){ |
| while(low<high&&L.p[high]>=pivot) high--; |
| L.p[low]=L.p[high]; |
| while(low<high&&L.p[low]<=pivot) low++; |
| L.p[high]=L.p[low]; |
| } |
| L.p[low]=pivot; |
| return low; |
| } |
| |
| |
| void UseQuickSort(SqList &L,int low,int high){ |
| if(low<high){ |
| 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); |
| } |
多线程快速排序
| |
| void multiThreadingQuickSort(SqList &L,int low,int high){ |
| if(low>=high) return; |
| int i=low,j=high; |
| int pivot = L.p[low]; |
| while(i<j){ |
| while(i<j&&L.p[j]>=pivot) j--; |
| L.p[i]=L.p[j]; |
| while(i<j&&L.p[i]<=pivot) i++; |
| L.p[j]=L.p[i]; |
| } |
| L.p[i]=pivot; |
| thread t1(multiThreadingQuickSort,ref(L),low,i-1); |
| thread t2(multiThreadingQuickSort,ref(L),i+1,high); |
| t1.join(); |
| t2.join(); |
| } |
| void QuickSort(SqList &L){ |
| multiThreadingQuickSort(L,0,L.len-1); |
| } |
简单选择排序
| |
| |
| void SelectSort(SqList &L){ |
| for(int i=0;i<L.len-1;i++){ |
| int min=i; |
| for(int j=i+1;j<L.len;j++) |
| if(L.p[j]<L.p[min]) min=j; |
| if(min!=i){ |
| Elem temp=L.p[min]; |
| L.p[min]=L.p[i]; |
| L.p[i]=temp; |
| } |
| } |
| } |
堆排序
| |
| |
| |
| void AdjustDown(SqList &L,int low, int high){ |
| int i=low,j=i*2+1; |
| while(j<=high){ |
| if(j+1<=high&&L.p[j+1]>L.p[j]) |
| j++; |
| if(L.p[j]>L.p[i]){ |
| Elem temp=L.p[i]; |
| L.p[i]=L.p[j]; |
| L.p[j]=temp; |
| i=j; j=2*i+1; |
| } |
| else break; |
| } |
| } |
| |
| void BuildMaxHeap(SqList &L){ |
| for(int i=L.len/2-1;i>=0;i--) |
| AdjustDown(L,i,L.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); |
| } |
| } |
归并排序
归并排序可以通过递归方式实现,也可以通过非递归方式实现,这里暂时给出递归实现的代码。
归并排序的递归实现
| |
| void Merge(SqList &L,SqList &tempL,int left,int mid,int right){ |
| int i=left,j=mid; |
| int tmp=left; |
| 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){ |
| 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]; |
| for(int i=0;i<8;i++) InitList(L[i]); |
| srand((int)time(NULL)); |
| for(int i=0;i<size;i++){ |
| temp=rand()%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 |
| ---------------------------------------------------------------------- |
排序算法对比
排序算法的时间复杂度、空间复杂度和稳定性对比如下所示:
排序算法 |
最坏时间复杂度 |
最好时间复杂度 |
平均时间复杂度 |
空间复杂度 |
稳定性 |
插入排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
希尔排序 |
|
|
O(n^1.3) |
O(1) |
不稳定 |
冒泡排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
稳定 |
快速排序 |
O(n^2) |
O(nlogn) |
O(nlogn) |
O(nlogn) |
不稳定 |
选择排序 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
不稳定 |
堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) |
不稳定 |
归并排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) |
稳定 |
基数排序 |
O(d(n+r)) |
O(d(n+r)) |
O(d(n+r)) |
O(r) |
稳定 |
Comments | NOTHING