算法导论第七章:快速排序-全部代码实现

62 阅读 0 评论 41 点赞

我是靠谱客的博主腼腆猎豹，最近开发中收集的这篇文章主要介绍算法导论第七章:快速排序-全部代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

package 第七章_快速排序;

import java.math.BigInteger;

public class Main {
    static Boolean equal=true;
    public static void main(String[] args) {
        Main example = new Main();
        //图7-1例子
//        int[] A = {2, 8, 7, 1, 3, 5, 6, 4};
        //练习7.1-1例子
        int[] A = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};
        //练习7.1-2
        for (int j = 0; j < A.length; j++) { if (A[j]!=A[j+1]){ equal = false;break;} }
        example.TAL_RECURSIVE_QUICKSORT(A,0,A.length-1);
        for (int i : A) { System.out.print(i + " "); }
    }

    //一般快速排序
    public void QUICKSORT(int A[], int p, int r) {
        if (p < r) {
//            int q = PARTITION(A, p, r);
//            int q = RANDOMIZED_PARTITION(A, p, r);
            int q = HOARE_PARTITION(A, p, r);
            QUICKSORT(A, p, q - 1);
            QUICKSORT(A, q + 1, r);
        }
    }

    //尾递归快速排序
    public void TAL_RECURSIVE_QUICKSORT(int A[], int p, int r) {
        while (p < r) {
            int q = PARTITION(A, p, r);
            TAL_RECURSIVE_QUICKSORT(A, p, q - 1);
            p = q + 1;
        }
    }

    public void MODIFIED_TAIL_RECURSIVE_QUICKSORT(int A[], int p, int r){
        while (p < r) {
            int q = PARTITION(A, p, r);
            if (q < floor((p + r) / 2)) {
                MODIFIED_TAIL_RECURSIVE_QUICKSORT(A, p, q - 1);
                p = q + 1;
            } else{
                MODIFIED_TAIL_RECURSIVE_QUICKSORT(A, q + 1, r)
                r = q - 1;
            }
        }
    }

    //随机分块
    private int RANDOMIZED_PARTITION(int[] A, int p, int r) {
        int i = (int) (Math.random() * (r - p) + p + 1);
        int temp = A[i];
        A[i] = A[r];
        A[r] = temp;
        return PARTITION(A, p, r);
    }
    //HOARE式分块
    private int HOARE_PARTITION(int[] A, int p, int r) {
        int x = A[p];
        int i = p;
        int j = r+1;
        while (true) {
            while (i + 1 < A.length && A[++i] < x) ;
            while (A[--j] > x) ;
            if (i < j && j < A.length) {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            } else {
                A[p] = A[j];
                A[j] = x;
                return j;
            }
        }
    }

    //一般分块
    private int PARTITION(int[] A, int p, int r) {
        int curr = A[r];
        int i = p;
        int t = 0;
        for (int j = p; j < r; j++) {
//            if (A[j]=>curr){//非递增排序
            if (A[j] <= curr) {
                A[r] = A[i];
                A[i] = A[j];
                A[j] = A[r];
                i++;
//                记录值为curr的个数
//                if (A[j] == curr) t++;
            }
            //查看每次循环的结果
//            for (int k : A) {
//                System.out.print(k + " ");
//            }
//            System.out.println();
        }
        A[r] = A[i];
        A[i] = curr;
        //将值相等的元素放在一起
//        for (int k = 0; t!=0 ; k++) {
//            if (A[k] == curr) {
//                A[k] = A[i-(t--)];
//                A[i - (t + 1)] = curr;
//            }
//        }
        //查看每次排完的结果
//        for (int j : A) {
//            System.out.print(j + " ");
//        }
//        System.out.println();
        if (equal) return (p+r)/2;
        return i;
    }
}