chapter_sorting/quick_sort/ #47
Replies: 56 comments 111 replies
-
js版本错的有点严重啊 |
Beta Was this translation helpful? Give feedback.
-
此部分的尾递归优化能否有图说明呢,看文字简短描述实在是想象不出来 |
Beta Was this translation helpful? Give feedback.
-
为什么里面的循环还需要i<j |
Beta Was this translation helpful? Give feedback.
-
图的文章啥时候出来~等了一个月啦 K神 |
Beta Was this translation helpful? Give feedback.
-
k佬,排序算法这块能不能加上链表的,犹记得第一次面试,被问道链表的逆序,之前从来没考虑过,懵掉了🤣🤣🤣🤣 |
Beta Was this translation helpful? Give feedback.
-
K神,插入排序定义了base基准数,快排里也使用了基准数,但是并没有用局部变量来保存基准数,而在是在哨兵划分中定义了i和j,下边儿这种写法会不会更容易让读者理解呢? int partition(int[] nums, int left, int right) {
// 以 nums[left] 作为基准数,并记录基准数索引
int base = nums[left];
int baseIndex = left;
while (left < right) {
while (left < right && nums[right] >= base)
right--; // 从右向左找首个小于基准数的元素
while (left < right && nums[left] <= base)
left++; // 从左向右找首个大于基准数的元素
swap(nums, left, right); // 交换这两个元素
}
swap(nums, baseIndex, left); // 将基准数交换到两子数组的分界线
return left; // 返回基准数索引
} |
Beta Was this translation helpful? Give feedback.
-
刚发现哨兵划分这里,先 从右往左 还是 从左往右 寻找,结果是不一样的。显然,先 从右往左 是正确的 |
Beta Was this translation helpful? Give feedback.
-
基准数优化,Java代码,' < '本身优先级高于' ^ ',可略去括号 if (nums[left] < nums[mid] ^ nums[left] < nums[right])
return left;
else if (nums[mid] < nums[left] ^ nums[mid] < nums[right])
return mid; |
Beta Was this translation helpful? Give feedback.
-
快排的C语言实现中swap函数是已经自己实现了吗?我并没有查到C语言有封装好的swap函数 |
Beta Was this translation helpful? Give feedback.
-
K神,关于尾递归优化,为什么选短的数组能保证递归深度不超过 |
Beta Was this translation helpful? Give feedback.
-
尾递归优化的那个 未排序的子数组再怎么去处理? |
Beta Was this translation helpful? Give feedback.
-
请问, 如果数据全是一样的, 是不是会退化到n^2, 这该咋办 |
Beta Was this translation helpful? Give feedback.
-
格式出现点问题,例如 (0),都多了“\”,我使用的是edge浏览器 |
Beta Was this translation helpful? Give feedback.
-
这尾递归也牛逼了吧,这是怎么想出来的,我拿着241035自个推了一遍,实在是妙不可言。while (left < right)这个循环太牛了。对内递归,对外跳出递归。 |
Beta Was this translation helpful? Give feedback.
-
为什么在查找元素的时候,需要先要找出比基准数大的值呢?如果先找比基准数小的值的话,排序的结果是不正确的(即交换j--和i++的执行顺序) |
Beta Was this translation helpful? Give feedback.
-
发现个问题,就是在partition方法中的while循环中,里面的while循环必须要是j--这个循环放在上面,而i++这个while要放在下面才可以,一旦交换位置,排序就不对,这是为什么?在逻辑上想不通这个道理。想着两个while子循环应该是彼此独立的,都是各干各的才对,为什么不能交换位置? |
Beta Was this translation helpful? Give feedback.
-
K神是怎么做到代码写的这么优美又这么易懂的?我曾经以为二者不可兼得,直到我看到了你的代码。 |
Beta Was this translation helpful? Give feedback.
-
K神,尾递归优化没看懂,能不能举个例子说明一下🙏 |
Beta Was this translation helpful? Give feedback.
-
非递归快速排序 def partition(arr, left, right):
i, j = left, right
while i < j:
while i < j and arr[j] >= arr[left]:
j -= 1
while i < j and arr[i] <= arr[left]:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i], arr[left] = arr[left], arr[i]
return i
def quick_sort(arr):
s = [(0, len(arr) - 1)]
while not len(s) == 0:
left, right = s.pop()
pivot = partition(arr, left, right)
if left < right:
s.append((left, pivot - 1))
if pivot + 1 < right:
s.append((pivot + 1, right))
if __name__ == '__main__':
nums = [5, 2, 8, 3, 9, 1, 7]
quick_sort(nums)
print(nums) |
Beta Was this translation helpful? Give feedback.
-
void QuickSorting(std::vector<int> &v,
std::vector<int>::size_type L,
std::vector<int>::size_type R)
{
if (L >= R)
return; // 左位置索引大于右位置索引,此数组已排完,函数退出
int benchmark = v[L ]; // 设左索引值为基准
auto i = L+1;
auto j = R;
/****************形成左子数组<=基准数<=右子数组****************/
while (i < j)
{
while (v[i] <= benchmark && i < j) // 找到左数组大于基准的索引
i++;
while (v[j] >= benchmark && i < j) // 找到右数组小于基准的索引
j--;
if (i < j) {
std::swap(v[i], v[j]);
}
}
std::swap(v[L],v[i]);//将基准值交换到分界线
/****************************************************************/
QuickSorting(v,L,i-1);//左子数组递归为左子数组<=基准数<=右子数组
QuickSorting(v,i+1,R);//右子数组递归为左子数组<=基准数<=右子数组
} |
Beta Was this translation helpful? Give feedback.
-
想请问一下,尾递归优化时,输入完全有序的数组的话,真的有优化吗,没有想明白 |
Beta Was this translation helpful? Give feedback.
-
int partition(int nums[], int left, int right){
int i = left, j = right;
while(i < j){
while(i < j && nums[i] <= nums[left]){
i++;
}
while(i < j && nums[j] >= nums[left]){
j--;
}
swap(nums, i, j);
}
swap(nums, i, left);
return i;
} 哪位大佬帮我看看哪里错了?找了好久找不到,谢谢 |
Beta Was this translation helpful? Give feedback.
-
while (i < j) {
while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
this.swap(nums, i, j); // 交换这两个元素
} 我将从右向左找首个小于基准数的元素,这个while循环放在下面,改成 while (i < j) {
while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
this.swap(nums, i, j); // 交换这两个元素
} 排序得到的结果,就不正确了,这是为什么,有同学知道吗 |
Beta Was this translation helpful? Give feedback.
-
关于尾递归 其实大家只要关注 left = pivot + 1 这一个条件就好了 在递归完短的左子数组的时候 你会想对应长的右子数组去哪了 其实就在这里被划分到 下一个while left<right 的整体数组里面去了 然后会生成新的pivot再重复这个过程 就像是在不断的削苹果到只剩苹果核的过程 每次都把削完的部分看做一个新的整体 再次进行短的削除 不知道说明白了没有 希望可以提供一点微小的帮助 |
Beta Was this translation helpful? Give feedback.
-
我不太理解尾递归优化这个名字,这个递归函数也是在函数体最后执行的递归啊,应该不是尾递归把 |
Beta Was this translation helpful? Give feedback.
-
感觉自适应并不一定就是好处,数据规律好自适应了可以提高效率,但也意味着需要忍受极端数据样例下的效率降低,归并的非自适应就可以总是nlogn,而快排自适应的nlogn在大部分情况适用 |
Beta Was this translation helpful? Give feedback.
-
为什么要交换到最左端,不能将后续left改成med吗 |
Beta Was this translation helpful? Give feedback.
-
def quick_sort(arr): print(quick_sort([3,6,8,10,1,2,1])) |
Beta Was this translation helpful? Give feedback.
-
第一次做贡献,写一个我认为更容易记忆的Python版本吧。 这个版本不需要单独定义partition函数,也不需要记忆复杂的指针移动规则,本质原理和官方版本是一样的,所以理论上时间复杂度应该是一样的,都是O(nlogn),但空间复杂度应该是O(n*n) = O(n^2),因为最多n层递归栈帧,每层需要额外保存left, mid, right三个数组,长度加起来是n。但考虑到面试的时候一般不要求空间复杂度,写出来最重要。。。 def quick_sort(nums: list[int]) -> list[int]:
n: int = len(nums)
# 如果传入的nums只剩下一个数字或者没有数字,则说明已经排序好了,直接返回即可
if n <= 1:
return nums
# 这个pivot的基本上是随机选的,不用这个中间的数也没关系
pivot: int = nums[n//2]
# 把传入的nums分成三组,左边的都小于刚刚选的pivot,右边的都大于pivot,中间的都等于pivot。
# mid也需要是list是因为:1. 需要保持形式的一致性,否则语法上后面return部分没办法拼起来。2. 因为等于pivot的元素可能不止有1个。
left, mid, right = [], [], []
for num in nums:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
mid.append(num)
# 现在已经做到,left里的数字 < mid里的数字 < right里的数字
# mid里的所有数字都是一个值,等于pivot,所以已经排序好,不需要再管了。
# left和right里的数字还没有排序,所以把它们各自再当作一个子问题,递归应用quick_sort排序,这样它们也可以排好了。
return quick_sort(left) + mid + quick_sort(right) |
Beta Was this translation helpful? Give feedback.
-
快速排序算法的递归和非递归C语言版本 // 快速排序
int mid3(float *x, int low, int high) { // 三数取中法,选取low, mid, high三个位置的元素,取其中值作为pivot
int mid = (low + high) / 2;
if (x[low] > x[mid]) swap(&x[low], &x[mid]); if (x[low] > x[high]) swap(&x[low], &x[high]); if (x[mid] > x[high]) swap(&x[mid], &x[high]);
return mid;
}
void partition(float *x, int size, int *pivot) { // 根据pivot将数组分为两部分,左边的元素小于等于pivot,右边的元素大于pivot
int low = 0, high = size - 1, i = low - 1, j = low, pivotIndex = mid3(x, low, high);
float pivotValue = x[pivotIndex]; swap(&x[pivotIndex], &x[high]);
for (j = low; j < high; j++) { if (x[j] <= pivotValue) { i++; swap(&x[i], &x[j]); } }
swap(&x[i + 1], &x[high]); *pivot = i + 1;
}
void q_sort_rec(float *x, int size) { if (size > 1) { int pivot; partition(x, size, &pivot); q_sort_rec(x, pivot); q_sort_rec(x + pivot + 1, size - pivot - 1); } }
void q_sort_nrec(float *x, int size) {
int *stack, top_idx = -1, left, right, pivot;
// 最坏情况通常发生在每次分区时,枢轴总是选择到最小或最大的元素,递归深度会达到最大,即等于数组的大小 n,每次处理一个子数组时,会向栈中压入左右边界,即栈空间的需求为两倍。
stack = (int *)malloc(2 * size * sizeof(int)); stack[++top_idx] = 0; stack[++top_idx] = size - 1;
while (top_idx >= 0){
right = stack[top_idx--]; left = stack[top_idx--]; partition(x + left, right - left + 1, &pivot); pivot += left;
if (pivot - 1 > left) {stack[++top_idx] = left; stack[++top_idx] = pivot - 1;} if (pivot + 1 < right) {stack[++top_idx] = pivot + 1; stack[++top_idx] = right;}
}
free(stack);
} |
Beta Was this translation helpful? Give feedback.
-
chapter_sorting/quick_sort/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_sorting/quick_sort/
Beta Was this translation helpful? Give feedback.
All reactions