冒泡是交换排序的基础算法,而快排是交换排序的高级算法。快排给我的感觉跟插入排序的感觉很像,都有点挖坑填数的感觉。不同的是插入是一个一个元素的定位,少了分而治之.
快速排序主要思路是: 挖坑填数 + 分治法(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 + " "); } } }
相关推荐
并行快速排序实验不仅加深了对快速排序算法的理解,还为学生提供了实践并行计算的机会。通过在多处理器系统上实现快速排序算法,学生能够亲身体验并行计算如何提升算法效率,同时熟悉MPI系统的通信机制,为将来在...
冒泡排序虽然效率相对较低,但在这个示例中可能作为对比或辅助理解快速排序的工具。 在这个“jiaoben181359”文件中,很可能包含了HTML页面、CSS样式表和JavaScript脚本,这些组合在一起构成了排序动画的前端部分。...
快速排序的过程主要包括两个步骤:选择一个基准元素并根据它将数组分为两部分,一部分的元素都比基准小,另一部分的元素都比基准大,然后对这两部分分别进行快速排序。这种算法的平均时间复杂度为O(n log n),在最坏...
首先,我们来深入理解快速排序。快速排序是由英国计算机科学家C.A.R. Hoare在1960年提出的。其基本思想是分治法(Divide and Conquer)。快速排序的步骤如下: 1. 选择一个元素作为“基准”(pivot)。 2. 将所有...
快速排序和归并排序是两种常用的排序算法,它们在计算机科学和互联网领域有着广泛的应用。本次实验的主要目的是对比这两种算法在平均情况下的运行效率,并通过实际编程和实验数据来加深对时间复杂度的理解。 快速...
快速排序和归并排序是两种常见的排序算法,它们在不同的场景下有着各自的优势。本实验旨在比较这两种算法在平均情况下的运行效率,加深对时间复杂度概念的理解。 快速排序是一种基于分治策略的排序算法,由英国...
快速排序的时间复杂度在最坏情况下为O(n^2),但在大多数情况下都能达到O(n log n)的平均时间复杂度,这使得它成为实际应用中最常用的排序算法之一。 ### 工作原理 快速排序的核心步骤包括选择一个基准值(pivot),...
本项目着重探讨了两种经典的排序算法——冒泡排序和快速排序,并通过C语言进行了实现。这两种排序算法各有特点,理解它们的工作原理及其优缺点对于提升编程技能和理解算法效率至关重要。 **冒泡排序** 是一种简单...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法...同时,快速排序也是许多算法竞赛和面试中常见的考察点,理解其工作原理和实现方式对于提升编程技能十分有益。
本资源“C# 简单的冒泡、快速排序及二分法查找.zip”显然关注的是数据排序和查找算法的实现,这些都是计算机科学和编程的基础知识。 首先,我们来探讨冒泡排序(Bubble Sort)。这是一种简单的交换排序方法,适用于...
在本实验中,我们主要探讨了三种经典的排序算法:插入排序、快速排序和选择排序。这些排序算法是计算机科学中的基础,特别是在数据结构和算法领域。以下是对这三种排序算法的详细说明: **插入排序(Insertion Sort...
在这个zip压缩包中,包含了三种不同的快速排序分区方法的Java实现:快速排序三分法、快速排序单向扫描分区法和快速排序双向扫描分区法。 1. **快速排序三分法**: 三分法快速排序是基于快速排序的一种改进,其核心...
这里我们将深入探讨几种常见的排序算法:冒泡排序、插入排序、快速排序、双路快速排序、三路快速排序以及堆排序。 **1. 冒泡排序** 冒泡排序是最基础的排序算法之一,其工作原理类似于水底下的气泡逐渐上浮。通过...
为了更好地理解快速排序的实现细节,下面将详细介绍具体的代码实现过程。 1. **分区函数**:分区函数负责将数组分为两部分。具体实现如下: ```c #include <stdio.h> void swap(int *a, int *b) { int temp =...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法...通过阅读并理解`qk.java`文件中的代码,我们可以深入学习快速排序的实现细节,并将其运用到自己的编程实践中。
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and ...学习并理解这些代码可以帮助开发者更有效地在嵌入式系统中实现快速排序,提高程序的运行效率。
本实验报告的主要目的是学习合并排序和快速排序算法的思想,掌握原理,并运用这些算法的思想进行编程实现,以加深理解。 一、实验目的 学习合并排序和快速排序算法的思想,掌握原理。运用合并排序和快速排序算法的...
冒泡排序和快速排序是两种在计算机科学中广泛使用的排序算法,它们都在Python编程语言中有具体的应用...通过理解冒泡排序和快速排序的工作原理,我们可以更好地选择和优化排序操作,特别是在处理大量数据或特定场景时。