首页 / 算法 / 快排的非递归算法和最大子串乘积

快排的非递归算法和最大子串乘积

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快排的非递归算法和最大子串乘积，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1355字，纯文字阅读大概需要2分钟。

内容图文

         快排的原理是，让一个数作为中间值A，使得左边的数都小于(大于)等于A，右边的数都大于(小于)A。

         

            1
            public
            static
            void quickSort(Integer[] arrayList,int begin,int end){
2if(begin>=end)
3return;
4int par=paration3(arrayList, begin, end);
5if(begin<par-1)
6             quickSort(arrayList, begin, par-1);
7if (par<end) 
8             quickSort(arrayList, par+1, end);
9     }
            public
            static
            int paration(Integer[] arrayList,int begin,int end){
        int temp=arrayList[begin];
        while (begin<end) {
            while (begin<end&&arrayList[end]>temp) {
                end--;
            }
            if (begin<end) {
                arrayList[begin]=arrayList[end];
                begin++;
            }
            while (begin<end&&arrayList[begin]<temp) {
                begin++;
            }
            if (begin<end) {
                arrayList[end]=arrayList[begin];
                end--;
            }
        }
        arrayList[begin]=temp;
        return begin;
    }

       一般来说，递归算法都可以用非递归来实现，添加一个栈， 保存相关信息即可。快速排序的非递归算法亦是如此，每次保存下下次需要排序的。

     

            public
            static
            void quickSort2(Integer[] arrayList,int begin,int end){
        int par=paration3(arrayList, begin, end);
        Stack<Integer> stack=new Stack<Integer>();
        if(begin>par-1){
            stack.push(begin);
            stack.push(par-1);
        }
        if(par+1<end){
            stack.push(par+1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end=stack.pop();
            begin=stack.pop();
            par=paration3(arrayList, begin, end);
            if(begin<par-1){
                stack.push(begin);
                stack.push(par-1);
            }
            if(par+1<end){
                stack.push(par+1);
                stack.push(end);
            }
        }
    }

          

原文：http://www.cnblogs.com/xiaoyi115/p/3992735.html

内容总结

以上是互联网集市为您收集整理的快排的非递归算法和最大子串乘积全部内容，希望文章能够帮你解决快排的非递归算法和最大子串乘积所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1049685.html

来源：【匿名】