快速排序

Reducto 發布于2019-08-14 15:11 / 839人閱讀

摘要：快速排序，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序以達到整個序列有序的目的。

概述

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(nlogn)次比較。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來，并且在大部分真實世界的數據，可以決定設計的選擇，減少所需時間的二次方項之可能性。

快速排序，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序,以達到整個序列有序的目的。

形象圖示：

步驟

選擇一個基準元素，通常選擇第一個元素或者最后一個元素

通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值均比基準值大

此時基準元素在其排好序后的正確位置

然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。

實例

原始數據：

3 5 2 6 2

選擇 3 作為基準

第一輪

從右往左找比3小的，2符合，將2和3對調
2 5 2 6 3
對調一次，查找的方向反向，從左向右找比3大的，5符合，對調
2 3 2 6 5
再從右往左找比3小的，2符合，對調
2 2 3 6 5
一輪結束

第二輪

對 [2 2] 采用同上的方式進行，得到
2 2 3 6 5

第三輪

對 [6 5] 采用同上的方式進行，得到
2 2 3 5 6

最終結果

2 2 3 5 6

代碼實現(Java)

package com.coder4j.main.arithmetic.sorting;

public class Quick {

    private static int mark = 0;

    /**
     * 輔助交換方法
     * 
     * @param array
     * @param a
     * @param b
     */
    private static void swap(int[] array, int a, int b) {
        if (a != b) {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
            // 找到符合的，對調
            System.out.println("對調" + array[a] + "與" + array[b] + ",得到");
            for (int i : array) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    /**
     * 新一輪分隔
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition(int array[], int low, int high) {
        int base = array[low];
        mark++;
        System.out.println("正在進行第" + mark + "輪分隔，區域：" + low + "-" + high);
        while (low < high) {
            while (low < high && array[high] >= base) {
                high--;
                System.out.println("從右往左找比" + base + "小的，指針變動：" + low + "-" + high);
            }
            swap(array, low, high);
            while (low < high && array[low] <= base) {
                low++;
                System.out.println("從左往右找比" + base + "大的，指針變動：" + low + "-" + high);
            }
            swap(array, low, high);
        }
        return low;
    }

    /**
     * 對數組進行快速排序，遞歸調用
     * 
     * @param array
     * @param low
     * @param heigh
     * @return
     */
    private static int[] quickSort(int[] array, int low, int high) {
        if (low < high) {
            int division = partition(array, low, high);
            quickSort(array, low, division - 1);
            quickSort(array, division + 1, high);
        }
        return array;
    }

    /**
     * 快排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return quickSort(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

測試輸出結果：

正在進行第1輪分隔，區域：0-4
對調2與3,得到
2 5 2 6 3 
從左往右找比3大的，指針變動：1-4
對調3與5,得到
2 3 2 6 5 
從右往左找比3小的，指針變動：1-3
從右往左找比3小的，指針變動：1-2
對調2與3,得到
2 2 3 6 5 
從左往右找比3大的，指針變動：2-2
正在進行第2輪分隔，區域：0-1
從右往左找比2小的，指針變動：0-0
正在進行第3輪分隔，區域：3-4
對調5與6,得到
2 2 3 5 6 
從左往右找比6大的，指針變動：4-4
最終結果
2 2 3 5 6

經測試，與實例中結果一致。

云服務器 GPU云服務器快速排序快速排序函數快速排序算法 php快速排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65414.html

快速排序就這么簡單

摘要：快速排序的介紹來源百度百科快速排序由在年提出。快速排序是面試出現的可能性比較高的，也是經常會用到的一種排序，應該重點掌握。前面一個章節已經講了遞歸了，那么現在來看快速排序就非常簡單了。快速排序就這么簡單從前面已經講解了冒泡排序、選擇排序、插入排序了，本章主要講解的是快速排序，希望大家看完能夠理解并手寫出快速排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。 ...

Faremax 2019-08-15 14:54 評論0 收藏0
算法之旅 | 快速排序法

摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...

AlanKeene 2019-08-22 11:11 評論0 收藏0
Javascript實現冒泡排序與快速排序以及對快速排序的性能優化

摘要：實現快速排序介紹通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。冒泡排序介紹重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后冒泡到數組的末端。假如數組...

dadong 2019-08-23 15:08 評論0 收藏0
怎樣測試程序的平均性能

標準庫中的sort函數，是快速排序算法的典型實現。算法將含有n個元素的序列排序，平均需要 O(n log n) 時間。上周，我提出了測試一個程序的性能比測試其功能更難這個觀點。確認程序的性能達到標準以及確定標準的含義都十分困難。接下來，我會繼續討論標準庫中的sort(排序)函數。sort函數實現了快速排序算法，快速排序算法平均可以在 O(n log n) 時間內對含有n個元素的序列進行排序...

mochixuan 2019-05-29 16:19 評論0 收藏0