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

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

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

基本排序方式詳圖:

一、概念

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

二、基本思想

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

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

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

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

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

空間復(fù)雜度

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

時間復(fù)雜度

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

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

三、算法步驟

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

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

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

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

四、具體示例

實例數(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] 取到第一個值“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ù)對左、右子序列遞歸進行處理,一直縮小到左、右都是一個值,則快速排序結(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);
    }
 
    /**
     * 快排核心算法,遞歸實現(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)了,交換兩個數(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碰頭了,說明要我排的這個子數(shù)列就剩下一個數(shù)了,就不用排序了
    if not start < end :
        return
 
    mid = li[start] #拿出第一個數(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ù)的位置
 
    # 我們要進行循環(huán),只要low和high沒有碰頭就一直進行,當(dāng)low和high相等說明碰頭了
    while low < high :
        #從high開始向左,找到第一個比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)記了這個空位
        li[low] = li[high]
        # 從low開始向右,找到第一個比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)記了這個空位
        li[high] = li[low]
        #以上我們完成了一次 從右側(cè)找到一個小數(shù)移到左側(cè),從左側(cè)找到一個大數(shù)移動到右側(cè)
    #當(dāng)這個while跳出來之后相當(dāng)于low和high碰頭了,我們把mid所在位置放在這個空位
    li[low] = mid
    #這個時候mid左側(cè)看的數(shù)都比mid小,mid右側(cè)的數(shù)都比mid大
 
    #然后我們對mid左側(cè)所有數(shù)進行上述的排序
    quick_sort( li , start, low-1 )
    #我們mid右側(cè)所有數(shù)進行上述排序
    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),希望通過這篇文章,讓你對快速排序知識點有一定的了解,在日后面試或各種考試中對你有所幫助,希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java異常處理運行時異常(RuntimeException)詳解及實例

    Java異常處理運行時異常(RuntimeException)詳解及實例

    這篇文章主要介紹了 Java異常處理運行時異常(RuntimeException)詳解及實例的相關(guān)資料,需要的朋友可以參考下http://time.qq.com/?pgv_ref=aiotime
    2017-05-05
  • Java中方法優(yōu)先調(diào)用可選參數(shù)還是固定參數(shù)

    Java中方法優(yōu)先調(diào)用可選參數(shù)還是固定參數(shù)

    這篇文章主要介紹了Java中方法優(yōu)先調(diào)用可選參數(shù)還是固定參數(shù),可選參數(shù)是?JDK?5?中新增的特性,也叫變長參數(shù)或可變參數(shù),固定參數(shù)的概念恰好與可選參數(shù)相反,固定參數(shù)也就是普通的參,下文更多詳細內(nèi)容需要的小伙伴可以參考一下
    2022-05-05
  • Java SpringBoot+vue+實戰(zhàn)項目詳解

    Java SpringBoot+vue+實戰(zhàn)項目詳解

    這篇文章主要介紹了SpringBoot+VUE實現(xiàn)前后端分離的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-09-09
  • Java中的zookeeper常用命令詳解

    Java中的zookeeper常用命令詳解

    這篇文章主要介紹了Java中的zookeeper常用命令,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-06-06
  • Java多線程4種拒絕策略小結(jié)

    Java多線程4種拒絕策略小結(jié)

    當(dāng)線程池中的任務(wù)隊列已滿且無法再接受新的任務(wù)時,就需要采取拒絕策略來處理這種情況,本文主要介紹了Java多線程拒絕策略,包含了四種常見的拒絕策略,具有一定的參考價值,感興趣的可以了解一下
    2024-03-03
  • 詳解Java的Hibernate框架中的緩存與原生SQL語句的使用

    詳解Java的Hibernate框架中的緩存與原生SQL語句的使用

    這篇文章主要介紹了Java的Hibernate框架中的緩存與原生SQL語句的使用,Hibernate是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下
    2015-12-12
  • 使用Jackson來實現(xiàn)Java對象與JSON的相互轉(zhuǎn)換的教程

    使用Jackson來實現(xiàn)Java對象與JSON的相互轉(zhuǎn)換的教程

    這篇文章主要介紹了使用Jackson來實現(xiàn)Java對象與JSON的互相轉(zhuǎn)換的教程,文中羅列了3中Jackson的使用方式,需要的朋友可以參考下
    2016-01-01
  • PowerJob的TimingStrategyHandler工作流程源碼解讀

    PowerJob的TimingStrategyHandler工作流程源碼解讀

    這篇文章主要為大家介紹了PowerJob的TimingStrategyHandler工作流程源碼解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2024-01-01
  • JSON.toJSONString()方法在Java中的使用方法及應(yīng)用場景

    JSON.toJSONString()方法在Java中的使用方法及應(yīng)用場景

    這篇文章主要給大家介紹了關(guān)于JSON.toJSONString()方法在Java中的使用方法及應(yīng)用場景,JSON.toJSONString是將對象轉(zhuǎn)化為Json字符串,文中通過代碼介紹的非常詳細,需要的朋友可以參考下
    2024-04-04
  • Java遠程調(diào)用Shell腳本并獲取輸出信息【推薦】

    Java遠程調(diào)用Shell腳本并獲取輸出信息【推薦】

    這篇文章主要介紹了Java遠程調(diào)用Shell腳本并獲取輸出信息,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-09-09

最新評論