章节四:快速排序

快速排序通常是用于排序的最佳实用选择,虽然最坏情况下时间性能为O(n*n),但其平均时间性能为O(nlgn)且记号中隐含的常数因子很小,且为原地排序。

快速排序也是一种分治模式,其基本思想如下:找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区(Partition,核心部分)操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置;然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

//Partition PHP实现 

function Partition(&$array,$p,$r){

    $key=$array[$p];

    $i=$p;   $j=$r;

    while($i<$j){

    while($i<$j&&$array[$j]>$key){$j--;}

    if($i<$j){$array[$i]=$array[$j]; i++;}

    while($i<$j&&$array[$i]<$key){$i++;}

    if($i<$j){$array[$j]=$array[$i];  $j--;}

    }

   $array[$i]=$key;

return $i;

}

//快速排序  PHP实现

function Quick_sort(&$array,$p,$r){

    if($p<$r){

        $pivot=Partition($array,$p,$r);

        Quick_sort($array,$p,$pivot-1);

        Quick_sort($array,$pivot+1,$r);

    }

}

快速排序的运行时间与划分是否对称有关,而后者又与选择了哪个元素进行划分有关;如果划分是对称的,那么本算法从渐近意义上和合并排序一样快,如果划分不对称,本算法从渐近意义和插入排序一样慢。

//快速排序的随机化版本

Random_Partition(&$array,$p,$r){

    $i=rand($p,$r);

    swap($array[$i],$array[p]);

    return Partition($array,$p,$r);

}

2. 荷兰国旗问题和三路快速排序

问题描述:荷兰国旗有红、白、蓝三种颜色。现有这三种颜色的小球混放在一起,要求对小球排序,使得相同颜色的小球相邻摆放。问题模型化:假设用数字0,1,2代表红、白、蓝三种颜色。数组array混乱存放着这些代表球的颜色的元素值。

//荷兰国旗 PHP实现

function Threeflag(&$array,$p,$r){

    $beg=$p; $end=$r; $curr=$p;

    while($curr<=$end){

        if($array[$curr]==0){

            swap($array[$beg],$array[$curr]);

            $curr++;  $beg++;

        }elseif($array[$curr]==2){

            swap($array[$end],$array[$curr]);

            $end--;

        }elseif($array[$curr]==1){

            $curr++;

        }

    }

}

快速排序算法扩展之三路快速排序算法:

随机快排虽然能很大程度上解决子问题划分不均的情况,但当排序对象中有很多重复的元素时,快排划分情况很不尽人意。例如:当所有元素都相等时,在每次递归中,左边部分是空的(没有元素比关键元素小),而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。为了解决这个问题(有时叫做荷兰国旗问题),我们将快排划分扩展为三路快排:即排序对象被划分为三部分:<$privot,=$privot,>$privot

//三路快速排序 PHP实现

function quick_sort(&$array,$p,$r){

    if ($p<$r) {

        $pivot=ThreePartition($array,$p,$r);

        quick_sort($array,$p,$pivot[0]);

        quick_sort($array,$pivot[1]+1,$r);

        // $pivot=Partition($array,$p,$r);

        // quick_sort($array,$p,$pivot-1);

        // quick_sort($array,$pivot+1,$r);

    }

}

//three partition

function ThreePartition(&$array,$p,$r){

    $key=$array[$p];

    $i=$p;  $j=$r; $k=$p;

    while ($k<=$j) {

        if ($array[$k]<$key) {

            swap($array[$i],$array[$k]);

            $i++;$k++;

        }elseif ($array[$k]>$key) {

            swap($array[$j],$array[$k]);

            $j--;

        }elseif ($array[$k]==$key) {

            $k++;

        }

    }

return array($i,$j);

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,790评论 0 33
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,238评论 0 52
  • quicksort可以说是应用最广泛的排序算法之一,它的基本思想是分治法,选择一个pivot(中轴点),将小于pi...
    黎景阳阅读 480评论 0 1
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,754评论 0 15
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,290评论 0 2