首页 > 代码库 > 随机化快速排序(Java实现)

随机化快速排序(Java实现)

2024-10-23 16:37:02   208人阅读

Randomized quicksort(随机化快速排序)

  • running time is independent of input ordering.
  • no assumption about the input distribution.(无需对输入序列分布做任何假设)
  • no specific input elicit the worst-case behavior.(没有特定输入引起最差的运行效率)
  • worst-case determined only by a random -number generator.(最差的情况由随机数产生器决定)
  • pivot a random element.(随机选择一个主元)

根据《算法导论》中快速排序的随机化样本中的伪代码如下：

数组的划分：

1 RANDOMIZED-PARTITION(A, p, r)2 i = RANDOM(p, r)3 exchange A[r] with A[i]4 return PARTITION(A, p ,r)

其中PARTITION(A, p, r)参考快速排序（Java实现）

1 RANDOMIZED-QUICKSORT(A, p, r)2     if p < r3         q = RANDOMIZED-PARTITION(A, p, r)4         RANDOMIZED-QUICKSORT(A, p, q-1)5         RANDOMIZED-QUICKSORT(A, q+1, r)

随机快速排序，随机选择一个主元和数组划分：RandomQuickSort.java

 1 package quicksort; 2  3 import java.util.Random; 4  5 public class RandomQuickSort { 6  7     public void Sort(int[] a, int p, int r) { 8         if (p < r) { 9             int q = Partition(a, p, r);10             Sort(a, p, q-1);11             Sort(a,q+1, r);            12         }13     }14     15     private int Partition(int[] A, int p, int r) {16         /*随机选取主元元素*/17         Random random = new Random();18         int random_index = random.nextInt(r-p+1)+p;19         System.out.println("random_index="+random_index);20         int temp = A[random_index];21         A[random_index] = A[r];22         A[r] = temp;23         24         int x = A[r];  //pivot = A[p]25         int i = p-1;26         for (int j = p; j < r; j++) {27             if (A[j] <= x) {  //与pivot作比较28                 i++;29                 int tmp = A[j];30                 A[j] = A[i];31                 A[i] = tmp;32             }33         }34         35         int tmp = A[r];36         A[r] = A[i+1];37         A[i+1] = tmp;38         39         return i+1;40         41     }42     43 }

 测试随机化快速排序：RandomQuickSortTest.java

 1 package quicksort; 2  3 public class RandomQuickSortTest { 4  5 //    static int[] a ={2, 8, 7, 1, 3, 5, 6, 4}; 6     static int[] a ={13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11}; 7     public static void main(String[] args) { 8         RandomQuickSort randomQuickSort = new RandomQuickSort(); 9         randomQuickSort.Sort(a, 0, a.length-1);10         11         for (int i = 0; i < a.length; i++) {12             System.out.print(a[i]+" ");13         }14     }15 }

 测试结果： 

random_index=2random_index=2random_index=0random_index=0random_index=8random_index=10random_index=7random_index=72 4 5 6 7 8 9 11 12 13 19 21

 

随机化快速排序(Java实现)


联系
我们