排序算法（CompareTo 的实现）
- 对应算法（P153 开始）
一、选择排序法：
遍历数组，每次把数组中最小的放到前面，最后完成排序。(1)在使用泛型时，要说明泛型实现 Comparable 接口
public static <E extends Comparable> sort(E[] arr)
对于 compareTo() 返回 int 类型， -1（<） ， 0 (=) ，1 (>)
(2)类在实现接口时，需要说明类型
public class Student implements Comparable<Student>
(3)ToString 方法
String.format(); // 将 String 格式化// 也可以使用 StringBuilder@Overridepublic String toString(){StringBuilder res = new StringBuilder();res.append(anotherString);return res.toString();}
(4)实现接口以及泛型后的选择排序算法
public static <E extends Comparable<E>> void sort(E[] arr) {for (int i = 0; i < arr.length; i++) {int minIndex = i;for (int j=i;j<arr.length;j++){if(arr[j].compareTo(arr[minIndex])<0){minIndex = j;}}swap(arr, i , minIndex);}}private static <E> void swap(E[] arr, int i , int j){E t = arr[i];arr[i] = arr[j];arr[j] = t;}
1.复杂度分析：
对于二重循环，复杂度为 O((n+1)*n) => O(n^2)
2.在进行排序时，需要验证排序是否成功，需要写一个 Helper 进行验证
public static <E extends Comparable<E>> Boolean isSorted(E[] arr) {for (int i = 1; i < arr.length; i++) {if (arr[i - 1].compareTo(arr[i]) > 0) {return false;}}return true;} // 测试是否正常排序
3.将测试方法进行封装，可以利用反射来对应不同的排序方法
public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {long startTime = System.nanoTime();if (sortName.equals("SelectionSort")) // 可以用反射来写SelectionSort.sort(arr);long endTime = System.nanoTime();double time = (endTime - startTime)*1.0 / 1000000000;if (!SortingHelper.isSorted(arr)) { // throw ExceptionSystem.out.println("failed");throw new RuntimeException("未正确排序");}System.out.println(String.format("%s ,n = %d : %f s", sortName, arr.length, time));}
二、插入排序
插入排序，每次把现在的那个数与前面的数进行比较，然后交换，最后遍历完所有index, 即可完成排序。
eg:/// 1 4 3 5 7//第一次: 1 < 3 1 4 3 5 7// 第二次: 4 < 3 1 3 4 5 7 然后再第二次时，还要比较 3 与 1 若 更小， 则再次交换
未优化
public static <E extends Comparable<E>> void sort(E[] arr) {for (int i = 0; i < arr.length; i++) {// 选择 index = i 上的数// 再遍历 j = 0 到 j = i 处的数，假如更小，则交换for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {swap(arr, j, j - 1);}}}public static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {E temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
优化（空间复杂度）
swap 的 赋值所需的空间复杂度比 CompareTo(o) 所需要的高
public static <E extends Comparable<E>> void sort2(E[] arr) {for (int i = 0; i < arr.length; i++) {// 获取 index = i 处的值E t = arr[i];int j ;//假如 arr[j] < arr[j-1] , 将 arr[j-1] 后移给 arr[j],j--;// 因为每次排序，index = i - 1 时都已经排好// 所以 若 t.compare(arr[j-1]) > 0, 在 就之前的数已经完成排序// j 位置的数字就是t;for(j = i; j> 0 && t.compareTo(arr[j-1]) < 0;j--){arr[j] = arr[j-1];}arr[j] = t;}}
重要特性
- 循环终止条件，内层循环提前终止的机制。
- 对于有序数组，插入排序法的复杂度为O(n)。
- 对于插入算法，平均状态下仅需要 n^2/4 ，但是赋值过程比比较过程运行速度慢，因此可能性能更好。
- 比较二者，对于大部分排序比较好的情况，比如银行，使用插入排序比选择的遍历次数要更少，运行速度就更快。
因为选择排序始终需要遍历n^2次，而假如是插入排序，最好情况下仅需要O(n) 次。
三、归并排序（分治思想）
- 分治思想就是把 较大规模的问题，不断分为更小规模的问题进行处理，再将处理结果进行合并。从而获得大规模问题的结果。
- 排序过程：将两个区间进行排序 [l,mid] 和 [mid, r]区间
- 归并过程：使用两个 index , i 与 j ，分别对[l, mid] 与 [mid + 1, r] 进行排序。从而将[l,r]数组进行合并的过程，称为合并过程。
- 为非原地排序
1.实现代码
```java // 分别对 [l, mid] 和 [mid ,r] 进行排序 public E[] sort(E[] arr){ E[] temp = Arrays.copyOfRange(arr,0,arr.length); return mergeSort(arr, 0 , arr.length - 1 , temp); }
public E[] mergeSort(E[] arr, int l, int r, E[] temp){
// 当 l >= r 时，数组中[l,r]仅一个元素，无需排序
int mid = l + (r - l) /2; // 防止整型溢出
if(l < r){
mergeSort(arr, l, mid,temp);
mergeSort(arr, mid+1, r,temp);
merge(arr, l, mid, r,temp);
}
return arr;
}
public void merge(E[] arr, int l, int mid ,int r, E[] temp){ System.arraycopy(arr,low,temp,low,r-l+1); //复制arr[l,r]因为每次进行合并后，arr都会变化 // 创建 i, j 下标，对[l,mid] [mid+1,r] 进行遍历 // 创建 k 下标，遍历 temp[k] 数组 int i = l, j = mid + 1; for(int k = l; k <= r; k++){ // 当 i > mid 时，直接将 arr[j] 放入temp 中 // 要先判断，是因为如果不在前面判断的话，容易和后面发生冲突 if(i > mid){ temp[k] = arr[j]; j++; }else if(j > r){ temp[k] = arr[i]; i++; }else if(arr[i].compareTo(arr[j]) < 0){ temp[k] = arr[i]; i++ }else if(arr[i].compareTo(arr[j]) >= 0){ temp[k] = arr[j]; j++; } } // 将 temp中排好的序，赋值给 arr for(int k = l; k <= r; k++){ arr[k] = temp[k]; } }
<a name="OMPje"></a>### 2.使用插入排序对较小的数组进行优化当 r - l < 16 使用 插入排序进行排序可能会更快```java// merge 部分不变// 更改 mergeSort() 方法public E[] mergeSort(E[] arr, int l, int r){// 当 l >= r 时，数组中[l,r]仅一个元素，无需排序int mid = l + (r - l) /2; // 防止整型溢出if(r - l < 16){inseration(arr, l ,r);return arr;}mergeSort(arr, l, mid);mergeSort(arr, mid+1, r);merge(arr, l, mid, r);}
3.使用递归条件进行优化
当 arr[mid] < arr[mid + 1] 时， 由于两侧均是有序的，所以如果成立，则不需要再次进行 merge 合并排序
public E[] mergeSort(E[] arr, int l, int r){ // 当 l >= r 时，数组中[l,r]仅一个元素，无需排序 int mid = l + (r - l) /2; // 防止整型溢出 if(r - l < 16){ inseration(arr, l ,r); return arr; } mergeSort(arr, l, mid); mergeSort(arr, mid+1, r); if(arr[mid].compareTo(arr[mid+1]) < 0){ merge(arr, l, mid, r); } }4.复杂度分析
越往下一层 n 的规模就降低为 n / 2, 进行 比较需要 n / 2 次，进行赋值需要 n / 2次
O = O( n ) + 2O( n / 2) + 4O( n / 4 ) 进行等比数列相加
最终获得时间复杂度为 O(nlogn);对于有序数组，由于不需要 merge , 故 时间复杂度为 O(n);
5.自底向上实现归并排序
同样使用 以上的三种优化方式
// 自底向上进行排序 // 非递归实现 public void mergeSort(E[] arr, int l , int r){ // 对 size 不断增加，从而规定 [l,mid] [mid+1,r]的范围，再进行 merge // 将所有数组， 划分为 [left, left + 15] [left+16,left+31]这样的数组，再进行merge for(int i = left; i < r ; i+=16){ // 这里要要判断是否越界 // 假如取 i = r, 则 inseration(i,i) 没有必要 inserationSort(arr, i , Math.min(i + 15, r)); return; } // 每次 size 都需要翻倍 for(int size = 16; size < r - l + 1; size +=size){ // 每次 merge 范围 [i , i + size, i +size + size - 1]; for(int i = left; i + size < r; i += size + size) if(arr[i + size - 1].compareTo(arr[i + size]) < 0){ // i + size < r 因为如果 >= r 则 merge 无法继续进行 // 同理 size < r-l +1 ,这样 r 作为右边界进行 merge， mid 不会等于 r merge(arr, i, i + size -1, Math(i+size+size -1 ,right)); } } }归并相关问题：leetcode Offer.51
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ 数组中的逆序对
class Solution{ // 每次进行排序时，由于 两部分的数组都是有序的，所以只需要考虑 arr[mid+1, r] 部分 // arr[mid+1]每在 arr[i] 前排入一个，就产生 mid - i + 1 个逆序数对 public int reversePairs(int[] nums){ int[] temp = new int[nums.length]; return sort(nums, 0 , nums.length - 1); } private int sort(int[] nums, int l, int r, int[] temp){ if(l < r){ int mid = l + (r - l) / 2; int res = 0; res += sort(nums, l, mid,temp); res +=sort(nums, mid + 1, r,temp); if(nums[mid] > nums[mid + 1]){ res +=merge(nums, l, mid, r, temp); } return res; } return 0; } private int merge(int[] nums, int l, int mid, int r,int[] temp){ int res = 0; int i = l, j = mid + 1; for(int k = l; k <= r; k++){ if(i > mid){ temp[k] = nums[j]; j++; } else if(j > r){ temp[k] = nums[i]; i++; } else if(nums[j].compareTo(nums[i]) < 0){ temp[k] = nums[j] res += mid - i + 1; j++; }else{ temp[k] = nums[i]; i++; } } return res; } }
这里我们使用递归进行实现 ```java // 合并 arr[l, mid) 和 arr[mid, r) private void merge(int[] arr, int l ,int mid, int r, int[] aux){ System.arraycopy(arr,l , aux, l , r - l); // 因为取不到 r, 所以长度为 r - l int i = l, j = mid; int k = l; for(; k < r; k++){if( i >= mid ){ aux[k] = arr[j]; j++; }else if( j >= r ){ aux[k] = arr[i]; i++; }else if(arr[j] < arr[i]){ aux[k] = arr[j]; j++; }else{ aux[k] = arr[i]; i++; }} for(k = l; k < r; k++){
arr[k] = aux[k];} }
// 对arr[l,r) 进行归并排序 // 说明 l < r - 1 // 因为当 l = r - 1 时，循环结束 private void sort(int[] arr, int l, int r, int[] temp){ if(l >= r -1 ){ return ; } int mid = l + (r - l) / 2; sort(arr, l ,mid, temp); sort(arr, mid, r, temp); if(arr[mid - 1] > arr[mid]){ merge(arr, l , mid , r, temp); } }
<a name="aUI3Y"></a>
## （**）四、快速排序：
- 快速排序的基本思想也是分治法
- **target 为 头部第一个元素**
- **遍历将 小于 target 放到前面， 将大于 target 的放到后面**
- **把最后的 头部元素 和 小于 target 的最后元素互换，完成排序**
- **然后再次分别对前后的元素进行排序**
<a name="GnFEU"></a>
#### 一、partition 基本实现：
```java
public void QuickSort(int[] arr, int l, int r){
if(l < r){
int p = partition(arr, l ,r);
QuickSort(arr,l,p-1);
QuickSort(arr,p+1,r);
}
return;
}
public int partition(int[] arr, int l, int r){
int target = arr[l];
int i = l, int j = l + 1;
while(j <= r){
if(arr[j] < target){
i++;
swap(arr, i, j);
}
j++;
}
swap(arr,l,i);
return i;
}
public void swap(int[] arr, int l, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
- 随机化优化：
当数组大部分为有序的数组时，算法退化为o(n^2) 级别
// 1 2 3 4 5 6 = arr
int p = partition(0,5,arr);
p = 0;
sort(arr,0,0); = > return arr[0,0] = > 1
sort(arr, 1,5); => int p = partition(2, 5, arr) => 1; => sort(arr, 0, 0)
= > sort(arr,2,5)
// 可以发现每个数都需要进行依次遍历， 而且是按从左到右依次排序
// 每进行一次 partition 都需要进行 n 次比较，一共有 n 个数， 故退化为 O(n^2) 级别算法
添加随机化，让 p 不是每次都是从左向右，从而防止退化为 O(n^2) 级别
// 将 random 对象传入，获取一个随机数，与 l 处的数进行交换
public int partition(int[] arr, int l, int r, Random rnd){
// 添加随机化
int p = rnd.nextInt(r- l + 1) + l; // .nextInt() 表示取 0 ~ r - l 内的数， 加上 l 就包括了整个范围
swap(arr, p, l); //进行交换
int target = arr[l];
int i = l, int j = l + 1;
while(j <= r){
if(arr[j] < target){
i++;
swap(arr, i, j);
}
j++;
}
swap(arr,l,i);
return i;
}
- 对于较小的数组，使用插入排序进行优化
就像之前的归并排序一样，对于较小的数组，使用插入排序速度可能会更快
// 更改调用递归的部分
public void QuickSort(int[] arr, int l, int r){
if( r - l <=16)
inserationSort(arr, l , r);
return;
}else if( l < r ) {
int p = partition(arr, l ,r);
QuickSort(arr,l,p-1);
QuickSort(arr,p+1,r);
}
}
-使用双路排序
对于数组中所有元素都相同的情况，算法将会退化为 O ( n ^ 2) 级别
// 0 0 0 0 0 0 arr
// 假如使用原来的算法
int p = (arr, l ,r) = > int p = rand; swap(arr, p, l);
// 对于相同的元素，负责对元素最终位置进行记录的 i 不会移动， 即数组的元素不会互换
// p = 0;
QuickSort(arr, l , -1) => if( l > r) return ;
QuickSort(arr, 1, r) ==> int p = 1 => QuickSort(arr,1,0) => return
=> QuickSort(arr,2,r)
每次都返回一个 arr[0,0] 与 arr[i,r]的数组Sort
O ( n ) = n + (n-1) + ... + 1 = O(n(n+1)/2) = O(n^2)
// 故使用双路排序，减少循环
// 循环下标，分别从两端过来，当相等时，结束循环
public int partition(int[] arr, int l, int r){
// 添加随机化
int p = rnd.nextInt(r- l + 1) + l; // .nextInt() 表示取 0 ~ r - l 内的数， 加上 l 就包括了整个范围
swap(arr, p, l); //进行交换
int i = l, j = r;
while(i < j){
if(arr[j] < arr[l]){
i++;
swap(arr,i,j);
}else{ // arr[j] >= arr[l]
j--;
}
}
swap(arr, i, l);
return i;
}
-使用三路排序
对于上面所有元素都相同的情况，实际上经过第一次排序后，就能确定都为完全一致的元素，不需要再次排序
// 注意不要从后往前进行循环， 因为 对于 当 arr[j] == target; 需要进行 swap(),但是此时无法确定 arr[k] 是否 == target 或者小于 target
public int partition(int[] arr, int l, int r){
// 添加随机化
int p = rnd.nextInt(r - l + 1) + l; // .nextInt() 表示取 0 ~ r - l 内的数， 加上 l 就包括了整个范围
swap(arr, p, l); //进行交换
// 数组分为 arr[l, i - 1] arr[i , j] arr[j+1, r]
// 当 k == j时，循环结束
// 开始情况下， 应该为三个空数组
int i = l , k = l + 1 , j = r;
while( k < j ){
if(arr[k] < arr[l]){
i++;
swap(arr, i, k);
k++
}else if( arr[k] == arr[l]){
k++;
}else{ // arr[k] > arr[l]
swap(arr,j,k);
j--;
}
}
- 确定好区间以及循环不变量，要分别考虑多种情况
二、复杂度分析;
对于快速排序算法，实际上为一种不稳定算法，需要不断的进行优化，最后优化为三路排序算法。
对于这类将问题拆解为更小范围的问题，可以用数来理解，当一侧没有元素，而另一侧元素较多时，算法就会退化。
此时算法时间复杂度为： 每次进行一次操作 都需要对 n - 1 个数进行遍历//// Sort[ arr, l , r ] /// Sort[arr, l, l] Sort[arr, l+1, r]
O( n ) = O （ n ^ 2 / 2 ) = O( n ^2）
在理想状况下 ， 每次都分为 n / 2 的理想状况
/// Sort[arr, l, r]
/// Sort[arr, l, l + (r - l) / 2] Sort[arr, mid + 1, r]
O ( n ) = 2O(n/2) + n / 2 = 2 ( 2 O( n /4) + 4/ n ) + n/2 == O(n logn) 级别
但是一般情况下，还是复杂度接近 O ( n log n ) 级别
三、相关的 leetcode 问题
// 可以使用 快速排序的三路排序， 但是此时 target 为固定值
// 注意原地排序
// [l, i - 1] [i , j - 1] [j, r]
class Solution {
public void sortColors(int[] nums) {
int i = -1, j = nums.length, k = 0;
while( k < j ){
if(nums[k] < 1){
i++;
swap(nums, i, k);
k++;
}else if (nums[k] == 1){
k++;
}else{
j--;
swap(nums, j, k);
}
}
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/ 最小的k个数
// 每次进行排序时， partition 所返回的索引，就是该数在其中的位置
// 前k个数，则为 0 ~ k - 1, 即当 p = k - 1 时，返回 arr, 取前 0 ~ k-1 即可
class Solution{
public int[] getLeastNumber(int[] arr, int k){
return Arrays.copyOfRange(arr, 0, k - 1);
}
public void sort (int[] arr, int l, int r, Random rnd, int target){
if(l >= r) return ;
int p = l + rnd.nextInt(r - l + 1);
swap(arr, p , l);
int j = l, i = l + 1, k = r + 1;
while( i < k ){
if( arr[i] > arr[l]){
j++;
swap(arr, j, i);
i++;
}else if(arr[i] == arr[l]){
i++;
}else{
k--;
swap(arr, i ,k);
}
}
swap(arr, l , i)
if( i == target - 1){
return ;
}
sort(arr, l, i - 1, rnd ,target);
sort(arr, j+1,r, rnd ,target);
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
若有收获，就点个赞吧
0 人点赞
