快速排序

快排思路

基于冒泡排序,通过比较和交换。

  1. 首先设定一个分界值,将小于等于分界值的放在左边,将大于分界值的放在右边;

  2. 然后左边和右边的数据可以单独进行排序,也按照上述思路分为左右两部分;

  3. 重复上述过程,这是一个递归排序。

时间复杂度:O(nLog2n) 最好情况:O(nLog2n) 最坏情况:O(n^2)

空间复杂度:O(1)

稳定性:不稳定

复杂性:较复杂

Java实现

package com.wangjun.arithmetic;

import java.util.Arrays;

/*
 * 快速排序
 */
public class SortQuick {

    public static void main(String[] args) {
        int[] arr = {2,3,7,5,43,8,9,0,3,1};
        SortQuick ss = new SortQuick();
        ss.sortQuick(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sortQuick(int[] arr) {
        sortHelper(arr, 0, arr.length - 1);
    }

    public void sortHelper(int[] arr, int start, int end) {
        int left = start;
        int right = end;
        int middle = arr[(left+right)/2];
        while(left < right) {
            /*
             * ? left不会越界么
             * 不会,因为它最多走到middle的位置,就相等了,不满足while条件;
             * 就算left和right都与middle相等然后交换了,剩下的交给递归去做
             */
            while(middle > arr[left]) {
                left++;
            }
            while(middle < arr[right]) {
                right--;
            }
            if(left < right) {
                int tem = arr[left];
                arr[left] = arr[right];
                arr[right] = tem;
                left++;
                right--;
            }
        }
        /*
         * ? 为啥要有这一步,为了完全隔开左右两边
         * 考虑到这种情况 7 5 3 排好序后是 3 5 7 这时left=right=1
         * 如果不让left++,那么左边和右边递归排序就重复了 5 这个值
         * 由于是同步的,右边先排好后,中间这个值可能已经不是5了
         * 还可能导致迭代死循环
         */
        if(left == right) {
            if(arr[left] > middle) { //处理边界值,保证左边都是小于等于middle的值,右边都是大于等于middle的值
                right--;
            }else {
                left++;
            }
        }
        if(left < end) {
            sortHelper(arr,left,end);
        }
        if(right > start) {
            sortHelper(arr, start, right);
        }
    }
}

写快排的时候可以分2步:

  1. 写一个算法实现:取一个值,将小于它的放在左边,大于它的放在右边;

  2. 将左右部分分别递归调用,注意下处理边界值就行了;

Last updated