欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

大廠面試常考:快速排序冒泡排序算法

 更新時(shí)間:2021年08月13日 16:58:50   作者:_陳哈哈  
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高,因此經(jīng)常被采用,再加上快速排序思想----分治法也確實(shí)實(shí)用,因此很多軟件公司的筆試面試,包括像BAT、字節(jié)、美團(tuán)等知名IT公司都喜歡考查快速排序原理和手寫源碼

基本排序方式詳圖:

一、概念

快速排序,顧名思義就是一種以效率快為特色的排序算法,快速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)。由英國計(jì)算機(jī)專家:托尼·霍爾(Tony Hoare)在1960年提出。

二、基本思想

從排序數(shù)組中找出一個(gè)數(shù),可以隨機(jī)取,也可以取固定位置,一般是取第一個(gè)或最后一個(gè),稱為基準(zhǔn)數(shù)。

然后將比基準(zhǔn)小的排在左邊,比基準(zhǔn)大的放到右邊;

如何放置呢,就是和基準(zhǔn)數(shù)進(jìn)行交換,交換完左邊都是比基準(zhǔn)小的,右邊都是比較基準(zhǔn)大的,這樣就將一個(gè)數(shù)組分成了兩個(gè)子數(shù)組,然后再按照同樣的方法把子數(shù)組再分成更小的子數(shù)組,直到不能分解(子數(shù)組只有一個(gè)值)為止。

以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

快速排序采用了一種分治的策略,通常稱其為分治法(Divide-and-ConquerMethod),現(xiàn)在各種語言中自帶的排序庫很多使用的都是快速排序。

空間復(fù)雜度

快速排序是一種原地排序,只需要一個(gè)很小的棧作為輔助空間,空間復(fù)雜度為O(log2n),所以適合在數(shù)據(jù)集比較大的時(shí)候使用。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度比較復(fù)雜,最好的情況是O(n),最差的情況是O(n2),所以平時(shí)說的O(nlogn),為其平均時(shí)間復(fù)雜度。

  • O(n):理想的情況,每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分,經(jīng)過log2n趟劃分,便可得到長度為1的子表。這樣,整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。
  • O(n2):最壞的情況,每次所選的中間數(shù)是當(dāng)前序列中的最大或最小元素,這使得每次劃分所得的子表中一個(gè)為空表,另一子表的長度為原表的長度-1。這樣,長度為n的數(shù)據(jù)表的快速排序需要經(jīng)過n趟劃分,使得整個(gè)排序算法的時(shí)間復(fù)雜度為O(n2)。

三、算法步驟

1.選定一個(gè)基準(zhǔn)數(shù)(一般取第一位數(shù)字)作為中心點(diǎn)(Pivot);

2.將大于Pivot的數(shù)字放到Pivot的左邊;

3.將小于Pivot的數(shù)字放到Pivot的右邊;

4.第一次排序結(jié)束后,分別對(duì)左右子序列繼續(xù)遞歸重復(fù)前三步操作。

四、具體示例

實(shí)例數(shù)組:arr[] = {19,97,9,17,1,8};

1.取出基準(zhǔn)數(shù)Pivot,以該值為中心軸。

快速排序中的規(guī)則:右邊有坑,就從左邊Arr[L + n]取值來填,反之左邊有坑,則從右邊Arr[R - n]取值來填;

2.從左邊取的基準(zhǔn)值,左邊的Arr[L]就空出來了,則先從右側(cè)取值來填,從最右側(cè)下標(biāo)開始,在Arr[R] 取到第一個(gè)值“8”;

3.將取到的Arr[R]與基準(zhǔn)值比較,發(fā)現(xiàn)小于基準(zhǔn)值,則插入到Arr[R],占到了基準(zhǔn)值Pivot的位置上。

4.然后從Arr[L+1]的位置取出值,繼續(xù)向右匹配并排序,將匹配到的值(匹配規(guī)則如下)插入到右側(cè)Arr[R]的空位置上;

匹配規(guī)則:大于基準(zhǔn)值的插入到Arr[R],如果小于,則直接忽略并跳過,繼續(xù)向右取值,直到坐標(biāo)L和坐標(biāo)R重合。

5.發(fā)現(xiàn)取出的值大于Pivot(基準(zhǔn)值),則將其插入到Arr[R]。

6.左邊有坑,從右邊Arr[R-1]繼續(xù)匹配,Arr[R-1] = 1,小于基準(zhǔn)值,則插入到Arr[L]的坑中;

7.右邊有坑了,繼續(xù)從左邊取值繼續(xù)匹配,則取到Arr[L+1] = 9,小于基準(zhǔn)值,則忽略并跳過,繼續(xù)找Arr[L + 1]繼續(xù)匹配。

8.繼續(xù)從左邊坐標(biāo) + 1 取值繼續(xù)匹配,則取到Arr[L] = 17,又小于基準(zhǔn)值,則忽略并跳過,繼續(xù)找Arr[L + 1]繼續(xù)匹配。

9.最后L坐標(biāo)和R坐標(biāo)重合了,將Pivot基準(zhǔn)值填入

10.至此,快速排序第一輪完整流程結(jié)束,分出了左右子序列,左邊都是小于Pivot基準(zhǔn)值的,右邊都是大于Pivot基準(zhǔn)值的。

11.繼續(xù)對(duì)左、右子序列遞歸進(jìn)行處理,一直縮小到左、右都是一個(gè)值,則快速排序結(jié)束,最終得出順序數(shù)組{1,8,9,17,19,97};中間遞歸流程這里不再贅述。

五、快排代碼

 @java代碼

package com.softsec.demo;
 
/**
 * Created with IDEA
 *
 * @Author Chensj
 * @Date 2020/5/17 19:04
 * @Description
 * @Version 1.0
 */
public class quickSortDemo {
 
    public static void main(String[] args) {
        // 創(chuàng)建測試數(shù)組
        int[] arr = new int[]{19,97,9,17,1,8};
        System.out.println("排序前:");
        showArray(arr); // 打印數(shù)組
        // 調(diào)用快排接口
        quickSort(arr);
        System.out.println("\n" + "排序后:");
        showArray(arr);// 打印數(shù)組
    }
 
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return ;
        }
        sort(array, 0, len - 1);
    }
 
    /**
     * 快排核心算法,遞歸實(shí)現(xiàn)
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基準(zhǔn)數(shù)
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 順序很重要,先從右邊開始往左找,直到找到比base值小的數(shù)
            while(array[j] >= base && i < j) {
                j--;
            }
 
            // 再從左往右邊找,直到找到比base值大的數(shù)
            while(array[i] <= base && i < j) {
                i++;
            }
 
            // 上面的循環(huán)結(jié)束表示找到了位置或者(i>=j)了,交換兩個(gè)數(shù)在數(shù)組中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
 
        // 將基準(zhǔn)數(shù)放到中間的位置(基準(zhǔn)數(shù)歸位)
        array[left] = array[i];
        array[i] = base;
 
        // 遞歸,繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作
        // i的索引處為上面已確定好的基準(zhǔn)值的位置,無需再處理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }
 
    /**
     * 數(shù)組打印
     * @param num
     */
    private static void showArray(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

返回結(jié)果:

排序前:
19 97 9 17 1 8
排序后:
1 8 9 17 19 97
Process finished with exit code 0

@python代碼

#快速排序 傳入列表、開始位置和結(jié)束位置
def quick_sort( li , start , end ):
    # 如果start和end碰頭了,說明要我排的這個(gè)子數(shù)列就剩下一個(gè)數(shù)了,就不用排序了
    if not start < end :
        return
 
    mid = li[start] #拿出第一個(gè)數(shù)當(dāng)作基準(zhǔn)數(shù)mid
    low = start   #low來標(biāo)記左側(cè)從基準(zhǔn)數(shù)始找比mid大的數(shù)的位置
    high = end  #high來標(biāo)記右側(cè)end向左找比mid小的數(shù)的位置
 
    # 我們要進(jìn)行循環(huán),只要low和high沒有碰頭就一直進(jìn)行,當(dāng)low和high相等說明碰頭了
    while low < high :
        #從high開始向左,找到第一個(gè)比mid小或者等于mid的數(shù),標(biāo)記位置,(如果high的數(shù)比mid大,我們就左移high)
        # 并且我們要確定找到之前,如果low和high碰頭了,也不找了
        while low < high and li[high] > mid :
            high -= 1
        #跳出while后,high所在的下標(biāo)就是找到的右側(cè)比mid小的數(shù)
        #把找到的數(shù)放到左側(cè)的空位 low 標(biāo)記了這個(gè)空位
        li[low] = li[high]
        # 從low開始向右,找到第一個(gè)比mid大的數(shù),標(biāo)記位置,(如果low的數(shù)小于等于mid,我們就右移low)
        # 并且我們要確定找到之前,如果low和high碰頭了,也不找了
        while low < high and li[low] <= mid :
            low += 1
        #跳出while循環(huán)后low所在的下標(biāo)就是左側(cè)比mid大的數(shù)所在位置
        # 我們把找到的數(shù)放在右側(cè)空位上,high標(biāo)記了這個(gè)空位
        li[high] = li[low]
        #以上我們完成了一次 從右側(cè)找到一個(gè)小數(shù)移到左側(cè),從左側(cè)找到一個(gè)大數(shù)移動(dòng)到右側(cè)
    #當(dāng)這個(gè)while跳出來之后相當(dāng)于low和high碰頭了,我們把mid所在位置放在這個(gè)空位
    li[low] = mid
    #這個(gè)時(shí)候mid左側(cè)看的數(shù)都比mid小,mid右側(cè)的數(shù)都比mid大
 
    #然后我們對(duì)mid左側(cè)所有數(shù)進(jìn)行上述的排序
    quick_sort( li , start, low-1 )
    #我們mid右側(cè)所有數(shù)進(jìn)行上述排序
    quick_sort( li , low +1 , end )
 
 
#入口函數(shù)
if __name__ == '__main__':
    li = [19,97,9,17,1,8]
    quick_sort(li , 0 , len(li) -1 )
    print(li)

快速排序是當(dāng)前最為流行的排序算法之一,各大公司面試中頻頻出現(xiàn),希望通過這篇文章,讓你對(duì)快速排序知識(shí)點(diǎn)有一定的了解,在日后面試或各種考試中對(duì)你有所幫助,希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論