归并排序
一、概念及其介绍
归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
二、适用说明
当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。
归并排序适用于数据量大，并且对稳定性有要求的场景。
三、过程
归并排序是递归算法的一个实例，这个算法中基本的操作是合并两个已排序的数组，取两个输入数组 A 和 B，一个输出数组 C，以及三个计数器 i、j、k，它们初始位置置于对应数组的开始端。
A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置，相关计数器向前推进一步。
当两个输入数组有一个用完时候，则将另外一个数组中剩余部分拷贝到 C 中。
四、Java 实例代码
public class MergeSort {// 将arr[l...mid]和arr[mid+1...r]两部分进行归并private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1int i = l, j = mid + 1;for (int k = l; k <= r; k++) {if (i > mid) { // 如果左半部分元素已经全部处理完毕arr[k] = aux[j - l];j++;} else if (j > r) { // 如果右半部分元素已经全部处理完毕arr[k] = aux[i - l];i++;} else if (aux[i - l].compareTo(aux[j - l]) < 0) { // 左半部分所指元素 < 右半部分所指元素arr[k] = aux[i - l];i++;} else { // 左半部分所指元素 >= 右半部分所指元素arr[k] = aux[j - l];j++;}}}// 递归使用归并排序,对arr[l...r]的范围进行排序private static void sort(Comparable[] arr, int l, int r) {if (l >= r) {return;}int mid = (l + r) / 2;sort(arr, l, mid);sort(arr, mid + 1, r);// 对于arr[mid] <= arr[mid+1]的情况,不进行merge// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失if (arr[mid].compareTo(arr[mid + 1]) > 0)merge(arr, l, mid, r);}public static void sort(Comparable[] arr) {int n = arr.length;sort(arr, 0, n - 1);}// 测试MergeSortpublic static void main(String[] args) {int N = 1000;Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);sort(arr);//打印数组SortTestHelper.printArray(arr);}
}Java实例代码解析
merge方法：此方法用于合并两个已排序的部分数组。它首先复制需要合并的部分到一个辅助数组中，然后通过三个指针分别指向左半部分的开始、右半部分的开始和目标数组的位置，逐个比较并合并元素。sort方法：这是一个递归方法，用于将数组分割成更小的部分，并调用merge方法来合并这些部分。递归的基本条件是当子数组只有一个元素时停止递归。main方法：这是程序的入口点，用于测试归并排序算法。它生成了一个随机数组，调用了sort方法对其进行排序，并打印了排序后的结果。
随机化快速排序
一、概念及其介绍
快速排序由 C. A. R. Hoare 在 1960 年提出。
随机化快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
二、适用说明
快速排序是一种比较快速的排序算法，它的平均运行时间是 O(nlogn)，之所以特别快是由于非常精练和高度优化的内部循环，最坏的情形性能为 O(n^2)。像归并一样，快速排序也是一种分治的递归算法。从空间性能上看，快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归，空间复杂度也为O(logn)。
三、过程
在一个数组中选择一个基点，比如第一个位置的 4，然后把4挪到正确位置，使得之前的子数组中数据小于 4，之后的子数组中数据大于 4，然后逐渐递归下去完成整个排序。
如何和把选定的基点数据挪到正确位置上，这是快速排序的核心，我们称为 Partition。
过程如下所示，其中 i 为当前遍历比较的元素位置：
这个 partition 过程用代码表示为：
...
private static int partition(Comparable[] arr, int l, int r){Comparable v = arr[l];int j = l;for( int i = l + 1 ; i <= r ; i ++ )if( arr[i].compareTo(v) < 0 ){j ++;//数组元素位置交换swap(arr, j, i);}swap(arr, l, j);return j;
}...如果是对近乎有序的数组进行快速排序，每次 partition 分区后子数组大小极不平衡，容易退化成 O(n^2) 的时间复杂度算法。我们需要对上述代码进行优化，随机选择一个基点做为比较，称为随机化快速排序算法。只需要在上述代码前加上下面一行，随机选择数组中一数据和基点数据进行交换。
swap( arr, l , (int)(Math.random()*(r-l+1))+l );四、Java 实例代码
/*** 随机化快速排序*/
public class QuickSort {// 对arr[l...r]部分进行partition操作// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]private static int partition(Comparable[] arr, int l, int r){// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivotswap( arr, l , (int)(Math.random()*(r-l+1))+l );Comparable v = arr[l];// arr[l+1...j] < v ; arr[j+1...i) > vint j = l;for( int i = l + 1 ; i <= r ; i ++ )if( arr[i].compareTo(v) < 0 ){j ++;swap(arr, j, i);}swap(arr, l, j);return j;}// 递归使用快速排序,对arr[l...r]的范围进行排序private static void sort(Comparable[] arr, int l, int r){if (l >= r) {return;}int p = partition(arr, l, r);sort(arr, l, p-1 );sort(arr, p+1, r);}public static void sort(Comparable[] arr){int n = arr.length;sort(arr, 0, n-1);}private static void swap(Object[] arr, int i, int j) {Object t = arr[i];arr[i] = arr[j];arr[j] = t;}// 测试 QuickSortpublic static void main(String[] args) {// Quick Sort也是一个O(nlogn)复杂度的算法// 可以在1秒之内轻松处理100万数量级的数据int N = 1000000;Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);sort(arr);SortTestHelper.printArray(arr);}
}Java实例代码解析
partition方法：此方法实现了分区操作。首先随机选择一个基准元素，并将其与数组的第一个元素交换。然后，遍历数组中的其他元素，将小于基准的元素移动到左侧，大于基准的元素移动到右侧。最后，将基准元素放到中间位置，返回其索引。sort方法：这是一个递归方法，用于对数组的指定部分进行快速排序。它首先检查是否需要继续排序（即，子数组至少有两个元素）。如果需要，它会调用partition方法来获取基准元素的索引，然后分别对基准元素左右两侧的子数组进行递归排序。swap方法：用于交换数组中的两个元素。main方法：用于测试快速排序算法。它创建了一个包含100万个随机整数的数组，调用了sort方法对其进行排序，并打印排序后的数组（实际应用中，打印100万个数字可能不太现实，这里仅用于演示）。
_web前端开发设计_荆州百度推广_百度一下首页手机版)
