「排序算法」专题 7:快速排序(第 2 节)
参考资料:https://www.yuque.com/liweiwei1419/algo/lopi3w
Java 代码:
import java.util.Random;
public class Solution {
// 快速排序 2:双指针(指针对撞)快速排序
/**
* 列表大小等于或小于该大小,将优先于 quickSort 使用插入排序
*/
private static final int INSERTION_SORT_THRESHOLD = 7;
private static final Random RANDOM = new Random();
public int[] sortArray(int[] nums) {
int len = nums.length;
quickSort(nums, 0, len - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
// 小区间使用插入排序
if (right - left <= INSERTION_SORT_THRESHOLD) {
insertionSort(nums, left, right);
return;
}
int pIndex = partition(nums, left, right);
quickSort(nums, left, pIndex - 1);
quickSort(nums, pIndex + 1, right);
}
/**
* 对数组 nums 的子区间 [left, right] 使用插入排序
*
* @param nums 给定数组
* @param left 左边界,能取到
* @param right 右边界,能取到
*/
private void insertionSort(int[] nums, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = nums[i];
int j = i;
while (j > left && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
}
private int partition(int[] nums, int left, int right) {
int randomIndex = left + RANDOM.nextInt(right - left + 1);
swap(nums, randomIndex, left);
int pivot = nums[left];
int lt = left + 1;
int gt = right;
// 循环不变量:
// all in [left + 1, lt) <= pivot
// all in (gt, right] >= pivot
while (true) {
while (lt <= right && nums[lt] < pivot) {
lt++;
}
while (gt > left && nums[gt] > pivot) {
gt--;
}
if (lt > gt) {
break;
}
// 细节:相等的元素通过交换,等概率分到数组的两边
swap(nums, lt, gt);
lt++;
gt--;
}
swap(nums, left, gt);
return gt;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
Python 代码:
# 快速排序
# 在 partition 的过程中使用指针对撞的
# 特别注意,与标定点相等的元素的处理
# 双路快排:
# 随机将与标定点相等的元素分配到左边和右边
# 针对有许多重复键值的数组进行排序
class QuickSortTwoWays:
def __str__(self):
return "双路快排"
def __partition(self, arr, left, right):
p = arr[left]
le = left + 1
ge = right
while True:
# 针对索引进行判断的时候,要考虑是否越界
while le <= right and arr[le] < p:
le += 1
while ge >= left + 1 and arr[ge] > p:
ge -= 1
if le > ge:
break
arr[le], arr[ge] = arr[ge], arr[le]
le += 1
ge -= 1
# 注意:这里交换 left 与 ge 的位置
arr[left], arr[ge] = arr[ge], arr[left]
return ge
def __quick_sort(self, arr, left, right):
if left >= right:
return
p_index = self.__partition(arr, left, right)
self.__quick_sort(arr, left, p_index - 1)
self.__quick_sort(arr, p_index + 1, right)
def sort(self, arr):
size = len(arr)
self.__quick_sort(arr, 0, size - 1)
(本节完)