6、快速排序 O(nlogn)
public static void sort(Comparable[] arr) {
quickSort(arr, 0, arr.length - 1);
}
//递归使用快速排序，对arr[left...right]的范围进行排序
private static void quickSort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
// 对arr[left...right]部分进行partition操作
//返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex]; arr[partion+1...r]>arr[partitionIndex]
private static int partition(Comparable[] arr, int left, int right) {
Comparable v = arr[left];
int partitionIndex = left;
for (int i = left + 1; i <= right; i++) {
if (arr[i].compareTo(v) < 0) {
SortTestHelper.swap(arr, partitionIndex, i);
partitionIndex++;
}
}
arr[partitionIndex] = v;
return partitionIndex;
}
递归使用快速排序，对arr[left...right]的范围进行排序
对arr[left...right]部分进行partition操作
返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex]; arr[partion+1...r]>arr[partitionIndex]
快速排序也可以进行优化，当元素个数小于15的时候，比较接近有序状态，可以用针对有序队列排序效率高的插入排序进行优化,代码如下：
//递归使用快速排序，对arr[left...right]的范围进行排序
private static void quickSort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
if(right-left<=15){
insertSort(arr,left,right);
}
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
//插入排序
public static void insertSort(Comparable[] arr,int left,int right) {
for (int i = left; i <=right; i++) {
for (int j = i; j > left; j--) {
if (arr[j].compareTo(arr[j - 1]) > 0) {
break;
}
SortTestHelper.swap(arr, j, j - 1);
}
}
}
快速排序性能会比归并排序效率要高，但是有人对于接近有序队列，快速排序要比归并排序性能要差很多，归并排序每次平分的平衡性要比快速排序的要好，归并排序拆分的高度能保证是logn的，而快速排序并不能保证高度为logn，所以快速排序最坏的情况是退化为O(n^2)的。
快速排序不需要额外的空间。如果数据量大而且数据全部存放在内存中，那么
快速排序是首选的排序方法。具体的排序过程是先将元素分成两个区，所有小于某个元素的值在第一个区，其他元素在第二区。然后分别对这两个区进行快速排序，直到所分的区只剩下一个元素为止。
为了解决快速排序分割数组时，分布不均的问题，每次选择partitionIndex的时候，采用随机生成的方式 ,详见下面代码的：
SortTestHelper.swap(arr, left, (int) (Math.random() * (right - left + 1)) + left);
或者
Integer randomIndex = left+random.nextInt(right - left + 1);
SortTestHelper.swap(arr, left, randomIndex);
// 对arr[left...right]部分进行partition操作
//返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex]; arr[partion+1...r]>arr[partitionIndex]
private static int partition(Comparable[] arr, int left, int right) {
//Comparable v = arr[left];
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
SortTestHelper.swap(arr, left, (int) (Math.random() * (right - left + 1)) + left);
Comparable v = arr[left];
int partitionIndex = 0;
for (int i = left + 1; i <= right; i++) {
if (arr[i].compareTo(v) < 0) {
SortTestHelper.swap(arr, partitionIndex, i);
partitionIndex++;
}
}
arr[partitionIndex] = v;
return partitionIndex;
}
当需要排序的数据含有大量的重复元素的时候，快速排序的子序列的划分会极其不平衡，二分递归会退化为线性递归，递归深度接近于O(n)。为了解决这个问题，可以采用双排或者三排
快速排序 双排
private static int partition(Comparable[] arr, int left, int right) {
//随机选一个 povit
int swapLeft = (int) (Math.random() * (right - left + 1) + left);
SortTestHelper.swap(arr, left, swapLeft);
Comparable v = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= right && arr[i].compareTo(v) < 0) {
i++;
}
while (j >= left+1 && arr[j].compareTo(v) > 0) {
j--;
}
if (i >j) {
break;
}
SortTestHelper.swap(arr, i, j);
i++;
j--;
}
SortTestHelper.swap(arr, left, j);
return j;
}
快速排序 三路快排思想
// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void quickSortThreeWays(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
// 对于小规模数组, 使用插入排序
if (right - left <= 15) {
//优化代码
}
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
int swapLeft = (int) (Math.random() * (right - left + 1) + left);
SortTestHelper.swap(arr, left, swapLeft);
Comparable v = arr[left];
int lt = left; // arr[l+1...lt] < v
int gt = right + 1; // arr[gt...r] > v
int et = left + 1;// arr[lt+1...i) == v
while (et < gt) {
if (arr[et].compareTo(v) < 0) {
if (et != lt + 1) {
SortTestHelper.swap(arr, et, lt + 1);
}
et++;
lt++;
continue;
}
if (arr[et].compareTo(v) > 0) {
SortTestHelper.swap(arr, et, gt - 1);
gt--;
continue;
}
//arr[et].compareTo(v) == 0
et++;
}
SortTestHelper.swap(arr, left, lt);
//et 的 不变
quickSortThreeWays(arr, left, lt - 1);
quickSortThreeWays(arr, gt, right);
}
网友评论