Java实现快速排序

发布于 2021-08-01  35 次阅读


注意parytition方法中的两种循环,一种是替换一种是交换,

替换比交换效率好

package com.apesblog.sort.quick;

import javax.xml.crypto.Data;

public class Quick {
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int pivot;
        pivot = parytition(a, lo, hi);
        sort(a, lo, pivot - 1);
        sort(a, pivot + 1, hi);

    }

    private static int parytition(Comparable[] a, int lo, int hi) {
        Comparable key = a[lo];
//        替换
        while (lo < hi) {
            while (lo < hi && greater(a[hi], key)) {
                hi--;
            }
            a[lo] = a[hi];
            while (lo < hi && !greater(a[lo], key)) {
                lo++;
            }
            a[hi] = a[lo];
        }
        a[lo] = key;

//        交换
//        while (lo < hi) {
//            while (lo < hi && greater(a[hi], key)) {
//                hi--;
//            }
//            exch(a, lo, hi);
//            while (lo < hi && !greater(a[lo], key)) {
//                lo++;
//            }
//            exch(a, lo, hi);
//        }

        return lo;
    }

    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
package com.apesblog.sort.quick;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        Integer[] a = { 5, 1, 2, 4, 3, 6 };
        Quick.sort(a);
        System.out.println("快速排序:" + Arrays.toString(a));

        String[] str = { "d", "e", "f", "c", "b", "a" };
        Quick.sort(str);
        System.out.println("快速排序:" + Arrays.toString(str));

    }

}