Java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序

Panda 發(fā)布于2019-08-16 11:12 / 1189人閱讀

摘要：快排是一種不穩(wěn)定的排序算法，在經(jīng)過排序后，等值的元素的相對(duì)位置可能發(fā)生改變。

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中最常用也是面試中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代碼、快排的特點(diǎn)性能和快排的適用場(chǎng)景。

0、其他排序算法索引(待更)

java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序
java數(shù)據(jù)結(jié)構(gòu)與算法——插入排序

1、快速排序思想及原理

事實(shí)上，快速排序是堆冒泡排序的一種改進(jìn)。

它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割為兩部分，第一部分所有數(shù)據(jù)比第二部分的所有數(shù)據(jù)小，按照這種思路將兩部分?jǐn)?shù)據(jù)再次分別進(jìn)行快速排序，可以使用遞歸完成，最終使得整個(gè)數(shù)據(jù)序列有序。

具體來講，在待排數(shù)據(jù)中找一個(gè)基準(zhǔn)數(shù)據(jù)（通常取第一個(gè)數(shù)），接下來將待排數(shù)據(jù)中比基準(zhǔn)數(shù)據(jù)小的放在待排數(shù)據(jù)的左側(cè)，將比待排數(shù)據(jù)中比基準(zhǔn)數(shù)據(jù)大的放在待排數(shù)據(jù)右側(cè)。此時(shí)，左右兩個(gè)分區(qū)的元素相對(duì)有序，接著采用上述思路繼續(xù)對(duì)左右兩個(gè)分區(qū)繼續(xù)排序，直到各分區(qū)只有一個(gè)元素位置。這里用到了一個(gè)典型的分治思想。下面舉例說明：

待排序列依次為47、29、71、99、78、19、24、47。為了區(qū)分兩個(gè)47，將后面的47下面增加一個(gè)下劃線。

步驟：
1、選取一個(gè)基準(zhǔn)數(shù)，一般選第0個(gè)元素47。
2、將比基準(zhǔn)數(shù)小的移動(dòng)到左側(cè)，比基準(zhǔn)數(shù)大的移動(dòng)到右側(cè)，相等的不移動(dòng)，此時(shí)基準(zhǔn)數(shù)位置為K。
3、對(duì)左右兩側(cè)重復(fù)步驟1和步驟2，直到左右側(cè)細(xì)分到只有一個(gè)元素。

快排的難點(diǎn)也就是在第2步，怎么移動(dòng)各個(gè)數(shù)據(jù)？
<1> 首先從數(shù)列的右邊開始往左找，設(shè)下標(biāo)為i，也就是i--操作，找到第一個(gè)比基準(zhǔn)數(shù)小的值，讓他與基準(zhǔn)數(shù)交換；
<2> 接著開始從左往右找，設(shè)下標(biāo)為j，也就是j++，找到第一個(gè)比基準(zhǔn)數(shù)大的值，讓他與基準(zhǔn)數(shù)交換位置；
<3> 重復(fù)1和2，直到i和j相遇時(shí)結(jié)束，最后基準(zhǔn)值所在位置為k。

2、java快排代碼

public class QuickSort {
    private int[] array;
    public QuickSort(int[] array){
        this.array = array;
    }
    
    public void printSort(){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    
    public void sort(){
        quicksort(array,0,array.length -1);
    }
    
    private void quicksort(int[] array,int begin,int end){
        if(beginbase){ //從右往左掃，如果元素比基準(zhǔn)值大
                    j--;  //則右邊標(biāo)記--，直到找到第一個(gè)比基準(zhǔn)值小的，停止掃描
                }
                if(i
測(cè)試代碼
public class SortTest {
    public static void main(String[] args) {
        teseQuickSort();
    }

    private static void teseQuickSort(){
        int[] array = {3,5,7,3,8,9,6,1,0};
        QuickSort qs = new QuickSort(array);
        qs.sort();
        qs.printSort();
    }
}
3、快排的特點(diǎn)及性能
快排是在冒泡排序之上改進(jìn)而來的，冒泡排序每次只能交換相鄰的兩個(gè)元素，而快排則是跳躍式的交換，交換距離很大，總的比較次數(shù)和交換次數(shù)少了很多，速度也快了很多。
快排的平均時(shí)間復(fù)雜度為O(nlogn)，事實(shí)上，大多數(shù)情況下，排序速度要快于這個(gè)時(shí)間復(fù)雜度。快排實(shí)際上是采用的一種分而治之的思想，把問題分解為一個(gè)個(gè)的小問題去逐一解決，最終在把結(jié)果組合起來。
快排因?yàn)檫f歸調(diào)用，所以空間復(fù)雜度為O(logn)。
快排是一種不穩(wěn)定的排序算法，在經(jīng)過排序后，等值的元素的相對(duì)位置可能發(fā)生改變。
快排基本上被認(rèn)為是相同數(shù)量級(jí)中所有排序算法中平均性能最好的。
4、快排的適用場(chǎng)景
快排由于相對(duì)簡(jiǎn)單而且性能不錯(cuò)，所以快排適用于幾乎絕大多數(shù)場(chǎng)合。
其他排序算法索引(待更)
java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序
java數(shù)據(jù)結(jié)構(gòu)與算法——插入排序
碼字不易，如對(duì)您有幫助，歡迎點(diǎn)贊收藏打賞^_^