PHP快速排序(原地切分)

Wesley13
• 阅读 428

        快速排序是一种分治的排序算法,采用递归的思想,将数组元素分为两部分,选择切分元素,左右扫描数组,将大于切分元素的数据放在右边,小于切分元素的数据放在左边,直到扫描指针相遇,切分结束,同时递归调用,直到数组有序。

        代码如下:

<?php
function quick_sort(array& $array,$low,$high){
    if($low >= $high){
        return $array;//递归出口,数组的最高位下标小于数组最低位下标
    }
    $i = $low;
    $j = $high+1;    //数组切分循环
    $v = $array[$low];//切分元素
    while(true){//循环查找
        while($array[--$j] >= $v)if($j == $low)break;//从右往左查找第一个比$v小的元素
        while($array[++$i] <= $v)if($i == $high)break;//从左往右查找第一个比$v大的元素
        if($i >= $j)break;//指针相遇
        $tmp = $array[$j];
        $array[$j] = $array[$i];
        $array[$i] = $tmp;    //元素位置交换
    }
    $array[$low] = $array[$j];
    $array[$j]= $v;//将切分元素放入相应位置
    
    quick_sort($array,$low,$j-1);
    quick_sort($array,$j+1,$high); //递归调用

}

$array = array('1','3','2','5','6','5');
$high = count($array);
quick_sort($array,0,$high-1);
var_dump($array);
?>

同时也可以用shuffle()函数对数组进行打乱,以便消除对输入的依赖~

点赞
收藏
评论区
推荐文章
排序算法(简单选择、堆排序、归并)
简单选择排序:::tip简单选择排序原理:将未排序的数组中从前向后遍历,找到最小的元素和数组中第一个元素交换位置,此时数组中第一个元素位置已经确定,再将未排序的数组中从前向后遍历,找到最小的元素和数组中第二个元素交换位置,依次向下。:::需要两层循环,外层
Stella981 Stella981
2年前
C语言 快速排序 Quick Sort
算法描述:快速排序一般是选择数组的第一个数据为对称轴参考值pivot。按照大小数组分割成左右两个区间。然后对左右两个区间再进行递归排序,知道结束为止。例子演示:数组:43251,长度:5,对称轴参考值选择第一个数据4。比它小的我们放到它的右边,比它大的我们放到左边。设置左右两个工作位置。指向开头和末尾。第一轮:4325
Wesley13 Wesley13
2年前
MySQL_分库分表
分库分表数据切分  通过某种特定的条件,将我们存放在同一个数据库中的数据分散存放到多个数据库(主机)上面,以达到分散单台设备负载的效果。数据的切分同时还能够提高系统的总体可用性,由于单台设备Crash之后,仅仅有总体数据的某一部分不可用,而不是全部的数据。切分模式  数据的切分(Sharding)依据其切分规则的类
Stella981 Stella981
2年前
Quick Sort(三向切分的快速排序)(Java)
1//三向切分的快速排序2//这种切分方法对于数组中有大量重复元素的情况有比较大的性能提升34publicstaticvoidmain(Stringargs)5{6ScannerinputnewScanner(System.in);7
菜园前端 菜园前端
9个月前
什么是快速排序?
原文链接:什么是快速排序(quickSort)?主要分成两部分实现,分区、递归操作。分区从数组中任意选择一个"基准",所有比基准小的元素放在基准前面,比基准大的元素放在基本后面。递归递归地对基准前后的子数组进行分区。算法步骤1.首先获取数组的第一个值(作为
菜园前端 菜园前端
9个月前
什么是二分搜索?
原文链接:什么是二分搜索?二分搜索是一种比较高效的搜索算法,但前提必须是有序数组。主要步骤如下:1.从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束2.如果目标值大于或者小于中间元素,则在大于或者小于中间元素的那一半数组中继续二分搜索基础案例时间
京东云开发者 京东云开发者
4个月前
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数
菜园前端 菜园前端
9个月前
什么是选择排序?
原文链接:什么是选择排序(selectSort)?选择排序就是在一个排列中划分为有序区和无序区,有序区在左边,无序区在右边。首先在无序区中找到最小元素,存放到有序区的起始位置,然后再从剩余的无序区中继续寻找最小元素,然后放到有序区的末尾。以此类推,直到无序
菜园前端 菜园前端
9个月前
什么是插入排序?
原文链接:什么是插入排序(insertionSort)?在数组中从左到右依次取一个数出来,然后把它放到合适的位置。从思想上可以分为有序区和无序区,有序区在左边代表已经排列好的元素。算法步骤1.默认左边第一个元素已经在有序区了2.在无序区取一个数出来(第二个
菜园前端 菜园前端
9个月前
什么是归并排序?
原文链接:什么是归并排序(mergeSort)?主要分成两部分实现,分、合操作:分:把数组分成两半,在递归地对子数组进行"分"操作,直到分成一个个单独的数合:把两个数组合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组归并排序就是采用了