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

大廠面試???快速排序冒泡排序算法

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

基本排序方式詳圖:

一、概念

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

二、基本思想

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

然后將比基準小的排在左邊,比基準大的放到右邊;

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

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

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

空間復雜度

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

時間復雜度

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

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

三、算法步驟

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

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

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

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

四、具體示例

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

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

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

2.從左邊取的基準值,左邊的Arr[L]就空出來了,則先從右側取值來填,從最右側下標開始,在Arr[R] 取到第一個值“8”;

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

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

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

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

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

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

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

9.最后L坐標和R坐標重合了,將Pivot基準值填入

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

11.繼續(xù)對左、右子序列遞歸進行處理,一直縮小到左、右都是一個值,則快速排序結束,最終得出順序數(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中存放基準數(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)結束表示找到了位置或者(i>=j)了,交換兩個數(shù)在數(shù)組中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
 
        // 將基準數(shù)放到中間的位置(基準數(shù)歸位)
        array[left] = array[i];
        array[i] = base;
 
        // 遞歸,繼續(xù)向基準的左右兩邊執(zhí)行和上面同樣的操作
        // i的索引處為上面已確定好的基準值的位置,無需再處理
        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] + " ");
        }
    }
}

返回結果:

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

@python代碼

#快速排序 傳入列表、開始位置和結束位置
def quick_sort( li , start , end ):
    # 如果start和end碰頭了,說明要我排的這個子數(shù)列就剩下一個數(shù)了,就不用排序了
    if not start < end :
        return
 
    mid = li[start] #拿出第一個數(shù)當作基準數(shù)mid
    low = start   #low來標記左側從基準數(shù)始找比mid大的數(shù)的位置
    high = end  #high來標記右側end向左找比mid小的數(shù)的位置
 
    # 我們要進行循環(huán),只要low和high沒有碰頭就一直進行,當low和high相等說明碰頭了
    while low < high :
        #從high開始向左,找到第一個比mid小或者等于mid的數(shù),標記位置,(如果high的數(shù)比mid大,我們就左移high)
        # 并且我們要確定找到之前,如果low和high碰頭了,也不找了
        while low < high and li[high] > mid :
            high -= 1
        #跳出while后,high所在的下標就是找到的右側比mid小的數(shù)
        #把找到的數(shù)放到左側的空位 low 標記了這個空位
        li[low] = li[high]
        # 從low開始向右,找到第一個比mid大的數(shù),標記位置,(如果low的數(shù)小于等于mid,我們就右移low)
        # 并且我們要確定找到之前,如果low和high碰頭了,也不找了
        while low < high and li[low] <= mid :
            low += 1
        #跳出while循環(huán)后low所在的下標就是左側比mid大的數(shù)所在位置
        # 我們把找到的數(shù)放在右側空位上,high標記了這個空位
        li[high] = li[low]
        #以上我們完成了一次 從右側找到一個小數(shù)移到左側,從左側找到一個大數(shù)移動到右側
    #當這個while跳出來之后相當于low和high碰頭了,我們把mid所在位置放在這個空位
    li[low] = mid
    #這個時候mid左側看的數(shù)都比mid小,mid右側的數(shù)都比mid大
 
    #然后我們對mid左側所有數(shù)進行上述的排序
    quick_sort( li , start, low-1 )
    #我們mid右側所有數(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)

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

相關文章

最新評論