佛山专业网站设计公司,wordpress做简单的商城,网站底部美化代码,北极鱼wordpress随机化快速排序
一、概念及其介绍
快速排序由 C. A. R. Hoare 在 1960 年提出。
随机化快速排序基本思想#xff1a;通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小#xff0c;然后再按此方法对这两部分数…随机化快速排序
一、概念及其介绍
快速排序由 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-l1))l );
四、Java 实例代码
源码包下载Downloadhttps://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-random-quick-sort.zip
QuickSort.java 文件代码
package runoob; /** * 随机化快速排序 */ public class QuickSort { // 对arr[l...r]部分进行partition操作 // 返回p, 使得arr[l...p-1] arr[p] ; arr[p1...r] arr[p] private static int partition(Comparable[] arr, int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr, l , (int)(Math.random()*(r-l1))l ); Comparable v arr[l]; // arr[l1...j] v ; arr[j1...i) v 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; } // 递归使用快速排序,对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, p1, 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; } // 测试 QuickSort public 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); } }
