快速排序

frank_fun 发布于2019-06-27 15:38 / 2120人阅读

摘要：快速排序定义一个基准数，用于做参照。此轮一直与的位置相遇，当两者相遇的时候，则将相遇位置的数与基准数进行互换。左侧数组为右侧数组为左侧数组用上述方法进行排列，变成。利用递归，将的数组参数左侧进行判断归位，右侧进行判断归位，最终返回结果。

快速排序

定义一个基准数，用于做参照。

定义左右两侧的起始数和终止数，一般是以数组起始值0，以及数组长度-1为开始

数组【0】开始，与基准数X进行判断，如果比X大，则停止，保留数组【0】；比X小，则数组【0】变成数组【1】（即向右移动一位），再与基准数X判断，如此循环，到符合前面条件停止。

数组【长度-1】开始，与基准数X进行判断，如果比X小，则停止，保留数组【长度-1】；
比X大，则数组【长度-1】变成数组【长度-2】（即向左移动一位），再与基准数X判断，如此循环，到符合前面条件停止。

例如：

现在有数组$arr = [12, 6, 5, 35, 64, 78, 11, 85, 43,46];

我们取$arr[0]=12为基准数$temp。（这边如果设置基准数是最左边的，则让右侧先开始判断值，如果基准数设置是最右边的数，则让左侧开始先判断）

定义变量$i=0; $j=9(数组长度-1);

然后从$arr[$j]先开始进行判断，如果不符合条件则$j--; $j会在$arr[6]=11位置停下。

$arr[$i]开始进行判断，如果不符合条件则$i--; $i会在$arr[3]=35位置停下。

$arr[3]与$arr[6]互换。

更换完，数组是$arr = [12, 6, 5, 11, 64, 78, 35, 85, 43,46];

更换完以后，右侧的$j继续先判断,从$j=6开始往左走,此时$i=3。

$j此轮一直与$i=3的位置相遇，当两者相遇的时候，则将相遇位置($i=$j)的数与基准数$temp=12进行互换。

更换完，数组是$arr = [11, 6, 5, 12, 64, 78, 35, 85, 43,46];

此时，基于$arr[3]这个位置，将数组拆分为左右两次数组，进行相同的方式判断（这里会用到递归的方法）。

左侧数组为 $left_arr=[11,6,5]; 右侧数组为 $right_arr=[64,78,35,85,43,46];

左侧数组用上述方法进行排列，变成 $left_arr=[5,6,11];。

右侧数组用上述方法进行排列，首先变成$right_arr=[43,46,35,64,85,78];

这时，左侧已经不需要排列了，因为$temp=11基准数归位后，右侧没有数组，左侧5<6

右侧还要进行排列,$temp=64基准数归位后，左边数组为[43,46,35]，右边数组[85,78]。

最终右侧会变成$right_arr=[35,43,46,64,78,85];

最终数组$arr=[5,6,11,12,35,43,46,64,78,85];

代码：

= $right) {
        return;
    }
    
    //设置基准数，作为比较用的参数
    $temp = $arr[$left];

    //$i是左边起的起始数值，$j是右边起的起始数值
    $i = $left;
    $j = $right;

    //只要两个参数不相等，即两者不是指向同一个数组内参数 则继续循环
    while ($i != $j) {

        //从数组右侧开始，判断是否比基准数小并且($j>$i)确保从右往左且还未与$i相遇
        while ($arr[$j] >= $temp && $j > $i) {
            $j--;
        }

        //从数组左侧开始，判断是否比基准数大并且($j>$i)确保从左往右且还未与$j相遇
        while ($arr[$i] <= $temp && $i < $j) {
            $i++;
        }


        /**上述两个判断条件停止时，$i,$j都会指向数组内的某个数$arr[$i]，$arr[$j]
         *并且$arr[$i]是比基准数大的，$arr[$j]是比基准数小的
         *两者的值进行互换
         */
        if ($i < $j) {
            $t = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $t;
        }
    }
    
    
    //当$i,$j两个参数相等时候，则跳出循环，并且将基准数与数组中（当$j=$i的）$arr[$i]内的值进行互换。
    $arr[$left] = $arr[$i];
    $arr[$i] = $temp;
    
    
    //利用递归，将$i=$j的数组参数左侧进行判断归位，右侧进行判断归位，最终返回结果。
    quickSort($left, $i - 1);
    quickSort($i + 1, $right);
    
    return;

}

quickSort(0, count($arr) - 1);

//输出结果
print_r($arr);

GPU云服务器云服务器快速排序快速排序函数快速排序算法 php快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22463.html

快速排序就这么简单

摘要：快速排序的介绍来源百度百科快速排序由在年提出。快速排序是面试出现的可能性比较高的，也是经常会用到的一种排序，应该重点掌握。前面一个章节已经讲了递归了，那么现在来看快速排序就非常简单了。快速排序就这么简单从前面已经讲解了冒泡排序、选择排序、插入排序了，本章主要讲解的是快速排序，希望大家看完能够理解并手写出快速排序的代码，然后就通过面试了！如果我写得有错误的地方也请大家在评论下指出。 ...

Faremax 2019-08-15 14:54 评论0 收藏0
算法之旅 | 快速排序法

摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。 HTML5学堂-码匠：前几期算法之旅跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的慢排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法—— 快速排序法 [ 平均时间复杂度为O (n l...

AlanKeene 2019-08-22 11:11 评论0 收藏0
Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

摘要：实现快速排序介绍通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。冒泡排序介绍重复遍历要排序的元素列，依次比较两个相邻的元素，前一个元素若比后一个元素大则互换位置。以升序排序为例，最大的元素会在第一次遍历后冒泡到数组的末端。假如数组...

dadong 2019-08-23 15:08 评论0 收藏0
怎样测试程序的平均性能

标准库中的sort函数，是快速排序算法的典型实现。算法将含有n个元素的序列排序，平均需要 O(n log n) 时间。上周，我提出了测试一个程序的性能比测试其功能更难这个观点。确认程序的性能达到标准以及确定标准的含义都十分困难。接下来，我会继续讨论标准库中的sort(排序)函数。sort函数实现了快速排序算法，快速排序算法平均可以在 O(n log n) 时间内对含有n个元素的序列进行排序...

mochixuan 2019-05-29 16:19 评论0 收藏0