几种常见的排序方法整理
一、直接插入排序
插入排序是一种简单直观的排序算法。通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在从后向前扫描的过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法：
将需要排序的数列看成一个数组，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=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;
itmp){
array[j+gap] = array[j];
}else {
break;
}
}
array[j+gap]=tmp;
}}
三、选择排序
算法思想：
先从数组第一个数字开始，把这个数字和这个数字之后的所有数字进行比较，如果比这个数字小就交换，然后把数组第二个数字和它之后的所有数字进行比较，比他小就交换，以此类推，直到数组最后一个数字。
代码：
public static void selectSort(int[] array){
for(int i=0;
i时间复杂度：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时间复杂度：O（nlogn）
空间复杂度：O（1）
稳定性：不稳定
五、冒泡排序
冒泡排序是每一趟都从第一个数字开始，将数组每一个数字和它后一个数字进行比较，比它小就交换。如此往复，直到序列有序。
代码：
public static void bubleSort(int[] array){
//i表示趟数
for(int i=0;
iarray[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=tmp){
right--;
}
array[left]=array[right];
while(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时间复杂度：nlogn
空间复杂度：O(n)
稳定性：稳定
推荐阅读
- 数据结构|Java实现常见的排序算法
- Java|Java序列化和反序化
- Java|Java枚举类型
- 数据结构|排序算法（七大经典排序算法）
- 数据结构|劈叉都会还不会下腰吗（（二叉树经典面试题详解））
- java学习|Java高级学习笔记-1（多线程）
- java并发—动态调整线程池
- Firefox 禁止中国用户！！
- #java|***********--＞JAVA50必刷题之第一题＜--***************