五大排序算法
文章目录
前言
排序算法(Sorting algorithm)是一种能将序列按照某种特定排序方式进行排列的一种算法,下面简要介绍其中五种排序算法。
五大排序算法
1.冒泡排序
冒泡排序是一种较简单的排序算法,又称起泡排序。其基本思路是,每次将相邻的两个,每次比较一轮,总会找到序列中最大的一个或最小的一个。最终可以得到一个递增数列或者递减数。
核心过程
void Bubble_sort(int a[],int n) { int i,j,temp; for(i=0;i<n-1;i++)//C语言中数组的下标是从0开始,故i最大为n-1 { for(j=0;ja[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }
2.快速排序
快速排序是基于冒泡排序的改进方法,其基本思路为:先在未排序的序列选择一个值,以该值为基准数,将序列一分为二,小于基准数的放于左边,大于基准数的放于右边,重复上述操作,当个区间只有一个数时结束。
核心过程
void quick_Sort(int a[], int low, int high){ if (low > high) { return; } int i = low, j = high, temp = a[i];//temp为基准数 while (i < j) { while (temp < a[j] && i < j){ j--; } if (i a[i] && i < j){ i++;} if (i < j){ a[j--] = a[i]; } } a[i] = temp;//递归调用 quick_Sort(a, low, i - 1); quick_Sort(a, i + 1, high);}
3.插入排序
插入排序是一种简单的排序算法,即在有序序列中,插入一些数据且插入后序列依旧为有序序列。
核心过程
void insertion_sort(int arr[], int n){ int i,j,k; for (i=1;i=0) && (arr[j]>k)) { arr[j+1] = arr[j]; j--; } arr[j+1] = k; }}
4.希尔排序
希尔排序是基于插入排序而提出的方法的,其基本思想是:先将整个未排元素序列切割成分成若干个子序列,确定步长并分别进行插入排序,再减少一半步长同时进行上述操作,当每个子序列长度为1时,再进行一次插入排序,便可得到有序的序列。
核心过程
void shellSort(int a[], int len){ int i, j, k, temp, SL; // 设SL为希尔步长 for (SL = len / 2; SL > 0; SL /= 2) // 设置希尔步长的初始值为len的二分之一,完成一次遍历之后,步长减少一半{ for (i = 0; i < SL; ++i) // i 为每次分组的第一个元素下标 { for (j = i + SL; j = 0 && a[k] > temp) { a[k + SL] = a[k]; k -= SL; } a[k + SL] = temp; } } }}
5.选择排序
选择排序是一种简单直观的排序算法,其基本思路:先在未排序的序列中找到最小(大)元素,并存放到序列的起始位置,再从剩余的未排序排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。一直重复上述过程,直到所有排序完成。
核心过程
void select_sort(int a[],int n) { int i,j,k,temp;for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++) { if(a[j]<a[k]) k=j;} if(k!=j) { temp=a[i];a[i]=a[k]; a[k]=temp; } }}
例题讲解
将下列数列进行排序 a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21};
插入排序解法:
#include void select_sort(int a[],int n) { int i,j,k,temp;for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++) { if(a[j]<a[k]) k=j;} if(k!=j) { temp=a[i];a[i]=a[k]; a[k]=temp; } }}int main(){ int a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21};select_sort(a,20);for (int i=0;i<20;++i){printf("%d ",a[i]);} printf("\n"); return 0;}
快速排序解法
#include void quick_Sort(int a[], int low, int high){ if (low > high) { return; } int i = low, j = high, temp = a[i];//temp为基准数 while (i < j) { while (temp < a[j] && i < j){ j--; } if (i a[i] && i < j){ i++;} if (i < j){ a[j--] = a[i]; } } a[i] = temp;//递归调用 quick_Sort(a, low, i - 1); quick_Sort(a, i + 1, high);}int main(){ int a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21}; quick_Sort(a,0,20);for (int i=0;i<20;++i){printf("%d ",a[i]);} printf("\n"); return 0;}
运行结果显示:
性能比较
排序算法 | 时间复杂度(平均情况) | 时间复杂度(最好情况) | 时间复杂度(最坏情况) | 稳定性 |
冒泡排序 | O(n^2) | O(n) | O(n^2) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | 不稳定 |
插入排序 | O(n^2) | O(n) | O(n^2) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | 不稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 |
总结
冒泡算法,快速排序,插入算法,希尔算法和选择算法都是排序算法中常用的算法,其时间复杂度有所区别,当考虑算法的时间复杂度时,要合理的选择适当的排序算法。