fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
快速排序详解及应用 :: labuladong的算法小抄
while (i < hi && nums[i] <= pivot) {
i++;
// 此 while 结束时恰好 nums[i] > pivot
}
不知道我的理解是否正确
对于数组 [5,1,2,3,4] 排序时，经过这个循环，i 指向 4 ，并不满足 nums[i] > pivot，但是会由 if (i >= j) break; 终止 swap，结果是一样的
对于数组 [5,1,2,3,4,8] 排序时，就没问题了
试了一下，这里使用 i <= hi 也能AC，感觉这里之所以用 i < hi 是因为能够减少一次循环，因为hi元素的大小会在下面的j循环得到对比
对于数组 [5,1,2,3,4] 排序时，使用 i <= hi ，经过上面的循环i会指向4后面，但是依然会由 if (i >= j) break; 终止 swap，结果是一样的
而 j > lo 是因为 lo 元素就是 pivot，无须比较
@wy-luke 给你的思考点赞！关于你说的 使用 i <= hi 也能AC，确实是这样的，我简单说下我的分析：
这里的关键是控制 j 指针的位置，因为外层 while 结束之后需要把 pivot 换到 nums[j] 的位置上去。你对 i 的边界情况有微调，只要不影响 j 的位置，同时能够保证触发 if (i >= j) break; 的终止条件，则最终的结果都是正确的。
- 排序数组 javascript version
var sortArray = function(nums) {
// 为了避免出现耗时的极端情况 先随机打乱数组
randomShuffle(nums);
// 排序整个数组（原地修改）
sort(nums, 0, nums.length - 1);
return nums;
// 排序数组nums
function sort(nums, lo, hi) {
if (lo >= hi) {
return;
}
/****** 前序位置 ******/
// 对nums[lo...hi]进行切分
// 使得nums[lo...p-1] <= nums[p] < nums[p+1..hi]
let p = partition(nums, lo, hi);
/*********************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
// 对nums[lo...hi]进行切分
function partition(nums, lo, hi) {
// 取第一个位置的元素作为基准元素
let pivot = nums[lo];
// 这里把left, right定义为开区间
// 同时定义 [lo, left) <= pivot; (right, hi] > pivot
// 之后都要正确维护这个边界区间的定义
let left = lo + 1;
let right = hi;
// 当left > right时结束循环 以保证区间[lo, hi]都被覆盖
while(left <= right) {
while(left < hi && nums[left] <= pivot) {
left++;
// 此while循环结束时 恰好 nums[left] > pivot
}
while(right > lo && nums[right] > pivot) {
right--;
// 此while循环结束时 恰好 nums[right] <= pivot
}
// 此时[lo, left) <= pivot && (right, hi] > pivot
if (left >= right) {
break;
}
swap(nums, left, right)
}
// 将pivot放到合适的位置 即pivot左边元素较小 右边元素较大
swap(nums, lo, right);
return right;
}
// 随机打乱数组
function randomShuffle(nums) {
let len = nums.length;
for (let i; i < len; i++) {
// 随机生成[i, n - i]的随机数
let index = i + Math.floor(Math.random * (len - i));
swap(nums, i, index);
}
}
// 原地交换数组中的两个元素
function swap(nums, i, j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
- 数组中的第K个最大元素 javascript version
var findKthLargest = function(nums, k) {
// 转化成升序排名第targetIndex的元素
let targetIndex = nums.length - k;
let start = 0;
let end = nums.length - 1;
/** 在nums[start, end]中选择一个分界点 */
let index = partition(nums, start, end);
while (index != targetIndex) {
if (index > targetIndex) {
// 第k大的元素在nums[start, index - 1]中
end = index - 1;
} else {
// 第k大的元素在nums[index + 1, end]中
start = index + 1;
}
// 在nums[start, end]中选一个分界点
index = partition(nums, start, end);
}
// 找到第k大的元素
return nums[index];
}
/****** 对nums[start, end]进行切分 ******/
function partition(arr, startIndex, endIndex) {
// 取第一个位置的元素作为基准元素
let pivot = arr[startIndex];
// 设置一个mark指针指向数组的起始位置 最终mark指针代表小于基准元素的区域边界
let mark = startIndex;
for (let i = startIndex+1; i <= endIndex; i++) {
if (arr[i] < pivot) {
mark++;
// 交换两个元素
[arr[mark], arr[i]] = [arr[i], arr[mark]];
}
}
// 更新分界点的值
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
这个分区容易理解点，有点双指针技巧含义，选最后一个元素作为分区点，指针 i 表示比分区值小的元素应该放的位置，指针 j 只用来遍历。当 j 遍历到比分区值小的元素时，放到指针 i 的位置（通过交换实现）。当 j 遍历完时，[lo, i - 1] 都是比分区值小的元素，[i, hi - 1] 都是比分区值大的元素，最后交换一下分区值和 i 所指向的元素便实现了 pivot 左边都是比它小的元素，右边都是比它大的元素。
private static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int i = lo, j = lo;
while (j < hi) {
if (arr[j] < pivot) {
swap(arr, i, j);
i++;
}
j++;
}
swap(arr, i, hi);
return i;
}
笔记：
partition 里面有while(i <= j) {，等号的目的是解决array的长度只有2的edge case，其中一个被抓去做了pivot，另一个必须得验证一下是不是比pivot大，不是的话还是要swap一下。
如果长度只有1，那么进不了这个while循环
quick select里面还有一个while(i <= j) {， 等号的目的是解决array长度只有1的edge case。理论上应该返回0，如果不加等号会返回-1。
