- 浏览: 436235 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
quicksort
------
quicksort overview
quicksort 在实际应用中 非常出色,
时间复杂度:
理论上最差是:O(n^2),
实际应用中:平均可达到 O(n * lg(n)),且其中的 常量 比较小,
空间复杂度:
空间占用比较小,有优势,
即使在 虚拟内存中 也运行得较好,
------
quicksort 原理
quicksort 采用 divide-conquer 方法,
分3步:
* divide
将 A[p .. r] 分解为 A[p .. q-1] 和 A[q+1 .. r] 2个子数组,分解函数称为 partition,
2个子数组 满足:
A[p .. q-1] 中所有元素 <= A[q],
A[q+1 .. r] 中所有元素 >= A[q],
* conquer
对2个子数组,递归调用 partition ,进行分解,
* combine
合并子数组,从底到上合并时,都是排过序的,因此不需要额外操作,直接合并即可,
*
partition 分解 函数:
取最后1个值作为中间值,前面的值依次和该值比较,然后决定放到该值的前面还是后面,
当然可以根据实际情况,决定取哪个值作为分隔值,基本原则是 balance,即 所取的值可以将数组分隔为大小相近的2个子数组,
------
性能
性能取决于 分割点是否平衡,即 分割点的值在被分割数组中是否处于中间,
越平衡性能就越好,越不平衡性能越差,
最差性能是 O(n^2):
每次分割点都是 最大 或 最小值 时发生,
最好性能是 O(n*(lg n))
分割点每次都是 中间值时发生,
平均性能:
在实际应用中,quicksort 的性能更接近于 最好性能 O(n*(lg n)),
------
例子:
* js (quick_sort.js)
* html
*
------
------
quicksort overview
quicksort 在实际应用中 非常出色,
时间复杂度:
理论上最差是:O(n^2),
实际应用中:平均可达到 O(n * lg(n)),且其中的 常量 比较小,
空间复杂度:
空间占用比较小,有优势,
即使在 虚拟内存中 也运行得较好,
------
quicksort 原理
quicksort 采用 divide-conquer 方法,
分3步:
* divide
将 A[p .. r] 分解为 A[p .. q-1] 和 A[q+1 .. r] 2个子数组,分解函数称为 partition,
2个子数组 满足:
A[p .. q-1] 中所有元素 <= A[q],
A[q+1 .. r] 中所有元素 >= A[q],
* conquer
对2个子数组,递归调用 partition ,进行分解,
* combine
合并子数组,从底到上合并时,都是排过序的,因此不需要额外操作,直接合并即可,
*
partition 分解 函数:
取最后1个值作为中间值,前面的值依次和该值比较,然后决定放到该值的前面还是后面,
当然可以根据实际情况,决定取哪个值作为分隔值,基本原则是 balance,即 所取的值可以将数组分隔为大小相近的2个子数组,
------
性能
性能取决于 分割点是否平衡,即 分割点的值在被分割数组中是否处于中间,
越平衡性能就越好,越不平衡性能越差,
最差性能是 O(n^2):
每次分割点都是 最大 或 最小值 时发生,
最好性能是 O(n*(lg n))
分割点每次都是 中间值时发生,
平均性能:
在实际应用中,quicksort 的性能更接近于 最好性能 O(n*(lg n)),
------
例子:
* js (quick_sort.js)
var arr_quicksort = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ]; /** * quict sort<br /> * <pre> * <b>思路:</b> * divide-and-conquer, * 将数组 分成 左中右 3部分,左右是2个数组,左数组所有值 <= 中间值,右数组所有值 >= 中间值, * 直到最后所有值都被分解为单个值,而且已经是排过序的, * </pre> * <b>时间复杂度:</b>理论上最差是 O(n^2),实际应用中是 O(n * (lg n)),且常量系数较小<br /> * <b>空间复杂度:</b>O(n),即使在虚拟内存中也运行良好<br /> * * @author kuchaguangjie * @date 2011年1月1日 * @return */ function QuickSort(initArr) { this.totalCount = initArr.length; this.tmpArr = [ initArr ]; this.resultArr = []; } /** * 排序调用入口 * * @return */ QuickSort.prototype.sort = function() { while (this.resultArr.length < this.totalCount) { this.partition(); } return this.resultArr; }; /** * 将1个数组 分成 左中右 3块,满足:左 <= 中 <= 右,并将3块放到1个数组返回, * * @param arr * 待分解的数组 * @return */ QuickSort.prototype.partitionSingle = function(arr) { if (arr.length <= 1) { return arr; } var partLeftArr = []; var partRightArr = []; var partMiddle = arr[arr.length - 1]; // 最后1个元素,用作分隔值 for ( var i = 0; i < arr.length - 1; i++) { if (arr[i] <= partMiddle) { partLeftArr[partLeftArr.length] = arr[i]; } else { partRightArr[partRightArr.length] = arr[i]; } } var partArr = []; if (partLeftArr.length > 0) { if (partLeftArr.length == 1) { partArr[0] = partLeftArr[0]; } else { partArr[0] = partLeftArr; } } partArr[partArr.length] = partMiddle; if (partRightArr.length > 0) { if (partRightArr.length == 1) { partArr[partArr.length] = partRightArr[0]; } else { partArr[partArr.length] = partRightArr; } } return partArr; }; /** * 对整个数组做1次 partition * * @return */ QuickSort.prototype.partition = function() { this.resultArr = []; for ( var i = 0; i < this.tmpArr.length; i++) { if (QuickSort.prototype.isArray(this.tmpArr[i])) { // 是 array 则分解 var partArr = this.partitionSingle(this.tmpArr[i]); for ( var j = 0; j < partArr.length; j++) { this.resultArr[this.resultArr.length] = partArr[j]; } } else { // 单个数字 this.resultArr[this.resultArr.length] = this.tmpArr[i]; } } if (this.resultArr.length < this.totalCount) { this.tmpArr = this.resultArr.slice(0, this.resultArr.length); } }; /** * 检验是否是 Array * * @param v * @return */ QuickSort.prototype.isArray = function(v) { return Object.prototype.toString.apply(v) === '[object Array]'; }
* html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <script type="text/javascript" src="js/quick_sort.js"></script> </head> <body> <input type="button" value="quick sort" onclick="alert(new QuickSort(arr_quicksort).sort());" /> </body> </html>
*
------
发表评论
-
c - linkedlist
2012-05-10 14:52 1026c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1670c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1172random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1030sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1038max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1043binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 970bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1554linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4007queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2776Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1525counting sort ------ counting ... -
priority queue
2010-12-22 00:11 2223priority queue priority queue ... -
heap sort
2010-12-18 19:09 1169heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1113merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1008insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2141以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2585排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
已排序数组 a,求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1556已排序数组 a,求其元素的绝对值 共有多少个不同的值? ... -
binary search
2010-08-29 19:35 919binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1143算法导论(2nd) 结构 * <Introductio ...
相关推荐
quick sort 快速排序的代码实现~
数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort
python编写 快速排序 Quick Sort
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...
python 一行代码实现的快速排序 quick sort
快速排序(Quick Sort)
基于python的排序算法-快速排序Quick Sort
快速排序(Quick Sort)源码及运行示例
快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。
算法分析与设计教学课件:Chapter 7 Quick Sort.pptx
最差情况下达到O(NlogN)
非常通俗易懂的merge归并,和quick快速排序算法讲解。并含代码。
搜索算法源码:合并排序,快速排序,shell排序,插入排序,堆排序,冒泡排序,桶排序
快速排序算法图解,用图片的形式,清晰解构算法原理和实现过程,值得推荐。
实现快速排序,Implement Quicksort and answer the following questions. (1) How many comparisons will Quicksort do on a list of n elements that all have the same value? (2) What are the maximum and ...
实现确定性和随机化的两种快速排序算法,用实验数据分析算法的时间效率和稳定性。 (对相同的输入,随机算法均要运行多次,并用曲线图和表格的形式比较实验结果)。
快速排序算法的代码以及一些应用,在Linux下用vim编写的,gcc编译通过