几种常见的排序方法整理

一、直接插入排序

插入排序是一种简单直观的排序算法。通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在从后向前扫描的过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

算法:

将需要排序的数列看成一个数组,i初始化指向数组1号下标,j初始化指向数组0号下标,和i对应数值进行比较,比较一次往后退一步,如果j对应数值大于i对应数值,数值进行交换,直到i前面的数字都比它小,i往后走。

时间复杂度:(1)最坏情况是O(n^2)
(2) 最好情况是有序情况:O(n)
空间复杂度:O(1)
稳定性:稳定

代码:
public static void insertSort(int[] array){ int tmp = 0; int j ; for(int i=1;
i<array.length; i++){ tmp = array[i]; for( j=i-1; j>=0; j--){ if(array[j] >
tmp){ array[j+1] = array[j]; //调换位置 }else{ // array[j+1] = tmp; //不用换,放回原位
break; } } array[j+1] = tmp; //不用换,放回原位 } }
二、希尔排序

希尔排序也是插入排序的一种,它是采用分组的思想,对每组进行插入排序。

代码:
public static void shellSort(int[] array){ int[] drr = {5,3,1}; for(int i = 0;
i<drr.length; i++){ shell(array,drr[i]); } } public static void shell(int[]
array,int gap){ int tmp = 0; for(int i = gap; i<array.length; i++){ tmp =
array[i]; int j; for(j=i-gap; j>=0; j-=gap){ if(array[j]>tmp){ array[j+gap] =
array[j]; }else { break; } } array[j+gap]=tmp; } }
三、选择排序

算法思想:

先从数组第一个数字开始,把这个数字和这个数字之后的所有数字进行比较,如果比这个数字小就交换,然后把数组第二个数字和它之后的所有数字进行比较,比他小就交换,以此类推,直到数组最后一个数字。

代码:
public static void selectSort(int[] array){ for(int i=0; i<array.length;
i++){ for(int j=i+1; j<array.length; j++){ if(array[j]<array[i]){ int tmp =
array[i]; array[i] = array[j]; array[j] = tmp; } } } }
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定

四、堆排序

首先将数组建立成一个大根堆,从数组最后一个数字开始,和数组0号下标数字进行交换,然后采用向下调整法。接着将倒数第二个数字和数组0号下标数字进行交换,然后采用向下调整法,以此类推,直到0号下标数字。

代码:
public static void heapSort(int[] array){ creatHeap(array); int end =
array.length-1; while(end>0){ int tmp = array[end]; array[end] = array[0];
array[0] = tmp; adjustDown(array,0,end); end--; } } //建立大根堆 public static void
creatHeap(int[] array){ for(int i = (array.length-1-1)/2; i>=0; i--){
adjustDown(array,i,array.length); } } //向下调整法 public static void
adjustDown(int[] array,int root,int len){ int patrnt = root; int child =
root*2+1; //最起码有左孩子 while(child<len){ //有右孩子且左孩子小于右孩子,进行交换 if(child+1<len &&
array[child]<array[child+1]){ int tmp = array[child]; array[child] =
array[child+1]; array[child+1] = tmp; } //如果左孩子大于父亲结点,要进行交换 if (array[child] >
array[patrnt]) { int tmp = array[child]; array[child] = array[patrnt];
array[patrnt] = tmp; patrnt = child; child = patrnt*2+1; }else{ break; } } }
时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定

五、冒泡排序

冒泡排序是每一趟都从第一个数字开始,将数组每一个数字和它后一个数字进行比较,比它小就交换。如此往复,直到序列有序。

代码:
public static void bubleSort(int[] array){ //i表示趟数 for(int i=0;
i<array.length-1; i++){ for(int j=0; j<array.length-1-i; j++){
if(array[j]>array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1]
= tmp; } } } }
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定

六、快速排序

快速排序,又称划分交换排序。通过一趟排序将要排序的数据分割成两部分,然后再按此方法对两部分数据分别进行快速排序,以此达到整个数据变成有序序列
步骤为:
(1) 从数列找出一个元素,称为“基准”。
(2)
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作。
(3)把基准元素左边的数值序列用递归的方法进行快速排序,右边序列也如此。直到整个序列有序。

代码:
public static void quickSort(int[] array){ quick(array,0,array.length-1); }
public static void quick(int[] array,int left,int right){ if(left>=right){
return; } int par = partition(array,left,right); //递归排序左边和右边
quick(array,left,par-1); quick(array,par+1,right); } //找基准 public static int
partition(int[] array,int left,int right){ int tmp = array[left];
while(left<right){ while(left<right && array[right]>=tmp){ right--; }
array[left]=array[right]; while(left<right && array[left]<=tmp) { left++; }
array[right] = array[left]; } array[left] = tmp; return left; }
时间复杂度:O(nlogn)
最坏情况:1 2 3 4 5 6 7 8 9 / 9 8 7 6 5 4 3 2 1 :O(n^2)
空间复杂度:O(logn)~O(n)
稳定性:不稳定

七、归并排序

归并排序是采用分治法,思想就是先将数组分解为一个一个的数(将数组从中间一分为二,然后递归分解左边和右边),再合并数组。
合并的基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指向就往后移一位。然后比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

代码:
public static void mergeSort(int[] array){
mergeSortIn(array,0,array.length-1); } //分解 public static void
mergeSortIn(int[] array,int low,int high){ if(low>=high){ return; }
//分解(从数组中间一分为二,直至分解为一个一个的数) int mid = (low+high)>>>1; //右移相当于除2
mergeSortIn(array,low,mid); mergeSortIn(array,mid+1,high); //归并(将一个一个的数按序归并)
merge(array,low,mid,high); } //归并 public static void merge(int[] array,int
low,int mid,int high){ int s1 = low; int s2 = mid+1; int len = high-low+1;
//新数组的长度 int[] ret = new int[len]; //新建一个数组用来存放归并排序后的数 int i = 0; //表示ret数组的下标
while (s1<=mid && s2<=high){ if(array[s1] <= array[s2]){ ret[i++] =
array[s1++]; }else { ret[i++] = array[s2++]; } } while (s1<=mid){ ret[i++] =
array[s1++]; } while (s2<=high){ ret[i++] = array[s2++]; } for(int j= 0;
j<ret.length; j++){ array[j+low] = ret[j]; } }
时间复杂度:nlogn
空间复杂度:O(n)
稳定性:稳定

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信