双路快速排序（Java 实例代码）

傷城~ 2023-10-14 14:58 21阅读 0赞

## 双路快速排序 ##

#### 一、概念及其介绍 ####

双路快速排序算法是随机化快速排序的改进版本，partition 过程使用两个索引值（i、j）用来遍历数组，将 **<v** 的元素放在索引i所指向位置的左边，而将 **>v** 的元素放在索引j所指向位置的右边，**v** 代表标定值。

#### 二、适用说明 ####

时间和空间复杂度同随机化快速排序。 对于有大量重复元素的数组，如果使用上一节随机化快速排序效率是非常低的，导致 partition 后大于基点或者小于基点数据的子数组长度会极度不平衡，甚至会退化成 O(n\*2) 时间复杂度的算法，对这种情况可以使用双路快速排序算法。

#### 三、过程图示 ####

使用两个索引值（i、j）用来遍历我们的序列，将 **<=v** 的元素放在索引 i 所指向位置的左边，而将 **>=v** 的元素放在索引 j 所指向位置的右边，平衡左右两边子数组。

![9f5681da44d3024603689d2f78f5ad9d.png][]

#### 四、Java 实例代码 ####

**源码包下载：**[Download![icon-default.png_t_N6B9][]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-QuickSort2Ways.zip][Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-QuickSort2Ways.zip]

### QuickSort2Ways.java 文件代码： ###

package runoob;  
  
/\*\*  
\* 双路快速排序  
\*/  
public class QuickSort2Ways \{  
  
//核心代码---开始  
private static int partition(Comparable\[\] arr, int l, int r)\{  
// 随机在arr\[l...r\]的范围中, 选择一个数值作为标定点pivot  
swap( arr, l , (int)(Math.random()\*(r-l+1))+l );  
Comparable v = arr\[l\];  
// arr\[l+1...i) <= v; arr(j...r\] >= v  
int i = l+1, j = r;  
while( true )\{  
while( i <= r && arr\[i\].compareTo(v) < 0 )  
i ++;  
while( j >= l+1 && arr\[j\].compareTo(v) > 0 )  
j --;  
if( i > j )  
break;  
swap( arr, i, j );  
i ++;  
j --;  
\}  
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;  
\}  
  
// 测试 QuickSort  
public static void main(String\[\] args) \{  
  
// 双路快速排序算法也是一个O(nlogn)复杂度的算法  
// 可以在1秒之内轻松处理100万数量级的数据  
  
// Quick Sort也是一个O(nlogn)复杂度的算法  
// 可以在1秒之内轻松处理100万数量级的数据  
int N = 1000000;  
Integer\[\] arr = SortTestHelper.generateRandomArray(N, 0, 100000);  
sort(arr);  
SortTestHelper.printArray(arr);  
  
\}  
\}

[9f5681da44d3024603689d2f78f5ad9d.png]: https://img-blog.csdnimg.cn/img_convert/9f5681da44d3024603689d2f78f5ad9d.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-QuickSort2Ways.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-QuickSort2Ways.zip