🚄1 快速排序
🚅1.1 快排原理
1 从待排序区间选择一个数，作为基准值
2 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
3 采用分治思想对左右两个小区间，对左右两个小区间按照同样的方式来处理，直到小区间的长度==1，那么表面已经有序，如果长度为零，则说明没有数据！
🚈1.2 递归实现
通过了解快排的原理，那么就可以编写如下代码（我们一开始以数列中第一个数为基准值，寻找基准在数列中所在的位置）：
public class TestDemo1 { public static void main(String[] args) { int[] array = {67,7,32,98,1,0,45,23,234,6746,123}; Quack(array); System.out.println(Arrays.toString(array)); } /** * 快排递归写法 * 时间复杂度: 最好 O(N*logN) 最差(有序) O(N*N) * 空间复杂度: O(logN) * 稳定性:不稳定 * @param array 待排序数列 */ public static void Quack(int[] array){ QuackSort(array,0,array.length-1); } public static void QuackSort(int[] array,int left,int right){ //递归的终止条件，当左等于大于右时，说明此时序列有序 if(left>=right){ return; } //找基准 int privot = getprivot(array,left,right); //递归左边 QuackSort(array,left,privot-1); //递归右边 QuackSort(array,privot+1,right); } public static int getprivot(int[] array,int start,int end){ int tmp = array[start]; while (start<end){ while (start<end&&array[end]>=tmp){ end--; } array[start]=array[end]; while (start<end&&array[start]<=tmp){ start++; } array[end]=array[start]; } array[start]=tmp; return start; } }
🚝1.3 对快排进行优化（三数取中法）
对于快排的优化，其实就是优化基准：
public class TestDemo1 { public static void main(String[] args) { int[] array = {67,7,32,98,1,0,45,23,234,6746,123}; Quack(array); System.out.println(Arrays.toString(array)); } /** * 快排递归写法 * 时间复杂度: 最好 O(N*logN) 最差(有序) O(N*N) * 空间复杂度: O(logN) * 稳定性:不稳定 * @param array */ public static void Quack(int[] array){ QuackSort(array,0,array.length-1); } public static void Swap(int[] array,int i,int j){ int tmp = array[i]; array[i]=array[j]; array[j]=tmp; } public static int getMid(int[] array,int a,int b){ int mid = a+((b-a)>>>1); if(array[a]>array[b]){ if(array[mid]>array[a]){ return a; }else if(array[mid]<array[b]){ return b; }else{ return mid; } }else{//array[a]<array[b] if(array[mid]<array[a]){ return a; }else if(array[mid]>array[b]){ return b; }else{ return mid; } } } public static void QuackSort(int[] array,int left,int right){ //递归的终止条件，当左等于大于右时，说明此时序列有序 if(left>=right){ return; } //获取三个值中间值的小标 int mid = getMid(array,left,right); //在把中间值放到一开始的位置 Swap(array,left,mid); //找基准 int privot = getprivot(array,left,right); //递归左边 QuackSort(array,left,privot-1); //递归右边 QuackSort(array,privot+1,right); } public static int getprivot(int[] array,int start,int end){ int tmp = array[start]; while (start<end){ while (start<end&&array[end]>=tmp){ end--; } array[start]=array[end]; while (start<end&&array[start]<=tmp){ start++; } array[end]=array[start]; } array[start]=tmp; return start; } }
优化总结：
1 快排的优化实质上就是在对基准进行优化，所以这里采用了三数取中法进行优化
2 可以结合我们之前所学的直接插入排序进行优化，对于插入排序，之前已经了解到数列越有序越快，那么就可以当调整的长度小于某个数的时候，可以直接利用直接插入排序
🚃1.4 非递归实现
对于非递归的实现，我们此时还是一样根据原理需要找到基准值，然后再利用数据结构中栈去解决（核心的思想也是利用找基准去解决）：
代码如下：
//非递归实现 public static void nonQuackSort(int[] array){ int start = 0; int end = array.length-1; Stack<Integer> stack = new Stack<>(); //找基准 int privot = getprivot(array,start,end); //确保右边至少有两个可排序的数，否则就是只有一个数，就是有序的 if(privot-1>start){ stack.push(start); stack.push(privot-1); } //确保左边至少有两个可排序的数，否则就是只有一个数，就是有序的 if(privot+1<end){ stack.push(privot+1); stack.push(end); } while (!stack.isEmpty()){ end=stack.pop(); start=stack.pop(); privot = getprivot(array,start,end); if(privot-1>start){ stack.push(start); stack.push(privot-1); } if(privot+1<end){ stack.push(privot+1); stack.push(end); } } }
🚋二 归并排序
🚌2.1 归并的核心思想
给定两个有序数组，那么如何将他们合并成为一个有序的数组呢？其实在合并的过程中就体现出归并排序的初步思想原理，就是依据这样的一个思想。
代码如下：
public static int[] conbine(int[] array1,int[] array2){ //创建一个新的数组来存储合并之后的数据 int[] array = new int[array1.length+array2.length]; //记录合并数组的下标 int i = 0; //第一个数组的第一个下标 int s1 = 0; //第一个数组的最后一个下标 int e1 = array1.length-1; //第二个数组的第一个下标 int s2 = 0; //第二个数组的最后一个下标 int e2 = array2.length-1; //将两个数组中的数据按照从小到大放入新的数组中 while (s1<=e1&&s2<=e2){ if(array1[s1]<array2[s2]){ array[i++]=array1[s1++]; }else{ array[i++]=array2[s2++]; } } //可能存在第一个数组没放完或者第二个数组的数据没放完 while (s1<=e1){ array[i++]=array1[s1++]; } while (s2<=e2){ array[i++]=array2[s2++]; } return array; }
🚎2.2 归并排序的递归实现
public static void mergeSort(int[] array){ merge(array,0,array.length-1); } public static void merge(int[] array,int low,int high){ int mid = low+((high-low)>>>1); //递归的终止条件 if(low>=high){ return; } //左边递归进行分解 merge(array,low,mid); //右边递归进行分解 merge(array,mid+1,high); //开始归并 Conbine(array,low,mid,high); } //归并的核心思想 public static void Conbine(int[] array,int low,int mid,int high){ int[] tmp = new int[high-low+1]; int i = 0; int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; while (s1<=e1&&s2<=e2){ while (s1<=e1&&s2<=e2){ if(array[s1]<array[s2]){ tmp[i++]=array[s1++]; }else{ tmp[i++]=array[s2++]; } } //可能存在第一个数组没放完或者第二个数组的数据没放完 while (s1<=e1){ tmp[i++]=array[s1++]; } while (s2<=e2){ tmp[i++]=array[s2++]; } } for (int j = 0; j < i; j++) { //注意数组下标，当遇到右边数组合并时，它的第一个下标已经不是零了 array[j+low]=tmp[j]; } }
🚍2.3 归并排序的非递归实现
非递归排序，所采用的思想就是先分组，先是一个一个一组，在变成两个一组，最后整个数组为一组时，此时就是一个有序的数组。
public static void nonmergeSort(int[] array){ //组数(一开始一个一组) int gap = 1; //只有组数大于等于数组的长度，那么此时说明数组已经有序 while (gap<array.length){ //每重新分组，遍历一遍数组，进行归并排序 for (int i = 0; i < array.length-1; i+=2*gap) { int left = i; int mid = left+gap-1; //注意这时mid可能会越界 if (mid>=array.length){ mid=array.length-1; } int right = mid+gap; if(right>=array.length){ right=array.length-1; } //开始归并 Conbine(array,left,mid,right); } //循环结束，组数乘2 gap=gap*2; } } public static void Conbine(int[] array,int low,int mid,int high){ int[] tmp = new int[high-low+1]; int i = 0; int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; while (s1<=e1&&s2<=e2){ while (s1<=e1&&s2<=e2){ if(array[s1]<array[s2]){ tmp[i++]=array[s1++]; }else{ tmp[i++]=array[s2++]; } } //可能存在第一个数组没放完或者第二个数组的数据没放完 while (s1<=e1){ tmp[i++]=array[s1++]; } while (s2<=e2){ tmp[i++]=array[s2++]; } } for (int j = 0; j < i; j++) { //注意数组下标，当遇到右边数组合并时，它的第一个下标已经不是零了 array[j+low]=tmp[j]; } }
🚗三 其他排序(非基于比较)
🚖3.1 计数排序
🚘3.2 基数排序
🚔3.3 桶排序
🚉4 总结
可以通过一个表格列举出这些排序的特点，根据排序的需求，选择合适的排序方式！
