随机快排算法

 1 package Sort;
 2
 3 import org.junit.Test;
 4
 5 // 随机快排算法
 6 public class RandQuickSort {
 7
 8     // 交换数组中的两个元素
 9     public void exchange(int[] array, int index1, int index2) {
10         int tmp = array[index1];
11         array[index1] = array[index2];
12         array[index2] = tmp;
13     }
14
15     // 分区函数,返回分区的元素下标
16     public int partition(int[] array, int start, int end) {
17         if (start >= end)
18             return -1;
19         int length = end - start + 1;
20         // 产生一个[start.. end]范围内的伪随机下标
21         int pivotIndex = start + (int) Math.floor(Math.random() * length);
22         System.out.println("选取的主元下标为: " + pivotIndex);
23         // 选取array[pivotIndex]作为主元
24         exchange(array, pivotIndex, end);
25         int i = start;
26         int j = end - 1;
27         while (i < j) {
28             // 从数组头部开始,依次找到数组中大于主元的元素
29             while (i <= end && array[i] < array[end])
30                 ++i;
31             // 从数组尾部开始,依次找到数组中小于主元的元素
32             while (j >= start && array[j] >= array[end])
33                 --j;
34             if (i < j) {
35                 exchange(array, i, j);
36                 ++i;
37                 --j;
38             }
39         }
40
41         if (i > j) {
42             exchange(array, i, end);
43             return i;
44         }
45         // i == j的两种情况
46         else if (array[i] > array[end]) {
47             exchange(array, i, end);
48             return i;
49         } else {
50             exchange(array, i + 1, end);
51             return i + 1;
52         }
53     }
54
55     // 真正的随机快速排序算法要开始了
56     public void quickSort(int[] array, int start, int end) {
57         if (start < end) {
58             int middle = partition(array, start, end);
59             quickSort(array, start, middle - 1);
60             quickSort(array, middle + 1, end);
61         }
62     }
63
64     @Test
65     public void test() {
66         int[] array = { 8, 2, -1, 4, 9, -5, 3, 6, 25, 5, 10, -3, 30, 21, 13 };
67         quickSort(array, 0, array.length - 1);
68         Array.print(array);
69     }
70 }
时间: 09-13

随机快排算法的相关文章

快排,随机快排,双路快排,三路快排的理解

再讲快排之前,首先对于任何一个数组,无论之前是多么杂乱,排完之后是不是一定存在一个数作为分界点(也就是所谓的支点),在支点左边全是小于等于这个支点的,然后在这个支点右边的全是大于等于这个支点的,快排过程就是寻找这个支点过程 先看普通的快排(普通单路快排) 代码如下 let findIndex = (arr, l, len) => { let par = arr[l], j = l for (let i = l + 1; i <= len; i++) { if (arr[i] < par)

随机快排

#include<stdio.h> int PARTITION(int*A,int p,int r)//分治 { int x=A[r-1]; int i=p-1; int j=p; int temp; while(j<=r-1) { if(A[j-1]<=x) { i++; temp=A[i-1]; A[i-1]=A[j-1]; A[j-1]=temp; } j++; } temp=A[i]; A[i]=A[r-1]; A[r-1]=temp; return i+1; } int

关于快排算法的学习

写在前面: 算法设计与分析,这门课其实在大学都学习过,也受到了很多启发,只是隔了很久,大多已经忘记了,想趁这个机会重新学习一下. 因为刚开始学习,可能初期的博客内容大多是跟着前辈们学习的,后面可能会尝试总结一些笔记和心得,看看能不能启发一些其他的方面. 下面是找的关于快排的一些资料,这篇觉得确实不错,原地址:https://blog.csdn.net/yzllz001/article/details/50982841 高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是"快速排序

快速排序(经典快排以及随机快排)

快速排序(Quicksort)是对冒泡排序的一种改进. 快速排序由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 首先来了解一下经典快排: 其中就小于等于的区域可以优化一下,小于的放小于区域,等于的放等于区域,大于的放大于区域.可以利用荷兰国旗问题 荷兰国旗问题: 给定一个数组arr

快排算法实现

public class QuickSort { public static void sort(int arr[],int low,int high){ int l=low; int h=high; int temp=arr[low]; while(l<h) { while(l<h&&arr[h]>=temp) h--; arr[l]=arr[h]; while(l<h&&arr[l]<=temp) l++; arr[h]=arr[l]; }

python快排算法

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 1 def kp(arr,i,j): 2 if i < j: 3 base = kpgc(arr,i,j) 4 kp(arr,i,base) 5 kp(arr,base+1,j) 6 def kpgc(arr,i,j): 7 base = arr[i] 8 while i < j: 9 whil

快排算法的简单实现

java实现: 细节和注解都在注释在代码中了. 1 private static int position(int[] ary,int low,int high){ 2 int i = low,j = high+1; 3 int pivot = ary[low];//选定中轴元素 4 while(true){ 5 while(ary[++i] < pivot) {//遇到大于等于pivot时停下 6 if (i == high) {break;}//此处有必要检查,当pivot刚好为当前序列的最

快排算法的深入理解

简述 给每组数分成小.中.大 三种,利用递归思想进行排序.时间复杂度是n*log2n  (log2n代表2的多少次方等于n),其中log2n代表组数.n*log2n代表所有数的对换次数所用的时间. 实例说明 代码: def kuaiPai(num): da,zhong,xiao=[],[],[] if len(num)<=1: return num pivo=num[0] for i in range(len(num)): if i>num[0]: da.append(i) elif i<

算法导论学习之快排+各种排序算法时间复杂度总结

快排是一种最常用的排序算法,因为其平均的时间复杂度是nlgn,并且其中的常数因子比较小. 一.快速排序 快排和合并排序一样都是基于分治的排序算法;快排的分治如下: 分解:对区间A[p,r]进行分解,返回q,使得A[p–q-1]都不大于A[q] A[q+1,r]都大于A[q]; 求解:对上面得到的区间继续递归进行快排 合并:因为快排是原地排序,所以不需要特别的合并 从上可以看出最重要的就是分解函数,其按关键值将数组划分成3部分,其具体实现的过程见代码注释. 我们一般取数组的最后一个元素作为划分比较