快速排序 QuickSort

名字是乱打的

发布于 2022-05-13 10:12:31

2040

发布于 2022-05-13 10:12:31

文章被收录于专栏：软件工程

它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中左部分数据小于这个基准数,右边部分数据都大于这个基准数,也就是右部分大于左部分。然后，再按此方法对这两部分数据分别进行排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 简单讲每次一个小排序都会选出等于区,然后排小于区和大于区

快排分两种

经典快排比较基准为数组最后一个数
随机快排比较基准为数组内随机一个数

快排时间复杂度O(N*logN) 额外空间复杂度O(logN)

快排额外空间复杂度来自存储等于区域的数组

一经典快排

package com.day1.sort;

import com.day1.comparator.ArrayComparator;


public class QuickSort extends ArrayComparator {

    public static void quickSort(int[] arr,int L,int R){ //在L到R上排序
        if(L<R){
            int[] ints = partition(arr, L, R);
            quickSort(arr,L,ints[0]-1);
            quickSort(arr,ints[1]+1,R);
        }
    }
    //以最后一个位置上的数做划分
    //将小于最后一个数的放左边,大于最后一个数的放右边,等于的放中间
    //返回排序后等于最后一个数的的左索引和右索引
    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;  //小于arr[R]的最后一个索引
        int more = R; //大于arr[R]的第一个索引
        int curr=L;
        while (curr < more) {
            if (arr[curr] < arr[R]) {
                swap(arr, ++less, curr++);
            } else if (arr[curr] >arr[R]) {
                swap(arr, --more, curr);
            } else {
                curr++;
            }
        }
        swap(arr,R,curr);
        return new int[] { less + 1, more};
    }
}

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。

为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

由此可见经典快排会随着我们数据的情况不同时间复杂度不同,这就造成了可能出现极端情况

二随机快排

跟经典快排不同的情况是我们的比较基准不是最后一个数,而是随机选一个数字.

与经典排序相比只多了一行代码`

          swap(arr, L + (int) (Math.random() * (R - L + 1)), R);

在L~R数组里随机取一个数放到最后作为比较基准

全文代码

package com.day1.sort;

import com.day1.comparator.ArrayComparator;


public class QuickSort extends ArrayComparator {

    public static void quickSort(int[] arr,int L,int R){ //在L到R上排序
        if (L<R){
            //在L~R数组里随机取一个数放到最后作为比较基准
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] ints = partition(arr, L, R);
            quickSort(arr,L,ints[0]-1);
            quickSort(arr,ints[1]+1,R);
        }
    }


    //以最后一个位置上的数做划分
    //将小于最后一个数的放左边,大于最后一个数的放右边,等于的放中间
    //返回排序后等于最后一个数的的左索引和右索引
    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;  //小于arr[R]的最后一个索引
        int more = R; //大于arr[R]的第一个索引
        int curr=L;
        while (curr < more) {
            if (arr[curr] < arr[R]) {
                swap(arr, ++less, curr++);
            } else if (arr[curr] >arr[R]) {
                swap(arr, --more, curr);
            } else {
                curr++;
            }
        }
        swap(arr,R,curr);
        return new int[] { less + 1, more};
    }
}

对partition()函数有疑问可以查看荷兰国旗问题

点击: 荷兰国旗问题

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树