关于数据结构与算法:数据结构与算法腾讯面试官让我模拟快排的执行过程背好的代码竟无用武之地

36次阅读

共计 1810 个字符，预计需要花费 5 分钟才能阅读完成。

我是少侠露飞。学习塑造人生，技术扭转世界。

疾速排序号称最优雅的算法之一，在开发中可能用得不算多，然而在一些场景下还是很杰出的。最要害的是，各大厂面试官都爱问啊，你说要不要好好把握吧。
而后就是网上很多快排的代码和解说，少侠发现很多人本人压根都没搞清楚，代码的边界不清，扔进去一执行就报数组越界异样；要么就是一些人模仿的快排过程都是错的，这让真心想学习的人不免心累。所以少侠决定写一篇记录之，解说未必是最好的，但代码肯定是正确的。

合成：快排的外围就是首先选定一个 主元 pivot，而后将原数组分解成两个子数组 A 和 B，保障 A 中的后果小于等于 pivot，B 中的后果都大于等于 pivot。
解决：而后针对两个子数组 A 和 B 再递归的调用，依照上步合成的逻辑进行。
合并：咱们晓得，归并排序最初是须要合并子数组的。但在这里，好消息是快排是旧址排序，不须要合并。

原理不难理解，然而初学者对这个过程可能还是比拟含糊。这里少侠就抉择一个数组，依照快排的过程一步一步展现给大家。
这里咱们抉择初始化数组 [6,2,3,9,5,8]。
首先抉择主元，怎么选呢，能够抉择某一索引地位的值，也能够抉择多个索引，而后取中位数的值作为主元。这里咱们固定抉择第一个元素为主元。

第一次合成的时候 pivot=6，合成的 指标就是把所有大于等于 6 的元素挪动左边，小于等于 6 的元素移到右边 。而后左指针 i 从起始地位开始，右指针 j 从结尾开始， 循环的边界就是 i <j。初始地位如下图：

每次从左边的指针断定。当右指针的值大于 pivot 时，右指针左移一位，直到遇到小于等于 pivot 的值。如下图：

当右指针的值小于 pivot 时，将以后值赋值给指针 i 对应的地位，同时 i 向右挪动一位，如下图：

当产生上步的状况（即右指针因小于 pivot 而产生值的笼罩时候），须要进入该逻辑：就是开始判断左指针的元素值，如果小于 pivot，就向右挪动一位，直到遇到大于等于 pivot 的元素。

此时 i 挪动到元素值为 9 的地位，也就是大于 pivot，此时须要将此地位的值赋值给 j 地位并使得指针 j 左移一位，即：

留神看，此时 i =j，左右指针重合，曾经不满足循环边界条件 (i<j) 了，退出循环。然而此时 i 地位的值才是 pivot 应该在的地位，所以执行赋值操作将 pivot 赋值给 nums[i]=pivot; 失去本次合成的最终后果：

最初再对主元 pivot 两侧的数组 {5,2,3} 和{9,8}递归的调用上述过程，失去最终排序后果。

    public void quickSort(int[] nums) {if (nums == null || nums.length <= 1) {return;}
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int left, int right) {
        // 左右指针没有相遇前比拟各数据与基元的大小
        if (left < right) {
            // 抉择主元值
            int pivot = nums[left];
            // 标记左右指针
            int i = left, j = right;
            // 一趟排序，找到比主元大的数据放在基元右侧，比主元小的值放在基元左侧
            while (i < j) {
                // 从右往左扫描，以后值大于主元时跳过，右指针左移一位
                while (i < j && nums[j] > pivot) {j--;}
                // 当走到这里时，意味着以后值左指针和右指针相遇，阐明本趟排序完结
                // 也可能是以后数据小于等于主元，此时须要将以后数据赋值给左指针对应的值，并将左指针右移一位
                if (i < j) {nums[i++] = nums[j];
                }
                // 从左往右扫描，以后值小于主元时跳过，左指针右移一位
                while (i < j && nums[i] < pivot) {i++;}
                // 当走到这里时，意味着以后值左指针和右指针相遇，阐明本趟排序完结
                // 也可能是以后数据大于等于主元，此时须要将以后数据赋值给右指针对应的值，并将右指针左移一位
                if (i < j) {nums[j--] = nums[i];
                }
            }
            // 此时索引 i 的地位应该就是主元值
            nums[i] = pivot;
            // 左侧依照雷同思路递归
            quickSort(nums, left, i - 1);
            // 右侧依照雷同思路递归
            quickSort(nums, i + 1, right);
        }
    }

本篇参考书籍《算法导论》。下期还会写篇对于 堆排序 的博客，敬请期待，也欢送点赞、关注。咱们下期再见。

正文完