排序算法(下)
2.排序算法(O(nlogn)时间复杂度)
2.1归并排序（自上而下）
核心思想:
将对于的数组以 size = arr.length / 2 递归下去，直到size = 1时就遍历到数组的每一个元素，而最核心的思想是如何将两个有序的数组合并成一个数组且有序。
方法：拷贝待排序的两组数组（为了好理解表述的是两组数组，其实待排序数组中的一段），然后维护三个索引值。
cope出的数组：copeArr[left,right]
第一个有序数组：arr1[left,mid]
第二个有序数组：arr2[mid+1,right]
每次拿出第一个与第二个数组的元素来比较
//伪代码
if(arr1[left] > arr2[mid + 1]){
copeArr[left] = arr2[mid + 1];
//扫描arr2数组 索引 +1
//扫描copeArr数组 索引 +1
//反之
}
排序分解图:
/**
* 归并操作 将 arr1[left...mid] arr2[mid+...right]两数组合并
* @param {[type]} int[] arr [待排序数组]
* @param {[type]} int left [左边索引]
* @param {[type]} int mid [中间索引]
* @param {[type]} int right [右边索引]
* @return {[type]} [void]
*/
privite static void merge(int[] arr,int left,int mid,int right){
int[] aux = Arrays.copyOfRange(arr, left, right);
//第一个数组的开始索引
int j = left;
//第二个数组的开始索引
int k = mid + 1;
for(int i = left ; i <= right ; i++){
if(k > right){
arr[i] = aux[k - left];
k++;
}else if(j > mid ){
arr[i] = aux[j - left];
j++;
}else if(aux[j - left] > aux[k - left]){
arr[i] = aux[k - left];
k++;
}else {
arr[i] = aux[j - left];
j++;
}
}
}
privite static void mergeSort(int[] arr, int left,int right){
if(left >= right){
return;
}
int mid = (right + left) / 2;
//从左边开始分割
mergeSort(arr,left,mid);
//从右边开始分割
mergeSort(arr,mid+1,right);
//归并
merge(arr,left,mid,right);
}
public static void mergeSort(int[] arr){
mergeSort(int[] arr,0,arr.length - 1);
}
总结：这样就可以通过并列寻找，每一次内循环都是从两个方向来排序的方式减少内循环的次数，达到时间复杂度为O(nlogn)的级别
2.1.1归并排序优化
优化一:
优化递归到底的情况，在最后的小序列时，可以采用插入排序算法。因为小序列本就有序性很高，这是插入排序会比归并排序的时间复杂度的期望值要高。
此也为所有O(nlogn)算法的通用优化方案。
优化二：
对于近乎有序的数组排序时，可以加上一则判断，在进入merge方法前，判断 arr[min+1] > arr[mid]为true时，说明两数组本就有序，不需要merge。
但是这种优化也不一定会有效，可以参考排序算法 (O(n^2)时间复杂度)，中测试的优化冒泡排序的数据。 原因：在jvm中产生了多余值及更多赋值，导致消耗性能。
优化过程：
private static void mergeSort(int[] arr, int left, int right) {
if (right - left <= 15) {
SimpleSort.insertSortInt(arr, left, right);
return;
}
if (left - right >= 0) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
if (arr[mid] > arr[mid + 1]) {
merge(arr, mid, left, right);
}
}
2.2归并排序另一种实现（自底向上）
核心思想：
在上述的 自上而下 的归并，变换成，自底向上的过程，是将数组中的每一个元素向上开始做归并。也就是先归并最小单位（每个元素），以后每一次归并上一次单位的2倍。外循环控制每一次归并的最小单位，内循环归并两个相邻最小单位中的元素。 例如：
3 | 1 | 4 | 6 | 5 | 7 | 8 | 9 第一次合并 index(0~1) (2~3) (4~5) (6~7) 1 3 | 4 6 | 5 7 | 8 9 第二次合并 index(0~3) (4~7) 1 3 4 6 | 5 7 8 9 第三次合并 index(0~7) 1 3 4 5 6 7 8 9
/**
* 自下而上 归并排序
* @param arr
*/
public static void mergeSortBU(int[] arr){
int n = arr.length;
//外循环 找出需要归并的两个数组
for (int sz = 1; sz < n; sz *= 2) {
for (int i = 0; i< n - sz;i+= sz + sz){
//对于 arr[i ~ i+sz-1]和 arr[sz ~ i+sz+sz-1]这两个数组判断合并
merge(arr,i+sz-1,i,Math.min(i+2*sz-1,n-1));
}
}
}
//延续上述，2.1.1归并排序优化 后为
/**
* 自下而上 归并排序
* 常规优化，对于小于一定数量的数组排序 用 插入排序
*
* @param arr
*/
public static void betterMergeSortBU(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i += 16) {
SimpleSort.insertSortInt(arr, i, Math.min(i + 15, n - 1));
}
//外循环 找出需要归并的两个数组
for (int sz = 16; sz < n; sz += sz) {
for (int i = 0; i < n - sz; i += sz + sz) {
//对于 arr[i ~ i+sz-1]和 arr[sz ~ i+sz+sz-1]这两个数组判断合并
if (arr[i + sz - 1] > arr[i + sz]) {
merge(arr, i + sz - 1, i, Math.min(i + 2 * sz - 1, n - 1));
}
}
}
}
测试：
测试用例 长度 1_000_000，元素随机范围为 [0,1_000_000]
第一次
mergeSort-->0.139 s
mergeSortBU-->0.17 s
betterMergeSortBU-->0.133 s
第二次
mergeSort-->0.136 s
mergeSortBU-->0.153 s
betterMergeSortBU-->0.138 s
测试用例 长度 10_000_000，元素随机范围为 [0,10_000_000]
第一次
mergeSort-->1.447 s
mergeSortBU-->1.589 s
betterMergeSortBU-->1.376 s
总结：优化效果显著
2.2快速排序(20世纪最伟大的算法之一)
核心思想:
在数组中随机拿出一个元素(通常是第一个)，在整个待排序的数组中找到其排序后的位置，然后与该位置元素进行交互。且将小于其元素放置其左边，大于其元素放在右边。然后通过此元素，将数组分割成两部分，继续对其两部分做快速排序，直到最后数组有序。
排序分解图：
如何在数组中找到一个元素有序时的位置？
partition实现图解：
/**
* 快速排序的核心思想
* <p>
* 遍历一次就找到当前元素 排序好的结果下 所在的数组的位子
*
* @param arr 当前数组
* @param l 左边边界
* @param r 右边边界
* @return 返回 arr[p] 使得在数组 arr[l ~ p-1] < arr[p] < arr[p+1 ~ r]
*/
private static int partition(int[] arr, int l, int r) {
//标记元素
int p = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i]<p){
j++;
CommonUtils.swap(arr,i,j);
}
}
CommonUtils.swap(arr,l,j);
return j;
}
/**
* 快速排序算法
*
* @param arr 数组
* @param l 左边边界
* @param r 右边边界
*/
private static void quickSort(int[] arr, int l, int r) {
//递归的结束条件
if (l >= r) {
return;
}
//返回已经排好序的index位子
int partition = partition(arr, l, r);
//左 右同时继续 操作
quickSort(arr, l, partition - 1);
quickSort(arr, partition + 1, r);
}
完成二十世纪最伟大的算法之一后测试一下：
测试用例 长度 1_000_000，元素随机范围为 [0,1_000_000]
第一次
quickSort-->0.079 s
第二次
quickSort-->0.076 s 果然很快，不愧是最伟大的算法之一，等等....
测试用例 长度 1_000_000，元素随机范围为 [0,20]
Exception in thread "main" java.lang.StackOverflowError !!??! 什么？伟大的算法 尽然栈溢出了？
等等….
测试用例 长度 1_000_000，近乎有序的数组只交互20组
Exception in thread "main" java.lang.StackOverflowError !!??! what?又是栈溢出了？
说好的最伟大的算法呢？原来我们实现的只是一个最基本的快速排序，其还有很多地方需要优化。
分析：
为什么 在数组中 如果 重复的过多后就会栈溢出？
这是因为当我们代码
partition里的if (arr[i]<p)判断，默认将等于p的元素放入了大于p的部分中，而此时分割的位置，在整个数组中是极其不均匀的，且每一次都是大于p多，导致退化为O(n^2)算法，而我们是用递归来实现的，调用太多次，故出现了栈溢出的情况。
为什么 在数组中 如果 数组近乎有序时会栈溢出？
原因是，当近乎有序时，分割的位置，同样也是极其不均衡的，退化为
O(n^2)。
2.2.1快速排序问题解决
上节出现的问题，这节集中解决。
2.2.1.1 解决方案1：
近乎有序的数组quicksort栈溢出：
这里只需要将每一次查找的元素，随机就可以了（我们之前`int p = arr[l];`
是直接拿了第一个元素，导致数组分割后极其不均匀）。
具体实现：
private static int partition(int[] arr, int l, int r) {
Random random = new Random();
int rand = l+random.nextInt(r - l + 1);
CommonUtils.swap(arr,l,rand);
//....
//...
}
2.2.1.2 解决方案2：
多重复元素，栈溢出：
将`if (arr[i]<p)`判断中，相等p的元素，*均匀*分布到两侧(大于`p`,小于`p`)，
即两路查找，从数组的开始，向后查找，和数组的结束，向前查找。
具体实现：
/**
* 两路寻找，将相等的那一部分分布大于其，和小于其部分。
* <p>
* 思路，从数组开始的地方查找，同时也从后向前查找
*
* @param arr 当前数组
* @param l 左边边界
* @param r 右边边界
* @return
*/
private static int partition2Ways(int[] arr, int l, int r) {
Random random = new Random();
int rand = l + random.nextInt(r - l + 1);
CommonUtils.swap(arr, l, rand);
//标记元素
int p = arr[l];
//arr[l+1 ~ j) <= p; arr(j ~ r] >= p
int i = l + 1;
int j = r;
while (true) {
// 这里 i <= r 有等号 是保证扫描 [l+1...r]区间内所有的元素
//arr[i] < p 不加等号，当加上等号时，若是出现 连续相等的情况，会使 生成 的树及其不平衡，进而退化到 O(n^2)
while (i <= r && arr[i] < p) {
i++;
}
// j >= l + 1 有等号 是保证扫描 [l+1...r]区间内所有元素
// arr[j] > p 不加等号，与上同理
while (j >= l + 1 && arr[j] > p) {
j--;
}
if (i > j) {
break;
}
CommonUtils.swap(arr, i, j);
i++;
j--;
}
CommonUtils.swap(arr, l, j);
return j;
}
思考为何 while (i <= r && arr[i] < p)中不能是 while (i <= r && arr[i] <= p)
2.2.1.3 解决方案3：
多重复元素，栈溢出：
将`arr[i]=p`的元素，新开一组记录，即三路查找。
具体实现：
/**
* 三路查找核心，遍历一遍数组，其元素与比判断元素的比较
* 大于 放入 arr[gt...r]中 既是 gr-- 交换(gt,i)，i 不动
* 等于 放入 arr[lt+1...i)中 即不需要交换 但 i++
* 小于 放入 arr[l+1...lt]中 既是 lt++ 交换(lt.i), i++
*
* @param arr
* @param l
* @param r
* @return
*/
private static void partition3Ways(int[] arr, int l, int r) {
Random random = new Random();
int rand = l + random.nextInt(r - l + 1);
CommonUtils.swap(arr, l, rand);
//标记元素
int p = arr[l];
//设置三数组边界，使得其初始化时为空数组。
//int[l+1...lt] < p
int lt = l;
//int[gt...r] < p
int gt = r + 1;
//int[lt+1...i) = p
int i = l + 1;
while (gt > i) {
if (arr[i] > p) {
gt--;
CommonUtils.swap(arr, i, gt);
} else if (arr[i] < p) {
lt++;
CommonUtils.swap(arr, i, lt);
i++;
} else {
i++;
}
}
CommonUtils.swap(arr, l, lt);
//此时 lt-1 是因为第一个元素交换后，将arr[l+1...lt]变成了--> arr[l,lt-1]
quickSort3Ways(arr, l, lt-1);
quickSort3Ways(arr, gt, r);
}
2.3测试与总结
测试用例 数量均为 1_000_000
第一次
quickSort2Ways : 多数重复元素 数组-->0.059 s
quickSort2Ways : 接近有序 数组-->0.047 s
quickSort2Ways : 随机无序 数组-->0.095 s
quickSort3Ways : 多数重复元素 数组-->0.028 s
quickSort3Ways : 接近有序 数组-->0.065 s
quickSort3Ways : 随机无序 数组-->0.143 s
第二次
quickSort2Ways : 多数重复元素 数组-->0.057 s
quickSort2Ways : 接近有序 数组-->0.063 s
quickSort2Ways : 随机无序 数组-->0.091 s
quickSort3Ways : 多数重复元素 数组-->0.023 s
quickSort3Ways : 接近有序 数组-->0.077 s
quickSort3Ways : 随机无序 数组-->0.136 s
第三次
quickSort2Ways : 多数重复元素 数组-->0.056 s
quickSort2Ways : 接近有序 数组-->0.034 s
quickSort2Ways : 随机无序 数组-->0.096 s
quickSort3Ways : 多数重复元素 数组-->0.028 s
quickSort3Ways : 接近有序 数组-->0.065 s
quickSort3Ways : 随机无序 数组-->0.126 s
总结： 测试数据看出，三路查询，在这三种情况下综合表现最好。所以一般系统默认排序都为三路查询， 在完全随机的情况下，虽然 耗时 是 两路查询的两倍，但是考虑到实际情况，在系统中很少出现对完全随机情况的排序。
