快速排序的递归和非递归

2021-05-16 21:30

阅读：557

标签：快速排序地址 span 下标 pre i++ 算法过程 nbsp

快速排序，顾名思义，是一种速度快，效率高的排序算法。

快排原理：

在要排的数（比如数组A）中选择一个中心值key（比如A[0]），通过一趟排序将数组A分成两部分，其中以key为中心，key右边都比key大，key左边的都key小，然后对这两部分分别重复这个过程，直到整个有序。

整个快排的过程就简化为了一趟排序的过程，然后递归调用就行了。

一趟排序的方法：

　　1定义i=0，j=A.lenght-1，i为第一个数的下标，j为最后一个数下标

　　2从数组的最后一个数Aj从右往左找，找到第一小于key的数，记为Aj；

　　3从数组的第一个数Ai 从左往右找，找到第一个大于key的数，记为Ai；

　　4交换Ai 和Aj

　　5重复这个过程，直到 i=j

　　6调整key的位置，把A[i] 和key交换

假设要排的数组为：A[8] ={ 5 2 8 9 2 3 4 9 }：

选择 key = 5，开始时 i=0，j=7

index 0 1 2 3 4 5 6 7

开始： 5 2 8 9 2 3 4 9

i j

第一次找 5 2 8 9 2 3 4 9

i j

交换： 5 2 4 9 2 3 8 9

i j

第二次找 5 2 4 9 2 3 8 9

i j

交换： 5 2 4 3 2 9 8 9

i j

第三次找 5 2 4 3 2 9 8 9

调整key： 2 5 4 3 5 9 8 9

--------------------- 本文来自 Yexiaofen 的CSDN 博客，全文地址请点击：https://blog.csdn.net/Yexiaofen/article/details/78018204?utm_source=copy

递归：

 void quick_sort(int m[],int l,int r){
        int i=l,j=r;
        int x=m[i];
        if(lr){
            while (i//一次不行，进行多次
                while (i = x)//从右向左，找比x小的
                    j--;
                if (i  j) {
                    m[i] = m[j];
                    i++;
                }
                while (i //从左向右，找比x大的
                    i++;
                if (i  j) {
                    m[j] = m[i];
                    j--;
                }
                m[i] = x;
            }
            quick_sort(m,l,i-1);//递归调用
            quick_sort(m,i+1,r);
        }
    }

快速排序的递归和非递归

标签：快速排序地址 span 下标 pre i++ 算法过程 nbsp

原文地址：https://www.cnblogs.com/nickup/p/9748188.html

上一篇：JavaScript学习——JavaScript 条件语句 switch语句 while语句

下一篇：java多线程知识总结（四）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：快速排序的递归和非递归
文章链接：http://soscw.com/index.php/essay/86431.html

亲，登录后才可以留言！

快速排序的递归和非递归

评论

热门文章

推荐文章

最新文章

置顶文章