大家好,欢迎来到IT知识分享网。
快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列不断分割成较小的子序列,然后对每个子序列进行排序,最后合并得到有序的序列。快速排序在大多数情况下具有优异的性能,是许多常见排序算法中最快的之一。
基本思想
这里的动画用大佬五分钟学算法的图,很清晰
- 选择一个基准元素(pivot)作为参考点。
- 将所有比基准元素小的元素移到基准元素的左边,将所有比基准元素大的元素移到基准元素的右边。此过程称为分区(partitioning)。
- 对基准元素左右两边的子序列递归地进行相同的快速排序,直到子序列的大小为1或0,表示子序列已经有序。
如上图所示,快速排序的基本思想就是选取一个基准数,将基准数小的都放在左边,大的都放在右边,也就是每次循环都会确定出基准数应该在的正确位置。
代码实现
对应在代码层面,需要使用到递归法来实现,对于快速排序来说,递归相对还是很容易想到的
java复制代码/ * @author HelloCode * @blog https://www.hellocode.top * @date 2023年08月08日 21:14 */ public class QuickSort { public static void quickSort(int[] arr) { // 特殊情况处理 if (arr == null || arr.length == 0 || arr.length == 1) { return; } // 递归入口 sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int left, int right) { // 递归出口 if (left > right) { return; } // 初始化双指针 int i = left, j = right; // 选取基准数 int base = arr[left]; while (i != j) { // (注意!!!!)从右边开始 // 找比基准数小的 while (i < j && arr[j] >= base) { j--; } // 从左边找比基准数大的 while (i < j && arr[i] <= base) { i++; } // 交换i j if (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 基准数归位(此时i == j) arr[left] = arr[i]; arr[i] = base; // 开始左右两边分别快排 sort(arr, left, i - 1); sort(arr, i + 1, right); } }
这里先移动j还是先移动i主要是需要看基准数选取的位置,如果选最左边的数,就需要先移动j(确保i == j 时对应的值是小于基准数的,再把基准数和该数交换,符合排序规则) 如果选取的基准数是最右边,则先移动i指针(确保 i == j 时对应的值是大于基准数的)
测试:
java复制代码/ * @author HelloCode * @blog https://www.hellocode.top * @date 2023年08月08日 21:14 */ public class Test { public static void main(String[] args) { int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12}; System.out.println("排序前:" + Arrays.toString(arr)); QuickSort.quickSort(arr); System.out.println("排序后:" + Arrays.toString(arr)); } }
优化
快排的优化主要需要关注基准数的选取,如果待排序数组整体偏降序,此时还选最左侧的为基准数的话,效率就相对慢一些,所以选取一个好的基准数可以让快排的效率更加稳定~
主要的方法有以下几种:
- 随机选择基准元素:选择随机的基准元素可以降低最坏情况的概率,进而提高算法性能。
- 三数取中法:在选取基准元素时,不是简单地选取第一个或最后一个元素,而是选择中间元素、第一个元素和最后一个元素中的中位数作为基准元素,也可以降低最坏情况的概率。
这里基准数的选取可以很巧妙,还有很多种其他方法,都可以降低最坏情况的发生,本文以三数取中法为例:
java复制代码/ * @author HelloCode * @blog https://www.hellocode.top * @date 2023年08月08日 21:14 */ public class QuickSort { public static void quickSort(int[] arr) { // 特殊情况处理 if (arr == null || arr.length == 0 || arr.length == 1) { return; } // 递归入口 sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int left, int right) { // 递归出口 if (left > right) { return; } // 初始化双指针 int i = left, j = right; // 选取基准数 getBase(arr, left, right); int base = arr[left]; while (i != j) { // (注意!!!!)从右边开始 // 找比基准数小的 while (i < j && arr[j] >= base) { j--; } // 从左边找比基准数大的 while (i < j && arr[i] <= base) { i++; } // 交换i j if (i < j) { swap(arr, i, j); } } // 基准数归位(此时i == j) arr[left] = arr[i]; arr[i] = base; // 开始左右两边分别快排 sort(arr, left, i - 1); sort(arr, i + 1, right); } // 取三点中间值(最终会移动到left位置,这样可以不改变原有代码) private static void getBase(int[] arr, int left, int right) { // 这里可以防止溢出且使用 >> 效率相对能高一些 // 等价于 (left + right) / 2 int mid = left + ((right - left) >> 1); // 确保第一个元素最小 if (arr[left] > arr[right]) { swap(arr, left, right); } // 确保最后一个元素最大 if (arr[mid] > arr[right]) { swap(arr, mid, right); } // 确定mid就是中间值,交换到最左边 if (arr[left] < arr[mid]) { swap(arr, left, mid); } System.out.println("基准数为:" + arr[left]); } // 交换数组两下标元素位置 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
测试:
java复制代码/ * @author HelloCode * @blog https://www.hellocode.top * @date 2023年08月07日 21:02 */ public class Test { public static void main(String[] args) { int[] arr = {21, 13, 4, 10, 7, 65, 32, 15, 32, 19}; System.out.println("排序前:" + Arrays.toString(arr)); BubbleSort.bubbleSortOptimized1(arr); System.out.println("排序后:" + Arrays.toString(arr)); } }
txt复制代码排序前:[21, 13, 4, 10, 7, 65, 32, 15, 32, 19, 33, 65, 89, 72, 12] 基准数为:15 基准数为:7 基准数为:4 基准数为:12 基准数为:10 基准数为:13 基准数为:32 基准数为:21 基准数为:19 基准数为:32 基准数为:65 基准数为:33 基准数为:65 基准数为:72 基准数为:89 排序后:[4, 7, 10, 12, 13, 15, 19, 21, 32, 32, 33, 65, 65, 72, 89]
总结
优点
- 高效性:快速排序是一种高效的排序算法,在大多数实际情况下,它的性能通常比其他常见排序算法(如冒泡排序、插入排序)更好。
- 原地排序:快速排序是原地排序算法,不需要额外的辅助空间,只需在原始数组上进行交换操作。
缺点
- 最坏情况下的性能:当待排序序列已经基本有序或完全逆序时,快速排序的时间复杂度退化为 O(n^2),导致性能下降。这是因为基准元素的选择可能导致分区不平衡,使得分区操作不再能有效地减少问题规模。
- 不稳定性:快速排序是一种不稳定的排序算法,意味着相等元素的相对顺序在排序后可能发生变化。这在某些情况下可能导致问题,特别是对于复杂对象的排序,需要额外的处理来保持稳定性。
复杂度
- 时间复杂度:快速排序的平均时间复杂度为O(n log n),最坏情况下为O(n^2)。
- 空间复杂度:快速排序是原地排序算法,空间复杂度为O(log n)。
适用于处理大规模数据集的排序,尤其在平均情况下,快速排序的性能较优。但在处理已经有序或近乎有序的数据集时,快速排序的性能可能会下降,这时候其他稳定的排序算法可能更合适。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/93686.html