关于快速排序的描述,网上有很多的资料, 我这里引用wiki上的解释来说明一下:
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤为:
从数列中挑出一个元素,称为 "基准"(pivot),
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形,
是数列的大小是零或一,也就是永远都已经被排序好了。
虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
而学习这个算法的时候,我发现网上有很多资料,但是唯独很少有图解的部分,对于我这样的算法新手来说,理解起来要费点劲。 OK, 现在我把我自己学习这个算法的一些东西,做个图解发上来, 希望能减少新手的学习成本,能对算法的执行过程有个直观的认识,那样的话,就会提高不少效率。(本人学习的时候,效率比较低。)
我们以java语言为例, wiki上有相关的示例:
package com.bbs;
import java.util.Comparator;
import java.util.Random;
/**
* 快速排序使用分治法(Divide and conquer)策略
* 来把一个序列(list)
* 分为两个子序列(sub-lists)。
步骤为:
1.从数列中挑出一个元素,称为 "基准"(pivot),
2.重新排序数列,
所有元素比基准值小的摆放在基准前面,
所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @author google
*/
public class QuickSort {
public static void main(String[] args) {
int[] intt={5,7,9,3,14};
qsort(intt,0,intt.length-1);
for (Integer i:intt) {
System.out.println(i);
}
}
public static final Random RND=new Random();
/**
* 交换指定元素
* @param ary
* @param i
* @param j
*/
public static void swap(int[] ary,int i,int j){
int tmp=ary[i];
ary[i]=ary[j];
ary[j]=tmp;
}
/**
* 获取枢纽元素
* @param ary
* @param begin
* @param end
* @param cmp
* @return
*/
private static int partition(int[] ary,int begin,int end){
//随即定位枢纽的位置
int index=begin+RND.nextInt(end-begin+1);
// int index=0;
//获取枢纽的值
int pivot=ary[index];
//获取枢纽后, 将其置放到数组的最后一个位置
swap(ary,index,end);
//之后循环数组, 与曲扭进行比较, 相当于重新排数组
for(int i=index=begin;i<end;i++){
//如果当前元素小于枢纽,则交换位置
if(ary[i]<pivot){
swap(ary, index++, i);
}
}
swap(ary, index, end);
return index;
}
/**
* 执行快速排序的方法
* @param ary
* @param begin
* @param end
* @param cmp
*/
public static void qsort(int[] ary,int begin,int end){
if(end>begin){
//找到枢纽
int index=partition(ary, begin, end);
qsort(ary, begin, index-1);
qsort(ary, index+1, end);
}
}
public static void sort(int[] ary){
qsort(ary, 0,ary.length-1);
}
}
下面,我以一个上述main方法中的调用为例,来把每一步算法执行过程图解一下。 当然,这个算法最核心的部分就是查找枢纽的方法。 也就是
/**
* 获取枢纽元素
* @param ary
* @param begin
* @param end
* @param cmp
* @return
*/
private static int partition(int[] ary,int begin,int end){
//随即定位枢纽的位置
int index=begin+RND.nextInt(end-begin+1);
// int index=0;
//获取枢纽的值
int pivot=ary[index];
//获取枢纽后, 将其置放到数组的最后一个位置
swap(ary,index,end);
//之后循环数组, 与曲扭进行比较, 相当于重新排数组
for(int i=index=begin;i<end;i++){
//如果当前元素小于枢纽,则交换位置
if(ary[i]<pivot){
swap(ary, index++, i);
}
}
swap(ary, index, end);
return index;
}
OK, 开始。 我们输入数组
int[] intt={5,4,7,10,3};
调用qsort方法, 其首先会要去查找枢纽位置。
public static void qsort(int[] ary,int begin,int end){
if(end>begin){
//找到枢纽
int index=partition(ary, begin, end);
qsort(ary, begin, index-1);
qsort(ary, index+1, end);
}
}
直接进入这个方法。
private static int partition(int[] ary,int begin,int end){
//随即定位枢纽的位置 这里假设index为 0 既以第一个元素 5 为枢纽值
int index=begin+RND.nextInt(end-begin+1);
//获取枢纽的值
int pivot=ary[index];
//获取枢纽后, 将其置放到数组的最后一个位置
swap(ary,index,end);
//之后循环数组, 与曲扭进行比较, 相当于重新排数组
for(int i=index=begin;i<end;i++){
//如果当前元素小于枢纽,则交换位置
if(ary[i]<pivot){
swap(ary, index++, i);
}
}
swap(ary, index, end);
return index;
}
那数组的初始图为:
在获取枢纽值后,我们将枢纽值与最后一元素交换, 则存储图为:
ok, 现在我们要做的事情就是要重排数组
既:
2.重新排序数列,
所有元素比基准值小的摆放在基准前面,
所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
(代码中体现在for循环中, for(int i=index=begin;i<end;i++)
当然,这里有个值得注意的地方, index=begin. index由原来指向枢纽的位置,被重新定位到了数组的开始位置
则进行for循环的次数为end, 这里我们要注意的是 end的实际参数值为 数组的.length-1. 这里既是4
每次循环中,数组的变化如下图, 注意, 小于枢纽5的只有 数组的第4个元素 3哦, 执行到这里,程序会有变化,注意看图:
第一次循环
第2次循环
第3次循环:
第4次循环(3<5): 交换小于枢纽的值到数组的第一位,同时index也++操作。
可以理解为记录小于枢纽的数的数量,同时也是下一个小于枢纽数的存储位置。
(如果还有小于枢纽值的话,就把它存放到ary[index++]位置上,既ary[1]上。)
最后,在for循环结束后, 需要将枢纽数放到数组的分界处,并返回枢纽的位置。return index.
(个人这样理解,因为之前说过,index代表着所有小于枢纽数数量,也是下一个小于枢纽数的位置。
那么当数组中再没有小于枢纽数的时候, index就标识枢纽值自己本身应该去的地方, 如图中的
3,5,9,14,7 这里index就是1。那么index左边的都是小于枢纽的数.)
OK,这样,快速排序就把第一次的枢纽位置找到了,然后,将数组按枢纽位置划分为2部分。
既 所有小于枢纽值的部分 ary[begin,index-1]
所有大于枢纽值的部分 ary[index+1,end]
再利用递归,分别对两部分进行再一次的quicksort.
最后,将所有的部分合并起来,就可以得到一个最后有序的数组了。
最后发一张快速排序执行的动态图, 你也可以从WIKI上找得到。
这里就快速排序的执行做了一个简单的介绍,希望对刚学快排的朋友有帮助,由于自身水平的有限,所以文章水平也很有限,希望各位拍拍砖。
- 大小: 3.7 KB
- 大小: 3.9 KB
- 大小: 8.6 KB
- 大小: 8.2 KB
- 大小: 8.5 KB
- 大小: 21.6 KB
- 大小: 18.5 KB
- 大小: 130 KB
分享到:
相关推荐
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...
现在有 1 亿的数据,请选择合适的排序算法与数据结构,在有限的时间内完成进行排序。 选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的...
1.5.3 带有限制的通配符 1.5.4 泛型static方法 1.5.5 类型限界 1.5.6 类型擦除 1.5.7 对于泛型的限制 1.6 函数对象 小结 练习 参考文献第2章 算法分析 2.1 数学基础 2.2 模型 2.3 要分析的...
1.5.3 带有限制的通配符 1.5.4 泛型static方法 1.5.5 类型限界 1.5.6 类型擦除 1.5.7 对于泛型的限制 1.6 函数对象 小结 练习 参考文献第2章 算法分析 2.1 数学基础 2.2 模型 2.3 要分析的...
1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序。(快速排序、归并排序讲到之后再做) 3、*能够显示各种排序算法的中间过程。
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
[数据结构与算法].王晓东.文字版。 第 章 引论 …………………………………… 算法及其复杂性的概念……………… 算法与程序 ………………………… 算法复杂性的概念 ………………… 算法复杂性的渐近性态 …………...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
中文名: 数据结构与算法分析_Java语言描述(第2版)作者: 韦斯译者: 冯舜玺资源格式: PDF版本: 扫描版出版社: 机械工业出版社书号: ISBN:9787111231837发行时间: 2009年01月01日地区: 大陆语言: 简体中文简介: 内容...
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...
算法分析2.1 数学基础2.2 模型2.3 要分析的问题2.4 运行时间计算2.4.1 一个简单的例子2.4.2 一般法则2.4.3 最大子序列和问题的求解2.4.4 运行时间中的对数2.4.5 检验你的分析2.4.6 分析结果的准确性小结练习参考文献...