快速排序和双轴快排

古城微笑少年丶 2024-04-17 21:59 83阅读 0赞

快速排序

/**
     * @Description 快速排序
     * @Author calvin
     * @Date 2019/9/1 20:59
     **/
    public class QuickSort {
        public static void main(String[] args) {
            int[] arr = {7, 3, 2, 10,8, 1, 9, 5, 4, 6 };
            sort(arr, 0, arr.length - 1);
            print(arr);
        }
    
         static void sort(int[] arr, int leftBound, int rightBound) {
            if (leftBound >= rightBound) return;
            int mid = partition(arr, leftBound, rightBound);
           // System.out.println("--" + mid);
            sort(arr, leftBound, mid - 1);
            sort(arr, mid + 1, rightBound);
        }
    
        private static int partition(int[] arr, int leftBound, int rightBound) {
            int pivot = arr[rightBound];
            int left = leftBound;
            int right = rightBound - 1;
            while (left < right) {
                while (left <= right && arr[left] <= pivot) left++;
                while (left <= right && arr[right] > pivot) right--;
                if (left < right) swap(arr, left, right);
            }
            if (arr[left]>arr[rightBound])
             swap(arr, left, rightBound);
            return left;
        }
    
        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        private static void print(int[] arr) {
            for (int anArr : arr) {
                System.out.print(anArr + " ");
            }
        }
    }

jdk工业快速排序 （可以试着读一下）

/*
         * Sorting methods. Note that all public "sort" methods take the
         * same form: Performing argument checks if necessary, and then
         * expanding arguments into those required for the internal
         * implementation methods residing in other package-private
         * classes (except for legacyMergeSort, included in this class).
         */
    
        /**
         * Sorts the specified array into ascending numerical order.
         *
         * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
         * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
         * offers O(n log(n)) performance on many data sets that cause other
         * quicksorts to degrade to quadratic performance, and is typically
         * faster than traditional (one-pivot) Quicksort implementations.
         *
         * @param a the array to be sorted
         */
        public static void sort(int[] a) {
            DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
        }
    
    
    
    
    
    
     /*
         * Sorting methods for seven primitive types.
         */
    
        /**
         * Sorts the specified range of the array using the given
         * workspace array slice if possible for merging
         *
         * @param a the array to be sorted
         * @param left the index of the first element, inclusive, to be sorted
         * @param right the index of the last element, inclusive, to be sorted
         * @param work a workspace array (slice)
         * @param workBase origin of usable space in work array
         * @param workLen usable size of work array
         */
        static void sort(int[] a, int left, int right,
                         int[] work, int workBase, int workLen) {
            // Use Quicksort on small arrays
            if (right - left < QUICKSORT_THRESHOLD) {
                sort(a, left, right, true);
                return;
            }
    
            /*
             * Index run[i] is the start of i-th run
             * (ascending or descending sequence).
             */
            int[] run = new int[MAX_RUN_COUNT + 1];
            int count = 0; run[0] = left;
    
            // Check if the array is nearly sorted
            for (int k = left; k < right; run[count] = k) {
                if (a[k] < a[k + 1]) { // ascending
                    while (++k <= right && a[k - 1] <= a[k]);
                } else if (a[k] > a[k + 1]) { // descending
                    while (++k <= right && a[k - 1] >= a[k]);
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                } else { // equal
                    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                        if (--m == 0) {
                            sort(a, left, right, true);
                            return;
                        }
                    }
                }
    
                /*
                 * The array is not highly structured,
                 * use Quicksort instead of merge sort.
                 */
                if (++count == MAX_RUN_COUNT) {
                    sort(a, left, right, true);
                    return;
                }
            }
    
            // Check special cases
            // Implementation note: variable "right" is increased by 1.
            if (run[count] == right++) { // The last run contains one element
                run[++count] = right;
            } else if (count == 1) { // The array is already sorted
                return;
            }
    
            // Determine alternation base for merge
            byte odd = 0;
            for (int n = 1; (n <<= 1) < count; odd ^= 1);
    
            // Use or create temporary array b for merging
            int[] b;                 // temp array; alternates with a
            int ao, bo;              // array offsets from 'left'
            int blen = right - left; // space needed for b
            if (work == null || workLen < blen || workBase + blen > work.length) {
                work = new int[blen];
                workBase = 0;
            }
            if (odd == 0) {
                System.arraycopy(a, left, work, workBase, blen);
                b = a;
                bo = 0;
                a = work;
                ao = workBase - left;
            } else {
                b = work;
                ao = 0;
                bo = workBase - left;
            }
    
            // Merging
            for (int last; count > 1; count = last) {
                for (int k = (last = 0) + 2; k <= count; k += 2) {
                    int hi = run[k], mi = run[k - 1];
                    for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                        if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                            b[i + bo] = a[p++ + ao];
                        } else {
                            b[i + bo] = a[q++ + ao];
                        }
                    }
                    run[++last] = hi;
                }
                if ((count & 1) != 0) {
                    for (int i = right, lo = run[count - 1]; --i >= lo;
                        b[i + bo] = a[i + ao]
                    );
                    run[++last] = right;
                }
                int[] t = a; a = b; b = t;
                int o = ao; ao = bo; bo = o;
            }
        }

这个排序中对于不同大小的数据，做了不同的处理，以及很多基础算法的应用以及优化后的算法应用（双插入排序[https://blog.csdn.net/qq\_28656707/article/details/100182093][https_blog.csdn.net_qq_28656707_article_details_100182093]）荷兰国旗算法等等。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70][]

[https_blog.csdn.net_qq_28656707_article_details_100182093]: https://blog.csdn.net/qq_28656707/article/details/100182093
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/96852300a8724a8a9686b8be5de08727.png