算法研究之快速排序

页面导航:首页 > 网络编程 > PHP编程 > 算法研究之快速排序

算法研究之快速排序

来源: 作者: 时间:2016-01-16 10:37 【

快速排序(Quicksort)是对冒泡排序的一种改进。由C A R Hoare在1962年提出。

快速排序(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所在的位置.

下面通过数据走一遍这个流程
引文用文字不好描述..所以我在本子上用笔画出来..
本人写字不好看..勿喷..^.^


写的代码

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);
}

Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<