kuchaguangjie
- 浏览: 442723 次
- 性别:
- 来自: 深圳
-
文章分类
- 全部博客 (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 1079c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1722c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1203random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1077sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1071max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1089binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1005bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1592linked list 链表， - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4047queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2825Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1561counting sort ------ counting ... -
priority queue
2010-12-22 00:11 2267priority queue priority queue ... -
heap sort
2010-12-18 19:09 1204heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1147merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1043insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2188以 z 字型 读取 矩阵， ... -
排序算法：求 长度为 n的 数组中，最大的 m个数
2010-08-31 10:16 2626排序:数组 length=m，从其中中取出最大的 n 数字，n ... -
已排序数组 a，求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1597已排序数组 a，求其元素的绝对值 共有多少个不同的值？ ... -
binary search
2010-08-29 19:35 966binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1184算法导论(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. **时间复杂度与空间复杂度**： - **时间复杂度**...