排序算法五：随机化快速排序(Randomized quicksort)
上一篇提到，快速排序的平均时间复杂度是O(nlgn)，比其他相同时间复杂度的堆排序、归并排序都要快，但这是有前提的，就是假定要排序的序列是随机分布的，而不是有序的。实际上，对于已经排好的序列，如果用快速排序时间复杂度是O(n2)。为应对这样的有序序列，于是出现了本篇要讲的随机化快速排序(Randomized quicksort)。
快速排序在选主元（pivot）时，总是选择第一个；随机化快速排序的思想是，随机从序列中选择一个作为主元。
（一）算法实现
protected void quicksort(int[] array, int first, int last) {
int randomIndex = CommonUtils.getRandomInt(first, last);
CommonUtils.swap(array, first, randomIndex);
int pivot = array[first];
int i = first;
int j = last - 1;
boolean serachBig = true;
while (i < j) {
if (serachBig) {
if (array[j] < pivot) {
array[i] = array[j];
i++;
serachBig = false;
} else {
j--;
}
} else {
if (array[i] > pivot) {
array[j] = array[i];
j--;
serachBig = true;
} else {
i++;
}
}
}
array[i] = pivot;
if (i - first > 1) {
quicksort(array, first, i);
}
if (last - i > 2) {
quicksort(array, i + 1, last);
}
}
Randomized quicksort
1）对于任何输入序列，随机化快速排序的时间复杂度是O(nlgn)
2）考虑递归，随机化快速排序空间复杂度是O(logn)，不是原地排序
3）随机化快速排序属于比较排序
4）随机化快速排序不是稳定排序算法
（二）仿真结果
下面比较快速排序和随机化快速排序，分别对随机序列和有序序列排序。
**************************************************
Number to Sort is:2500
Randomized sequence to sort is:{741988,773994,855169,757518,82329,596105,876316,561224,928992,721115...}
Cost time of 【QuickSort】 is(milliseconds):0
Sort result of 【QuickSort】:{250,786,1209,1434,2306,3074,3715,3800,4669,5510...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):1
Sort result of 【RandomizedQuickSort】:{250,786,1209,1434,2306,3074,3715,3800,4669,5510...}
Ordered sequence to sort is:{250,786,1209,1434,2306,3074,3715,3800,4669,5510...}
Cost time of 【QuickSort】 is(milliseconds):6
Sort result of 【QuickSort】:{250,786,1209,1434,2306,3074,3715,3800,4669,5510...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):0
Sort result of 【RandomizedQuickSort】:{250,786,1209,1434,2306,3074,3715,3800,4669,5510...}
**************************************************
Number to Sort is:25000
Randomized sequence to sort is:{791264,308128,451250,42835,620880,820510,650527,51751,716592,292370...}
Cost time of 【QuickSort】 is(milliseconds):2
Sort result of 【QuickSort】:{52,82,148,166,180,182,232,354,382,394...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):3
Sort result of 【RandomizedQuickSort】:{52,82,148,166,180,182,232,354,382,394...}
Ordered sequence to sort is:{52,82,148,166,180,182,232,354,382,394...}
Cost time of 【QuickSort】 is(milliseconds):650
Sort result of 【QuickSort】:{52,82,148,166,180,182,232,354,382,394...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):2
Sort result of 【RandomizedQuickSort】:{52,82,148,166,180,182,232,354,382,394...}
**************************************************
Number to Sort is:250000
Randomized sequence to sort is:{595090,163678,171858,249808,15138,951048,53215,611066,766255,454662...}
Cost time of 【QuickSort】 is(milliseconds):30
Sort result of 【QuickSort】:{1,1,8,8,10,11,11,17,31,32...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):55
Sort result of 【RandomizedQuickSort】:{1,1,8,8,10,11,11,17,31,32...}
Ordered sequence to sort is:{1,1,8,8,10,11,11,17,31,32...}
Cost time of 【QuickSort】 is(milliseconds):54,886
Sort result of 【QuickSort】:{1,1,8,8,10,11,11,17,31,32...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):19
Sort result of 【RandomizedQuickSort】:{1,1,8,8,10,11,11,17,31,32...}
相关代码：
package com.cnblogs.riyueshiwang.sort;
import java.util.Arrays;
public class RandomizedQuickSort extends abstractSort {
@Override
protected void sort(int[] toSort) {
quicksort(toSort, 0, toSort.length);
}
protected void quicksort(int[] array, int first, int last) {
int randomIndex = CommonUtils.getRandomInt(first, last);
CommonUtils.swap(array, first, randomIndex);
int pivot = array[first];
int i = first;
int j = last - 1;
boolean serachBig = true;
while (i < j) {
if (serachBig) {
if (array[j] < pivot) {
array[i] = array[j];
i++;
serachBig = false;
} else {
j--;
}
} else {
if (array[i] > pivot) {
array[j] = array[i];
j--;
serachBig = true;
} else {
i++;
}
}
}
array[i] = pivot;
if (i - first > 1) {
quicksort(array, first, i);
}
if (last - i > 2) {
quicksort(array, i + 1, last);
}
}
public static void main(String[] args) {
for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {
System.out
.println("**************************************************");
System.out.println("Number to Sort is:" + n);
int[] array = CommonUtils.getRandomIntArray(n, 1000000);
System.out.print("Randomized sequence to sort is:");
CommonUtils.printIntArray(array);
int[] array1 = Arrays.copyOf(array, n);
new QuickSort().sortAndprint(array1);
int[] array2 = Arrays.copyOf(array, n);
new RandomizedQuickSort().sortAndprint(array2);
System.out.print("Ordered sequence to sort is:");
CommonUtils.printIntArray(array1);
new QuickSort().sortAndprint(array1);
new RandomizedQuickSort().sortAndprint(array1);
}
}
}
RandomizedQuickSort.java
package com.cnblogs.riyueshiwang.sort;
import java.util.Random;
public class CommonUtils {
private static Random random = new Random();
public static void printIntArray(int[] array) {
System.out.print('{');
int length = Math.min(array.length, 10);
for (int i = 0; i < length; i++) {
System.out.print(array[i]);
if (i != length - 1) {
System.out.print(',');
} else {
if (array.length > 10) {
System.out.print("...");
}
System.out.println('}');
}
}
}
public static int[] getRandomIntArray(int size, int maxValue) {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(maxValue);
}
return array;
}
public static void swap(int[] toSort, int i, int j) {
int temp = toSort[i];
toSort[i] = toSort[j];
toSort[j] = temp;
}
/**
*
* @param first
* begin value
* @param last
* end value
* @return a pseudo random, uniformly distributed int value between first
* (inclusive) and last (exclusive)
*
*/
public static int getRandomInt(int first, int last) {
return random.nextInt(last - first) + first;
}
}
CommonUtils.java
最新文章
- Docket学习--Docker入门
- 修改shell提示符的显示格式
- MVC 3 IIS7.5 网站发布及IIS配置文件问题处理
- Caffe学习系列(13):对训练好的模型进行fine-tune
- Redis学习笔记(2) Redis基础类型及命令之一
- Centos 关闭后台进程 .sh 等
- python any()和all()用法
- Linux资源监控命令/工具（网络）
- Java二维码登录流程实现(包含短地址生成，含部分代码)
- ios开发----视图的生命周期
- STUCTS LABLE ‘S BENEFIT
- 负载均衡之DNS轮询
- SDN学习之实现环路通信
- CPP 栈 示例
- Metrics.NET step by step
- noj算法 素数环 回溯法
- Java中的transient关键字
- python-模块入门二(模块循环导入,区分python文件的两种用途,模块搜索路径,软件开发的目录规范)
- linux 分区、目录及用途
- urllib模块通过post请求获取数据