图解快速排序(使用递归算法)

2025-10-19 20:09:24

1、初始状态,设置基准值,将数组中的第一个值作为基准值,即数字6。

图解快速排序(使用递归算法)

2、第一次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。

图解快速排序(使用递归算法)

3、将两者数值交换。

图解快速排序(使用递归算法)

4、第二次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。

图解快速排序(使用递归算法)

5、两者数值交换。

图解快速排序(使用递归算法)

6、第三次循环,j找到小于6的值后,停止寻找,i找到大于6的值后,停止寻找。

图解快速排序(使用递归算法)

7、当j找到小于6的值后,停止寻找,i开始循环,寻找大于6的值,当i=j时,结束循环。

将i的值与基准值交换。

图解快速排序(使用递归算法)

8、此时,在基准值6的左侧均为小于6的值,右侧为大于6的值。

再使用递归算法,将左右两边数组进行排序。

1、代码段(使用js语言)。

function quickSort(num,from,to){

            var from = from != undefined ? from : 0;  //开始位置

            var to = to != undefined ? to : num.length-1; //结束位置

            var i = from;  

            var j = to;

            var key = num[from]; //基准值

            var temp;  // 临时变量,用于数字交换

            if(i>=j){

                return num;  //递归出口

            }

            while(i<j){    // 外层循环,当i=j时,循环结束,完成一轮的数字交换

                //j的目标是寻找比基准值小的值,

                //故当num[j]的值大于基准值时,需要往左移动,即j--,

                ////直到找到小于基准值的情况下退出循环,并记录下此时的j值。

                while(i<j && num[j]>key){   

                    j--;

                }

                //i的目标是寻找比基准值大的值,

                //故当num[j]的值小于基准值时,需要往右移动,即i++,

                //直到找到大于基准值的情况下退出循环,并记录下此时的i值。

                while(i<j && num[i]<=key){

                    i++;

                }

                //将i与j的值交换

                if(i<j){

                     temp = num[i];

                     num[i] = num[j];

                     num[j] = temp;

                }

            }

            //最后将i与基准值交换,完成第一轮的数字查找

            num[from] = num[i];

            num[i] = key; 

            //使用递归算法,对数组下标从from~i-1的部分,

            //即小于基准值的左边部分进行排序。

            quickSortTwo(num,from,i-1);

            //使用递归算法,对数组下标从i+1~to的部分,

            //即小于基准值的右边部分进行排序。

            return quickSortTwo(num,i+1,to);

        }

          //调用函数

          console.log(quickSort(arr));

为了方便,截图如下。

图解快速排序(使用递归算法)

2、注意点:

1、to = to != undefined ? to : num.length-1; 函数开始时需要有一个判断值是否为undefined的语句,不能直接写 to = to ? to: num.length-1,因为在函数执行的过程中,到递归语句时,可能会传入0,如果传入0,会将to赋值为num.length-1,导致函数运行不正确。

2、while(i<j && num[j]>key),该代码容易产生误解,容易写成num[j]<key,然后左移j--。

3、return quickSortTwo(num,i+1,to);写代码时容易漏掉最后的return,如果没有return,函数返回undefined。

声明:本网站引用、摘录或转载内容仅供网站访问者交流或参考,不代表本站立场,如存在版权或非法内容,请联系站长删除,联系邮箱:site.kefu@qq.com。
猜你喜欢