珠海网站建设公司排名,黄冈论坛东部社区,中山做营销型网站,网站自然优化是什么意思快速排序算法由 C. A. R. Hoare 在 1960 年提出。它的时间复杂度也是 O(nlogn)#xff0c;但它在时间复杂度为 O(nlogn) 级的几种排序算法中#xff0c;大多数情况下效率更高#xff0c;所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用#xff0c;使得… 快速排序算法由 C. A. R. Hoare 在 1960 年提出。它的时间复杂度也是 O(nlogn)但它在时间复杂度为 O(nlogn) 级的几种排序算法中大多数情况下效率更高所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用使得快速排序深受面试官的青睐所以掌握快速排序的思想尤为重要。 快速排序算法的基本思想是
从数组中取出一个数称之为基数pivot遍历数组将比基数大的数字放到它的右边比基数小的数字放到它的左边。遍历完成后数组被分成了左右两个区域将左右两个区域视为两个数组重复前两个步骤直到排序完成 事实上快速排序的每一次遍历都将基数摆到了最终位置上。第一轮遍历排好 1 个基数第二轮遍历排好 2 个基数每个区域一个基数但如果某个区域为空则此轮只能排好一个基数第三轮遍历排好 4 个基数同理最差的情况下只能排好一个基数以此类推。总遍历次数为 lognn 次每轮遍历的时间复杂度为 O(n)所以很容易分析出快速排序的时间复杂度为 O(nlogn) O(n^2)平均时间复杂度为 O(nlogn)。 快速排序递归框架
根据我们分析出的思路先搭出快速排序的架子
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
public static int partition(int[] arr, int start, int end) {// TODO: 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
}
partition 意为“划分”我们期望 partition 函数做的事情是将 arr 从 start 到 end 这一区间的值分成两个区域左边区域的每个数都比基数小右边区域的每个数都比基数大然后返回中间值的下标。
只要有了这个函数我们就能写出快速排序的递归函数框架。首先调用 partition 函数得到中间值的下标 middle然后对左边区域执行快速排序也就是递归调用 quickSort(arr, start, middle - 1)再对右边区域执行快速排序也就是递归调用 quickSort(arr, middle 1, end)。
现在还有一个问题何时退出这个递归函数呢 退出递归的边界条件 很容易想到当某个区域只剩下一个数字的时候自然不需要排序了此时退出递归函数。实际上还有一种情况就是某个区域只剩下 0 个数字时也需要退出递归函数。当 middle 等于 start 或者 end 时就会出现某个区域剩余数字为 0。
所以我们可以通过这种方式退出递归函数
public static void quickSort(int[] arr, int start, int end) {// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 当左边区域中至少有 2 个数字时对左边区域快速排序if (start ! middle start ! middle - 1) quickSort(arr, start, middle - 1);// 当右边区域中至少有 2 个数字时对右边区域快速排序if (middle ! end middle ! end - 1) quickSort(arr, middle 1, end);
} 在递归之前先判断此区域剩余数字是否为 0 个或者 1 个当数字至少为 2 个时才执行这个区域的快速排序。因为我们知道 middle start middle end 必然成立所以判断剩余区域的数字为 0 个或者 1 个也就是指 start 或 end 与 middle 相等或相差 1。
我们来分析一下这四个判断条件
当 start middle 时相当于 quickSort(arr, start, middle - 1) 中的 start end 1当 start middle - 1 时相当于 quickSort(arr, start, middle - 1) 中的 start end当 middle end 时相当于 quickSort(arr, middle 1, end) 中的 start end 1当 middle end -1 时相当于 quickSort(arr, middle 1, end) 中的 start end
综上我们可以将此边界条件统一移到 quickSort 函数之前
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end || start end 1) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
} 更进一步由上文所说的 middle start middle end 可以推出除了start end || start end 1这两个条件之外其他的情况下 start 都小于 end。所以我们可以将这个判断条件再次简写为
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
} 这样我们就写出了最简洁版的边界条件我们需要知道这里的 start end 实际上只有两种情况
start end: 表明区域内只有一个数字start end 1: 表明区域内一个数字也没有
不会存在 start 比 end 大 2 或者大 3 之类的。 分区算法实现 快速排序中最重要的便是分区算法也就是 partition 函数。大多数人都能说出快速排序的整体思路但实现起来却很难一次写对。主要问题就在于分区时存在的各种边界条件需要读者亲自动手实践才能加深体会。 上文已经说到partition 函数需要做的事情就是将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标。那么首先我们要做的事情就是选择一个基数基数我们一般称之为 pivot意为“轴”。整个数组就像围绕这个轴进行旋转小于轴的数字旋转到左边大于轴的数字旋转到右边。所谓的双轴快排就是一次选取两个基数将数组分为三个区域进行旋转关于双轴快排的内容我们将在后续章节讲解。 基数的选择 基数的选择没有固定标准随意选择区间内任何一个数字做基数都可以。通常来讲有三种选择方式
选择第一个元素作为基数选择最后一个元素作为基数选择区间内一个随机元素作为基数
选择的基数不同算法的实现也不同。实际上第三种选择方式的平均时间复杂度是最优的待会分析时间复杂度时我们会详细说明。
本文通过第一种方式来讲解快速排序
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;// TODO
} 最简单的分区算法 分区的方式也有很多种最简单的思路是从 left 开始遇到比基数大的数就交换到数组最后并将 right 减一直到 left 和 right 相遇此时数组就被分成了左右两个区域。再将基数和中间的数交换返回中间值的下标即可。
按照这个思路我们敲出了如下代码
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;// left、right 相遇时退出循环while (left right) {// 找到第一个大于基数的位置while (left right arr[left] pivot) left;// 交换这两个数使得左边分区都小于或等于基数右边分区大于或等于基数if (left ! right) {exchange(arr, left, right);right--;}}// 如果 left 和 right 相等单独比较 arr[right] 和 pivotif (left right arr[right] pivot) right--;// 将基数和中间数交换if (right ! start) exchange(arr, start, right);// 返回中间值的下标return right;
}
private static void exchange(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}因为我们选择了数组的第一个元素作为基数并且分完区后会执行将基数和中间值交换的操作这就意味着交换后的中间值会被分到左边区域。所以我们需要保证中间值的下标是分区完成后最后一个比基数小的值这里我们用 right 来记录这个值。 这段代码有一个细节。首先在交换 left 和 right 之前我们判断了 left ! right这是因为如果剩余的数组都比基数小则 left 会加到 right 才停止这时不应该发生交换。因为 right 已经指向了最后一个比基数小的值。 但这里的拦截可能会拦截到一种错误情况如果剩余的数组只有最后一个数比基数大left 仍然加到 right 停止了但我们并没有发生交换。所以我们在退出循环后单独比较了 arr[right] 和 pivot。 实际上这行单独比较的代码非常巧妙一共处理了三种情况
一是刚才提到的剩余数组中只有最后一个数比基数大的情况二是 left 和 right 区间内只有一个值则初始状态下 left right所以 while (left right) 根本不会进入所以此时我们单独比较这个值和基数的大小关系三是剩余数组中每个数都比基数大此时 right 会持续减小直到和 left 相等退出循环此时 left 所在位置的值还没有和 pivot 进行比较所以我们单独比较 left 所在位置的值和基数的大小关系
双指针分区算法 除了上述的分区算法外还有一种双指针的分区算法更为常用从 left 开始遇到比基数大的数记录其下标再从 right 往前遍历找到第一个比基数小的数记录其下标然后交换这两个数。继续遍历直到 left 和 right 相遇。然后就和刚才的算法一样了交换基数和中间值并返回中间值的下标。
代码如下
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;while (left right) {// 找到第一个大于基数的位置while (left right arr[left] pivot) left;// 找到第一个小于基数的位置while (left right arr[right] pivot) right--;// 交换这两个数使得左边分区都小于或等于基数右边分区大于或等于基数if (left right) {exchange(arr, left, right);left;right--;}}// 如果 left 和 right 相等单独比较 arr[right] 和 pivotif (left right arr[right] pivot) right--;// 将基数和轴交换exchange(arr, start, right);return right;
}
private static void exchange(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
} 同样地我们需要在退出循环后单独比较 left 和 right 的值。 从代码实现中可以分析出快速排序是一种不稳定的排序算法在分区过程中相同数字的相对顺序可能会被修改。 时间复杂度 空间复杂度 快速排序的时间复杂度上文已经提到过平均时间复杂度为 O(nlogn)最坏的时间复杂度为 O(n^2)空间复杂度与递归的层数有关每层递归会生成一些临时变量所以空间复杂度为 O(logn) ~ O(n)平均空间复杂度为 O(logn)。 快速排序的优化思路 第一种就是我们在前文中提到的每轮选择基数时从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低了。所以我们才说用这种方式选择基数其平均时间复杂度是最优的 第二种解决方案是在排序之前先用洗牌算法将数组的原有顺序打乱以防止原数组正序或逆序。 Java 已经将洗牌算法封装到了集合类中即 Collections.shuffle() 函数。洗牌算法由 Ronald A.Fisher 和 Frank Yates 于 1938 年发明思路是每次从未处理的数据中随机取出一个数字然后把该数字放在数组中所有未处理数据的尾部。 Collections.shuffle() 函数源码如下
private static final int SHUFFLE_THRESHOLD 5;public static void shuffle(List? list, Random rnd) {int size list.size();if (size SHUFFLE_THRESHOLD || list instanceof RandomAccess) {for (int isize; i1; i--)swap(list, i-1, rnd.nextInt(i));} else {Object arr[] list.toArray();// Shuffle arrayfor (int isize; i1; i--)swap(arr, i-1, rnd.nextInt(i));// Dump array back into list// instead of using a raw type here, its possible to capture// the wildcard but it will require a call to a supplementary// private methodListIterator it list.listIterator();for (int i0; iarr.length; i) {it.next();it.set(arr[i]);}}
}public static void swap(List? list, int i, int j) {// instead of using a raw type here, its possible to capture// the wildcard but it will require a call to a supplementary// private methodfinal List l list;l.set(i, l.set(j, l.get(i)));
}private static void swap(Object[] arr, int i, int j) {Object tmp arr[i];arr[i] arr[j];arr[j] tmp;
} 从源码中可以看出对于数据量较小的列表少于 5 个值shuffle 函数直接通过列表的 set 方法进行洗牌否则先将 list 转换为 array再进行洗牌以提高交换效率洗牌完成后再将 array 转成 list 返回。 还有一种解决方案既然数组重复排序的情况如此常见那么我们可以在快速排序之前先对数组做个判断如果已经有序则直接返回如果是逆序则直接倒序即可。在 Java 内部封装的 Arrays.sort() 的源码中就采用了此解决方案。
