面試三 ： 快速排序

    今天我們看看快速排序，其實我們是在大二上學期上的資料結構，現在基本上忘的差不多了，最近這兩年一直在做應用，是以這個面試官給我敲響了警鐘，雖然說我面試的結果不怎麼樣，但是我的收獲還是很多的，在這裡與大家分享一下。希望大家在面試之前，一定要看看我們常用的算法，這是經常考的，還有就是面試官會問你算法複雜度，這是個很頭疼的問題，一開始學的時候就不會，希望哪個大神有好的算算法複雜度的方法，請指教。

    下面我們看看快速排序的思想 和 java實作

    快速排序是對冒泡排序的一種改進。

    不穩定，時間複雜度

最理想 O(nlogn)最差時間O(n^2)

    基本思想 ： 利用的是 分治法的基本思想

    通過一躺排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一不部分的所有資料都要小，然後再按次方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

    我們看一下快速排序的步驟：

    一趟快速排序的算法是：

    1) 設定兩個變量 i 和 j  排序開始的時候， i = 0   j = N -1   (N 為數組的長度）

    2）選取基準元素，通常選取數組的第一個元素為基準元素 key = arr[0]

    3)  從 j 開始向前搜尋，即由後向前（j--）搜尋  ，找到第一個小于key的值 arr[j] 将arr[i] 和 arr[j]進行交換 然後停止

    4) 從 i 開始向後搜尋，即由前向後（i++）搜尋， 找到第一個大于key的值 arr[i]  将arr[i] 和 arr[j] 進行交換 然後停止

    5) 重複第 3 、4、 5步 直到 i == j 停止

    這樣第一趟排序就完成了，這樣就保證了 基準元素左面的元素都比基準元素小 ，基準元素右面的元素都比基準元素大 ，下面進行的就是在分别對基準元素左邊的（元素都比基準小）數組進行排序（和第一趟排序步驟一樣）和右邊的數組進行排序。（遞歸）

        java 算法實作：