`

quick sort

阅读更多
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)
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>


*

------
分享到:
评论

相关推荐

    sort_exp.rar_quick sort_桶排序

    快速排序(Quick Sort)是由C.A.R. Hoare在1960年提出的,它是一种非常高效的排序算法,其基本思想是分治法。快速排序的基本步骤如下: 1. **选择枢轴元素**:在待排序的数组中选取一个元素作为枢轴,通常选择第一...

    Quick Sort in the worst case

    快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。其基本思想是采用分治法(Divide and Conquer),通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有记录都比另一部分的所有...

    Quick sort Analysis.zip

    在这个名为"Quick sort Analysis.zip"的压缩包中,重点是分析快速排序的确定性与随机化实现。确定性快速排序通常是指每次选取固定的基准元素,如选择第一个或最后一个元素,这样对于相同的输入,排序过程完全可预测...

    PHP排序算法之快速排序(Quick Sort)及其优化算法详解

    快速排序(Quick Sort)是一种高效的排序算法,由C. A. R. Hoare在1960年提出。它采用分治法(Divide and Conquer)的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。快速排序在实现时,...

    快速排序C实现 quick sort

    数据结构,排序算法,快速排序算法的C语言实现, quick sort C qsort.c an c implementation of quick sort

    quick sort算法图解

    快速排序算法(Quick Sort)是一种高效的排序算法,由计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一个基准值(pivot)将数组分为两部分,其中一部分的...

    python编写 快速排序 Quick Sort

    python编写 快速排序 Quick Sort

    C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码

    各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码

    C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码。双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始...

    以 Quick Sort 算法将 ListBox 内容排序的范例(3k)

    快速排序(Quick Sort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用分治法(Divide and Conquer),将一个大问题分解为两个或多个相同或相似的子问题,直到最后子问题可以简单的直接求解...

    python 一行代码实现的快速排序 quick sort

    python 一行代码实现的快速排序 quick sort

    快速排序(Quick Sort)

    ### 快速排序(Quick Sort) #### 算法原理 快速排序是一种高效的排序算法,其基本思想是采用分治法(divide and conquer)来解决问题。对于待排序的数组A[0]...A[N-1],快速排序通过选择一个基准元素(pivot),通常...

    快速排序(Quick Sort)源码及运行示例

    快速排序(Quick Sort)源码及运行示例

    快速排序(Quick Sort)作者原版论文PDF

    快速排序(Quick Sort)作者原版论文,快速排序的作者C.A.R Hoare 发表的原著论文。

    算法分析与设计教学课件:Chapter 7 Quick Sort.pptx

    算法分析与设计教学课件:Chapter 7 Quick Sort.pptx

    Quick Sort (C++)

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)。在这个C++实现的快速排序中,我们将深入理解其原理、步骤以及如何用C++语言进行编码。...

    slides for merge and quick sort

    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); // 排序右半部分 ...

    基于python的排序算法-快速排序Quick Sort

    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. **时间复杂度与空间复杂度**: - **时间复杂度**...

Global site tag (gtag.js) - Google Analytics