快速排序

2021-07-11 06:04

阅读：800

标签：ret public 部分最好复杂 sort == ati 一个

基于交换的排序、不稳定的排序

对冒泡排序的改进

通过一趟排序，将待排关键字分为两部分，其中一部分的全部关键字都小于另一部分的全部关键字，然后分别对这两部分进行快速排序，可以选取第一个关键字为基准，将比它小的放在它之前，将比它大的放在它之后，完成这一趟之后，基准所在的位置就将初始序列分成两部分（一部分大、一部分小）

（1）选取序列的第一个关键字为基准base，附设两个指针low、high分别指向关键字序列的第一和最后一个元素

（2）从high位置往前，找到第一个小于base的数，交换

（3）从low位置往后，找到第一个大于base的数，交换

（4）重复（2）（3）直到low==high，完成了第一趟排序，将待排序列分成两部分

（5）分别对这两部分进行快速排序（递归）

    public static void quickSort(int[] array,int i,int j){
        //i和j记录本次快速排序的区间，由于下一次快速排序的区间需在本次区间的基础上确定，因此，i和j的值需要被记录
        int low = i;
        int high = j;
        int base = array[low];
        if(lowhigh){
            while(lowhigh){
                while(low=base){
                    high--;
                }
                if(lowhigh){
                    int temp = array[high];
                    array[high] = array[low];
                    array[low] = temp;
                }
                while(lowbase){
                    low++;
                }
                if(lowhigh){
                    int temp = array[high];
                    array[high] = array[low];
                    array[low] = temp;
                }
                    
            }
            listArray(array, i, j);
        }else{
            return;
        }

        quickSort(array, i, low-1);
        quickSort(array, high+1, j);
    }

注：其实交换是没有必要的，因为基准base最终在low==high那个位置上

    public static void quickSort(int[] array,int i,int j){
        //i和j记录本次快速排序的区间，由于下一次快速排序的区间需在本次区间的基础上确定，因此，i和j的值需要被记录
        int low = i;
        int high = j;
        int base = array[low];
        if(lowhigh){
            while(lowhigh){
                while(low=base){
                    high--;
                }
                if(lowhigh){
                    array[low] = array[high];
                }
                while(lowbase){
                    low++;
                }
                if(lowhigh){
                    array[high] = array[low];
                }
                    
            }
            array[low] = base;
            listArray(array, i, j);
        }else{
            return;
        }

        quickSort(array, i, low-1);
        quickSort(array, high+1, j);
    }

时间复杂度

最好平均O(nlogn) 最坏O(n^2)

快速排序

标签：ret public 部分最好复杂 sort == ati 一个

原文地址：https://www.cnblogs.com/duanjiapingjy/p/9553063.html

上一篇：python接口自动化测试一：http协议

下一篇：四种JavaEE架构简介

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

亲，登录后才可以留言！

快速排序

评论

热门文章

推荐文章

最新文章

置顶文章