冒泡是交换排序的基础算法,而快排是交换排序的高级算法。快排给我的感觉跟插入排序的感觉很像,都有点挖坑填数的感觉。不同的是插入是一个一个元素的定位,少了分而治之.
快速排序主要思路是: 挖坑填数 + 分治法(Divided-and-ConquerMethod).
分治法相对来说,还是很好理解,从字面就可以看出,分而治之的意思,以某个标准,或者说是以数组某个元素为中介,将数组划分为两部分,分别进行排序.
而挖坑填数,则是理解的难点,尤其是习惯了冒泡算法的交换之后,思路很不容易扭转过来.借用网上的一个例子:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
第一步, 选择一个pivotpos枢轴点. 其实不要被枢轴这两个看起来高大上的字眼给唬住.理解了的话, 其实就是任意选取一个数值而已.一般我们默认就选第一个.
将a[0]=72拿到一边去.数组变为:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
XX |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
然后a[0]就空出来了,变成一个等着被填的坑.
第二步,从右至左遍历数组,寻找比a[0]=72小的第一个数字,也就是48. 将48 填进72空出来的坑.于是数组变为:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
XX |
85 |
第三步,从左至右遍历数组,寻找比a[0]=72大的第一个数字,也就是88,将88填入刚才空出来的坑:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
48 |
6 |
57 |
XX |
60 |
42 |
83 |
73 |
88 |
85 |
循环第二步, 从右到左找小数,为42,填坑:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
48 |
6 |
57 |
42 |
60 |
XX |
83 |
73 |
88 |
85 |
循环第三步,从左到右找大数,到坑的index为止,a[0-4]都比72小.没有选择了,于是枢轴点a[0]=72入坑:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
到此,第一个数字的位置确定下来了.左边都是比它小的,右边都是比它大的.再以72为中点,将数组两边分别看作是一个数组.再次用刚才的方法排序.即可完成最终的排序.我想这也是枢轴点这个词的由来吧.
继续算法,对于左边部分:
48拿出来,42放进去:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
42 |
6 |
57 |
XX |
60 |
72 |
83 |
73 |
88 |
85 |
57放进去,48最后入坑:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
42 |
6 |
48 |
57 |
60 |
72 |
83 |
73 |
88 |
85 |
接下来,再次对48左右两边分而治之:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
6 |
42 |
48 |
57 |
60 |
72 |
83 |
73 |
88 |
85 |
待左边排序完成,对最早的枢轴点72右边进行排序:
83拿出来,73比它小,入坑:
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
6 |
42 |
48 |
57 |
60 |
72 |
73 |
83 |
88 |
85 |
当划分出来的数组长度为1时,递归结束。
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Value |
6 |
42 |
48 |
57 |
60 |
72 |
73 |
83 |
85 |
88 |
当划分出来的数组长度为1时,递归结束。遍历完成,标为黄色的数字是被选为枢轴的数字。
而其中运用到了递归分别对两端再次遍历,就是常说的分治法.晚点补上代码实现.
public class MyQuickSort { /** * 分治法, 确定每个枢轴的位置. * * @param a * @param low * @param high * @return */ private static int partition(int[] a, int low, int high) { int pivot = a[low]; while (low < high) { while (low < high && a[high] >= pivot) { // 找到右边第一个比枢轴小的值,循环退出. high--; } a[low] = a[high]; while (low < high && a[low] <= pivot) { // 左边找到第一个比枢轴大的值,循环退出. low++; } a[high] = a[low]; } a[low] = pivot; return low; } /** * 快速排序, 用递归不断迭代出每次枢轴两边的数组部分. * * @param a */ public static void quickSort(int[] a, int low, int high) { if (low < high) { //不加会堆溢出. int pivotPos = partition(a, low, high); quickSort(a, low, pivotPos - 1); quickSort(a, pivotPos + 1, high); } } /** * main(),测试用. * * @param args */ public static void main(String[] args) { int[] a = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85}; quickSort(a, 0, a.length - 1); for (int i : a) { System.out.print(i + " "); } } }
相关推荐
该资源包括实用练习,让读者可以练习在Java中实现快速排序,并提供解决方案以帮助读者检查自己的工作并深入理解所学内容。 无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,...
快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中...
本次提供的C语言项目源码合集涵盖了10个经典的数据结构课程设计实例,包括二叉树的建立与遍历、冒泡排序、快速排序等。这些实例不仅是对C语言编程能力的锻炼,更是对数据结构深入理解的有效实践。 其中,二叉树实例...
网上也有很多类似的代码.在这里写一下自己对快速排序的理解. 快速排序() { { 将a[n]分为三个部分 第一个部分 小于或等于A的,a[m]到a
冒泡排序、快速排序、简单插入排序、希尔排序、简单选择排序、堆叠排序六种数据结构必考的排序方式理解
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定。 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用...
一个自己怎么弄不懂的算法,快速排序确实有点难理解,学习学习
本资源包含了一系列精心编写的C和C++源码示例,旨在帮助开发者更好地理解和掌握这两种语言的核心概念和高级特性。这些源码覆盖了从基础语法到数据结构、算法实现等多个方面,适合不同水平的开发者学习和参考。 适用...
1、掌握快速排序随机算法的设计思想与方法。...3、利用实验测试给出不同快速排序算法的性能以理解其优缺点。 快速排序是算法导论中的经典算法。在本实验中,给定一个长为 n 的整数数 组,要求将数组升序排序。
用erlang语言实现的快速排序程序,简洁明了,能立即理解快速排序的核心思想
(2)理解快速排序方法的求解过程; (3)掌握快速排序方法运算。 3、实验内容及要求: (1)建立包含30个数据的序列(数据元素的值由自己设定); (2)完成快速排序运算的程序; (3)给出程序和快速排序前后的...
下面是我对快速排序的理解,和快速排序,去重的代码. 1.什么是快速排序? 第一步: 快速排序就是去个中间值,把比中间值小的放在左边设为arrLeft,比中间值大的放在右边设为arrRight 第二步: 对arrLeft进行第一步,对...
用C++语言实现的几个常见算法,里面有注解,方便大家理解,简单易学,都可以正常编译运行。
在这个示例中,我们首先定义了一个swap函数用于交换数组中两个元素的值,以及一个partition函数用于对数组进行分区操作。然后定义了quickSort函数来实现...希望这个示例能帮助你理解如何在C语言中实现快速排序算法!
c++快排(快速排序)的源代码。代码简洁明了。让您知道理解快排。 用一个函数解决快排问题。 请您赶快来下载吧!
快速排序**快速排序的四种方法实现以及优化:小学生也能理解的大智慧** **内容概要:** 本文为您详细介绍了快速排序的四种实现方法以及一些优化技巧,旨在帮助开发者掌握快速排序的核心知识。内容涵盖快速排序的定义...
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
注:由于我对排序算法理解的也不深,可能存在错误,请谅解指正谢谢.排序算法有很多,包括插入排序,冒泡排序,堆排序,归并排序,选择排序,计数排序,基数排序,桶排序,快速排序等。插入排序,堆排序,选择排序,归并...