世界杯竞猜网站开发,图片外链生成器,seo百度站长工具查询,wordpress分类信息 模板“快速排序就是个二叉树的前序遍历” ——————labuladong 快速排序的逻辑
快速排序是先将一个元素排好序#xff0c;然后再将剩下的元素排好序。
若要对 nums[lo..hi] 进行排序#xff0c;我们先找一个分界点 p#xff0c;通过交换元素使得 nums[lo..p-1] 都小于等于 … “快速排序就是个二叉树的前序遍历” ——————labuladong 快速排序的逻辑
快速排序是先将一个元素排好序然后再将剩下的元素排好序。
若要对 nums[lo..hi] 进行排序我们先找一个分界点 p通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]且 nums[p1..hi] 都大于 nums[p]然后递归地去 nums[lo..p-1] 和 nums[p1..hi] 中寻找新的分界点最后整个数组就被排序了。
从二叉树的视角我们可以把子数组 nums[lo..hi] 理解成二叉树节点上的值srot 函数理解成二叉树的遍历函数。
partition 函数每次都将数组切分成左小右大两部分最后形成的这棵二叉树是一棵二叉搜索树
但谈到二叉搜索树的构造那就不得不说二叉搜索树不平衡的极端情况极端情况下二叉搜索树会退化成一个链表导致操作效率大幅降低。所以我们要对初始数组进行随机性处理
快速排序的代码框架
void sort(int[] nums, int lo, int hi) {/****** 前序遍历位置 ******/// 通过交换元素构建分界点 pint p partition(nums, lo, hi);/************************/sort(nums, lo, p - 1);sort(nums, p 1, hi);
}
我们与二叉树的前序遍历代码框架进行对比
/* 二叉树遍历框架 */
void traverse(TreeNode root) {if (root null) {return;}/****** 前序位置 ******/print(root.val);/*********************/traverse(root.left);traverse(root.right);
}
快速排序的代码实现
class Quick {public static void sort(int[] nums) {// 为了避免出现耗时的极端情况先随机打乱数组元素顺序shuffle(nums);// 排序整个数组原地修改sort(nums, 0, nums.length - 1);}// 私有的递归排序函数使用快速排序算法对数组进行排序 private static void sort(int[] nums, int lo, int hi) {if (lo hi) {return; // 递归结束条件当 lo 大于等于 hi 时子数组已经有序}// 对 nums[lo..hi] 进行切分// 使得 nums[lo..p-1] nums[p] nums[p1..hi]int p partition(nums, lo, hi); // 获取切分点 p// 对切分点左右两边的子数组分别进行递归排序sort(nums, lo, p - 1);sort(nums, p 1, hi);}// 切分函数用于确定切分点并重新排列数组元素private static int partition(int[] nums, int lo, int hi) {int pivot nums[lo]; // 选择第一个元素作为切分元素int i lo 1, j hi; // 定义两个指针 i 和 j// 使用双指针将数组划分为两部分一部分小于等于pivot一部分大于pivotwhile (i j) {while (i hi nums[i] pivot) {i; // 移动左指针直到找到一个大于pivot的元素}while (j lo nums[j] pivot) {j--; // 移动右指针直到找到一个小于等于pivot的元素}// 交换左右指针所指向的元素保证左边小于等于pivot右边大于pivotif (i j) {break; // 当左右指针相遇时退出循环}swap(nums, i, j); // 交换 nums[i] 和 nums[j]}// 将pivot放到合适的位置即使得左边元素小于等于pivot右边元素大于pivotswap(nums, lo, j); // 将切分元素放到最终位置return j; // 返回切分元素的下标}// 洗牌算法将输入的数组随机打乱private static void shuffle(int[] nums) {Random rand new Random(); // 创建随机数生成器int n nums.length;for (int i 0 ; i n; i) {// 生成 [i, n - 1] 的随机数int r i rand.nextInt(n - i); // 生成 [i, n - 1] 范围内的随机数swap(nums, i, r); // 将第i个元素与第r个元素交换}}// 原地交换数组中的两个元素private static void swap(int[] nums, int i, int j) {int temp nums[i]; // 临时保存 nums[i]nums[i] nums[j]; // 将 nums[j] 放到 nums[i] 的位置nums[j] temp; // 将临时保存的 nums[i] 放到 nums[j] 的位置}
}
