参考文章
慕课网数据结构与算法课程
|
|
使用归并思想，也是分治思想，先走向递归深处，即分的过程，直到递归终止条件为止
对于递归终止条件，一般为只有一个叶子节点，为了优化性能，对于小数据采用插入排序法
分的方案，是二分法，每次找区间的中间值，注意数据越界情况，然后将分化的两个区间继续二分
合的方案，是新建一个数组，将要合并的两个数组逐个比较，将较小元素依次放入新数组中，最后将新数组copy到原数组中进行数值覆盖，注意，数组索引的对应问题
为了优化性能，在递归前，就将temp新数组容器准备好，依次传入即可，以免每次递归时新建开销
import java.util.Arrays;
import bubbleSort.ArrayGenerator;
import bubbleSort.SortingHelper;
import insertionSort.InsertionSort;
/**
*
* @author LiuS
* 归并排序多用于对象排序，可以稳定排序
* java库中，TimSort是改进的MergeSort,其中TimSort是直接分成n块，然后两两归并
* 小于某值，用二分插入排序
* 小数据用插入原因是，深度已经不是主要影响因素，新建数组，两两比较复杂度会高于插入过程
*/
public class MergeSort {
private MergeSort() {}
private static final int MIN_MERGE = 32;
public static <E extends Comparable<E>> void sort(E[] arr) {
if(arr == null || arr.length <= 2) return;
E[] temp = Arrays.copyOf(arr, arr.length); // 开辟和额外空间，减少每次递归重新开辟空间的消耗
sort(arr, 0, arr.length - 1, temp);
}
private static <E extends Comparable<E>> void sort(
E[] arr, int left, int right, E[] temp) {
// 递归终止条件，小于某一值，用插入法优化
if((right - left) <= MIN_MERGE) {
InsertionSort.sort(arr, left, right);
return; // 千万别忘记返回终止
}
// if(left >= right) return;
int mid = left + (right - left) / 2;
sort(arr, left, mid, temp);
sort(arr, mid + 1, right, temp);
if(arr[mid].compareTo(arr[mid + 1]) > 0)
merge(arr, left, mid, right, temp);
}
private static <E extends Comparable<E>> void merge(E[] arr, int left, int mid, int right, E[] temp) {
int i = left; // 左序列指针
int j = mid + 1; // 右序列指针
int t = left; // 新数组指针
while(t <= right) { // 一定要找好数组的索引位置
if(i > mid) {
temp[t ++] = arr[j ++];
} else if(j > right) {
temp[t ++] = arr[i ++];
} else if(arr[i].compareTo(arr[j]) <= 0) {
temp[t ++] = arr[i ++];
} else if(arr[i].compareTo(arr[j]) > 0) {
temp[t ++] = arr[j ++];
}
}
// 将temp数组元素copy到arr数组中，注意索引位置一一对应
// temp = Arrays.copyOfRange(arr, left, right); // 此方法索引还是从0开始
System.arraycopy(temp, left, arr, left, right - left + 1);
// int t = 0;
// while(left <= right){
// arr[left++] = temp[t++]; // arr[left++] = temp[left++];不对，left每次加2了
// }
}
}
public static void main(String[] args) {
int n = 1000000;
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
SortingHelper.sortTime("MergeSort", arr);
}
MergeSort, n = 1000000 : 0.490878 s
|
|
同样也是分治递归思想，先以分界点将区间分为两个区域，即小于分界点元素的值域和大于分界点的值域，分别在分界点左右两边
对于区分左右区间并找到分界点的partition过程，主要是双指针法，分别定义两个指针变量指向小于分界点和大于分界点的数，并依次移动遍历，并返回分界点位置，以供下一层递归调用
递归终止条件是区间元素只有一个，即上一个分界点的左右区间只有一个元素，由于分别小于和大于分界点，故一定可以与分界点构成有序数列
性能优化：
单路快速排序法图解：
import java.util.Random;
import bubbleSort.ArrayGenerator;
import bubbleSort.SortingHelper;
public class QuickSort {
private QuickSort() {}
/**
*
* @param <E> 支持泛型
* @param arr 传入数组
* 单路快速排序算法
*/
public static <E extends Comparable<E>> void sort1Way(E[] arr) {
if(arr == null || arr.length <= 2) return;
Random rad = new Random();
sort1Way(arr, 0, arr.length - 1, rad);
}
private static <E extends Comparable<E>> void sort1Way(
E[] arr, int left, int right, Random rad) {
if(left >= right) return;
int p = partition(arr, left, right, rad);
sort1Way(arr, left, p - 1, rad);
sort1Way(arr, p + 1, right, rad);
}
/**
* 分治过程，即将目标数组按照分界点区分左右大小区域
* @param <E>
* @param arr， 要处理区间数组
* @param left， 左边界
* @param right， 右边界
* @param rad，传入的随机数辅助对象
* @return， 返回分界点索引位置
*/
private static <E extends Comparable<E>> int partition(
E[] arr, int left, int right, Random rad) {
int radIndex = left + rad.nextInt(right - left + 1); // 找到随机一个索引
swap(arr, left, radIndex); // 将随机索引指向的值作为分界点，放在第一个位置
E v = arr[left]; // 定义好分界点
int i = left + 1; // 快指针，遍历数组，遇到小于v的数交换，i - 1 均指向>=v
int j = left; // 慢指针，指向<v的数，从i指向的数中交换所得
for(; i <= right; i ++) {
if(arr[i].compareTo(v) < 0) {
j ++; // 慢指针先开辟空间
swap(arr, i, j); // 新开辟的地址储存<v的数，i交换后依旧指向>=v的数
}
}
swap(arr, j, left); // 将最后一个j指向的小于v的数与v交换，v左边全为小于v的数
return j; // 交换后，j指向的就是v的值，即分界点
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] nums = {100000, 1000000};
for(int n : nums) {
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
SortingHelper.sortTime("QuickSort1Way", arr);
}
}
}
QuickSort1Way, n = 100000 : 0.039567 s
QuickSort1Way, n = 1000000 : 0.359868 s // 大致相差10倍
import java.util.Random;
import bubbleSort.ArrayGenerator;
import bubbleSort.SortingHelper;
public class QuickSort {
private QuickSort() {}
/**
*
* @param <E> 支持泛型
* @param arr 传入数组
* 双路排序算法
*/
public static <E extends Comparable<E>> void sort2Way(E[] arr) {
if(arr == null || arr.length <= 2) return;
Random rad = new Random();
sort2Way(arr, 0, arr.length - 1, rad);
}
private static <E extends Comparable<E>> void sort2Way(
E[] arr, int left, int right, Random rad) {
if(left >= right) return;
int p = partition2(arr, left, right, rad);
sort2Way(arr, left, p - 1, rad);
sort2Way(arr, p + 1, right, rad);
}
/**
* 分治过程，即将目标数组按照分界点区分左右大小区域
* @param <E>
* @param arr， 要处理区间数组
* @param left， 左边界
* @param right， 右边界
* @param rad，传入的随机数辅助对象
* @return， 返回分界点索引位置
*/
private static <E extends Comparable<E>> int partition2(E[] arr, int left, int right, Random rad) {
int radIndex = left + rad.nextInt(right - left + 1);
swap(arr, left, radIndex);
E v = arr[left]; // 分界值
int i = left + 1; // 指向左区域指针
int j = right; // 指向右区域指针
while(true) {
// 保证i-1指针指向的数一定小于v，大于等于v，停止移动，等待处理
while(i <= j && arr[i].compareTo(v) < 0) {
i ++; // i==j,继续循环，表明最后一个位置j指向的数小于v
}
// 保证j+1指针指向的数一定大于v，小于等于v，停止移动，等待处理
while(i <= j && arr[j].compareTo(v) > 0) {
j --; // i==j时继续循环，目的是让j--，使得最后j指向的数小于v，与v交换
}
if(i >= j) break; // 如果指针越界，就要立即终止循环，不能再走，否则j指向的位置就不对了
// i=j能走到这一步，说明i，j均指向v，此时j就是分界点，可以结束循环了
if(arr[i].compareTo(arr[j]) != 0) { // 如果均等于v，可以直接跳过，交换没有意义
swap(arr, i , j);// i指向的值大于v时或j指向的值小于v时，交换，放入正确区间
}
// 交换后，继续遍历，一边等于v，也交换，这样等于v的数均分在两侧
// 处理完相等的元素或要交换的元素后，指针需要继续走，判断下个元素
i ++;
j --;
}
swap(arr, j, left);
return j;
}
public static void main(String[] args) {
int[] nums = {100000, 1000000};
for(int n : nums) {
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("QuickSort1Way", arr);
SortingHelper.sortTime("QuickSort2Way", arr2);
}
}
}
QuickSort1Way, n = 100000 : 0.040037 s
QuickSort2Way, n = 100000 : 0.035355 s
QuickSort1Way, n = 1000000 : 0.352041 s
QuickSort2Way, n = 1000000 : 0.235757 s // 双路快排性能更优
// 三路快排
public static <E extends Comparable<E>> void sort3Way(E[] arr) {
Random rad = new Random();
sort3Way(arr, 0, arr.length - 1, rad);
}
private static <E extends Comparable<E>> void sort3Way(
E[] arr, int left, int right, Random rad) {
if (left >= right)
return;
int radIndex = left + rad.nextInt(right - left + 1);
swap(arr, left, radIndex);
// arr[l + 1,lt]<v,arr[lt+1,i-1]==v,arr[gt,r]>v
// 初始化，使得三个区间都为空区间
int lt = left; // lt为指向左区域指针
int i = left + 1; // i为遍历指针，i-1指向等于v区域
int gt = right + 1; // gt为指向右区域指针
while (i < gt) { // 不是所有的i都加加，用while循环，循环终止i==gt
if (arr[i].compareTo(arr[left]) < 0) {
lt++; // 开辟新空间
swap(arr, i, lt);
i++;
} else if (arr[i].compareTo(arr[left]) > 0) {
gt--;
swap(arr, i, gt);
} else {
i++; // i指向数值等于v，不做任何操作
}
}
swap(arr, left, lt); // 保证lt指向的数等于v
// 处理之后，arr[l,lt -1]<v,arr[lt,i-1]==v,arr[gt,r]>v
// 递归处理< v and > v 的部分就行
sort3Way(arr, left, lt - 1, rad);
sort3Way(arr, gt, right, rad);
}
public static void main(String[] args) {
int[] nums = {100000, 1000000};
for(int n : nums) {
System.out.println("Random Array:");
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
Integer[] arr3 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("QuickSort1Way", arr);
SortingHelper.sortTime("QuickSort2Way", arr2);
SortingHelper.sortTime("QuickSort3Way", arr3);
System.out.println();
System.out.println("Order Array:");
arr = ArrayGenerator.generateOrderedArray(n);
arr2 = Arrays.copyOf(arr, arr.length);
arr3 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("QuickSort1Way", arr);
SortingHelper.sortTime("QuickSort2Way", arr2);
SortingHelper.sortTime("QuickSort3Way", arr3);
System.out.println();
System.out.println("Same Value Array:");
arr = ArrayGenerator.generateRandomArray(n, 1);
arr2 = Arrays.copyOf(arr, arr.length);
arr3 = Arrays.copyOf(arr, arr.length);
//SortingHelper.sortTime("QuickSort1Way", arr);
SortingHelper.sortTime("QuickSort2Way", arr2);
SortingHelper.sortTime("QuickSort3Way", arr3);
System.out.println();
}
}
Random Array:
QuickSort1Way, n = 100000 : 0.039846 s
QuickSort2Way, n = 100000 : 0.036051 s
QuickSort3Way, n = 100000 : 0.059368 s
Order Array:
QuickSort1Way, n = 100000 : 0.009889 s
QuickSort2Way, n = 100000 : 0.005750 s
QuickSort3Way, n = 100000 : 0.049616 s
Same Value Array:
QuickSort2Way, n = 100000 : 0.005404 s
QuickSort3Way, n = 100000 : 0.000580 s
Random Array:
QuickSort1Way, n = 1000000 : 0.377061 s
QuickSort2Way, n = 1000000 : 0.243519 s // 双路快速排序法综合性能有优势
QuickSort3Way, n = 1000000 : 0.520272 s
Order Array:
QuickSort1Way, n = 1000000 : 0.217499 s
QuickSort2Way, n = 1000000 : 0.060744 s // 双路快速排序法综合性能有优势
QuickSort3Way, n = 1000000 : 0.379908 s
Same Value Array:
QuickSort2Way, n = 1000000 : 0.068403 s
QuickSort3Way, n = 1000000 : 0.001912 s // 三路快速排序法性能有优势
|
|
参考文章1，参考文章2
1.首先将无序的序列进行堆化，构建成一个最大堆或最小堆，本文以最大堆为例
2.进行排序，因为堆顶元素是最大，将堆顶元素与堆中最后一个元素交换，将最大元素"沉"到数组末端,堆中元素总数减一
3.新的数据结构堆化调整，同样采用自上而下堆化处理，因为涉及到堆中元素总数变化，函数设计中要传入size大小的参数，并注意新的堆的大小的维护
扩展：堆的结构，是一颗完全二叉树，完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。
向最大堆中新添加元素图解：
核心代码实现：
...
private Array<E> data; // 自定义动态数组
public void add(E e) {
data.addLast(e); // 因为调用的是辅助类动态数组，size已经在Array中维护了
siftUp(data.getSize() - 1); // 自下往上heapify堆化
}
private void siftUp(int k) {
// 往上heapify过程，注意k不能为根节点
while(k > 0 && data[k].compareTo(data[(k - 1) / 2]) > 0) { // (k-1)/2 父亲节点
data.swap(k, (k - 1) / 2); // swap交换函数在自定义数组中已经定义好
k = (k - 1) / 2; // 再次往上进行heapify
}
}
...
/**
* 自上向下堆化实现
* @param <E>
* @param data ，最大堆结构
* @param k， 向下堆化的起始根节点
* @param n， 最大堆容器的大小
*/
private static <E extends Comparable <E>>void siftDown(E[] data, int k, int n) {
// n是新堆结构的大小，不能用data.length,data数组中一部分排好序的数不参与堆化
while(2 * k + 1 < n) {
int j = 2 * k + 1; // 左子节点索引
if(j + 1 < n && data[j + 1].compareTo(data[j]) > 0) { // 判断左右子节点哪个大
j ++; // 如果右子节点大，j表示右节点
}
if(data[k].compareTo(data[j]) < 0) {
data.swap(k, j); // 以k为根节点的子二叉树，根节点最大
}
k = j; // 继续往下堆化，将改动的子节点作为根节点循环进行，另一个子节点完整不变
}
}
public class HeapSort {
private HeapSort() {};
public static <E extends Comparable<E>> void sort(E[] arr) {
if(arr == null || arr.length <= 2) return;
// 第一步，原地堆化
// 找非叶子节点，自下往上找；找到所有非叶子节点后，再自上往下交换进行堆化
// i为所有非叶子节点，故如果i为右节点，下一步要处理以左节点为根节点的树
// 即所有非叶子节点排列规律是从右往左，从下往上，层Z字行排列
for(int i = (arr.length - 2) / 2; i >= 0; i --) {
siftDown(arr, i, arr.length);
}
// 排序
for(int i = arr.length - 1; i > 0; i --) {
swap(arr, 0, i); // 先交换，将堆顶元素放到指定位置i，[i,n)排好序
siftDown(arr, 0, i); // 对新的大小的堆结构进行堆化，[i,n)数不参与
}
}
/**
* 自上向下堆化实现
* @param <E>
* @param arr ，最大堆结构
* @param k， 向下堆化的起始根节点
* @param n， 最大堆容器的大小
*/
private static <E extends Comparable <E>>void siftDown(E[] arr, int k, int n) {
// n是新堆结构的大小，不能用data.length,data数组中一部分排好序的数不参与堆化
while(2 * k + 1 < n) {
int j = 2 * k + 1; // 左子节点索引
// 判断左右子节点哪个大
if(j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
j ++; // 如果右子节点大，j表示右节点
}
if(arr[k].compareTo(arr[j]) < 0) {
swap(arr, k, j); // 以k为根节点的子二叉树，根节点最大
}
// 继续往下堆化，将改动的子节点作为根节点循环进行，另一个子节点完整不变
k = j;
}
}
private static <E>void swap(E[] data, int k, int j) {
E t = data[k];
data[k] = data[j];
data[j] = t;
}
}
public static void main(String[] args) {
int n = 1000000;
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
Integer[] arr1 = Arrays.copyOf(arr, arr.length);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTime("MergeSort", arr);
SortingHelper.sortTime("QuickSort2Way", arr1);
SortingHelper.sortTime("HeapSort", arr2);
}
MergeSort, n = 1000000 : 0.424197 s
QuickSort2Way, n = 1000000 : 0.331031 s
HeapSort, n = 1000000 : 0.689467 s
小结：为什么快速排序要比堆排序性能好？
堆排序优势主要应用于topK问题