- 浏览: 444064 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (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 1094c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1731c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1211random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1091sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1080max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1099binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1010bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1603linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4056queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2836Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1571counting sort ------ counting ... -
priority queue
2010-12-22 00:11 2279priority queue priority queue ... -
heap sort
2010-12-18 19:09 1211heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1159merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1048insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2198以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2642排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
已排序数组 a,求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1613已排序数组 a,求其元素的绝对值 共有多少个不同的值? ... -
binary search
2010-08-29 19:35 983binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1194算法导论(2nd) 结构 * <Introductio ...
相关推荐
快速排序(Quick Sort)是由C.A.R. Hoare在1960年提出的,它是一种非常高效的排序算法,其基本思想是分治法。快速排序的基本步骤如下: 1. **选择枢轴元素**:在待排序的数组中选取一个元素作为枢轴,通常选择第一...
快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。其基本思想是采用分治法(Divide and Conquer),通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有记录都比另一部分的所有...
在这个名为"Quick sort Analysis.zip"的压缩包中,重点是分析快速排序的确定性与随机化实现。确定性快速排序通常是指每次选取固定的基准元素,如选择第一个或最后一个元素,这样对于相同的输入,排序过程完全可预测...
快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它采用分治法(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。快速排序在实现时,...
数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort
快速排序算法(Quick Sort)是一种高效的排序算法,由计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一个基准值(pivot)将数组分为两部分,其中一部分的...
python编写 快速排序 Quick Sort
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...
快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用分治法(Divide and Conquer),将一个大问题分解为两个或多个相同或相似的子问题,直到最后子问题可以简单的直接求解...
python 一行代码实现的快速排序 quick sort
### 快速排序(Quick Sort) #### 算法原理 快速排序是一种高效的排序算法,其基本思想是采用分治法(divide and conquer)来解决问题。对于待排序的数组A[0]...A[N-1],快速排序通过选择一个基准元素(pivot),通常...
快速排序(Quick Sort)源码及运行示例
快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。
算法分析与设计教学课件:Chapter 7 Quick Sort.pptx
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个C++实现的快速排序中,我们将深入理解其原理、步骤以及如何用C++语言进行编码。...
private static void sort(Comparable[] a, Comparable[] aux, int l, int r) { if (r ) return; int m = l + (r - l) / 2; sort(a, aux, l, m); // 排序左半部分 sort(a, aux, m, r); // 排序右半部分 ...
return quick_sort(left) + middle + quick_sort(right) # 示例 arr = [3, 6, 8, 10, 1, 2, 1] print(quick_sort(arr)) # 输出: [1, 1, 2, 3, 6, 8, 10] ``` 6. **时间复杂度与空间复杂度**: - **时间复杂度**...