算法研究之快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
以上摘自百度百科.
最坏时间复杂度:
O(n二次方);
最好时间复杂度:
O(n);
快速排序的基本思想
1.分解:
在D[i...j...n]的数据中,找一个基准点D[j],将数据划分成左右两份,
左等于D[i...j-1]
右等于D[j+1...n]
2.求解
递归调用划分函数 对左右区间两个数据划分求解.
3.合并左右两个排序好的数据
可见快速排序算法时间复杂度等于划分所花费的时间.
下面详细说一说关键的第二部 求解
划分步骤
数据 D[low...high];
① 设两个变量 i,j,分别指向数据的low 和high.取其中任意一个数据为基准pivot.
② 从右向左移动j,查找比pivot小的数据,找到后将j所指向的数据赋给i,D[i]=D[j]
从左向右移动i,查找比pivot大的数据,找到后将i所指向的数据赋给j.D[j]=D[i];
以此类推不断交换方向,知道i=j的时候停止.这个时候i的位置就是基准pivot所在的位置.
下面通过数据走一遍这个流程
引文用文字不好描述..所以我在本子上用笔画出来..
本人写字不好看..勿喷..^.^
PHP写的代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
functionquick_sort(&$array,$x,$y) {
$i=$x;
$j=$y;
$key=$array[$x];//基准
while($i!=$j) {
//$j-- 查找比基准$key小的值
while($i<$j&&$array[$j] >=$key) {
$j--;
}
// if($i < $j)
$array[$i] =$array[$j];
//$i++查找比基准$key大的值
while($i<$j&&$array[$i] <=$key) {
$i++;
}
// if($i < $j)
$array[$j] =$array[$i];
}
$array[$i] =$key;
if($x<$i-1) //左区间的数据
quick_sort($array,$x,$i-1);
if($y>$i+1)//右区间的数据
quick_sort($array,$i+1,$y);
}
|
