大廠面試常考:快速排序冒泡排序算法
基本排序方式詳圖:
一、概念
快速排序,顧名思義就是一種以效率快為特色的排序算法,快速排序(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)文章
Java異常處理運(yùn)行時(shí)異常(RuntimeException)詳解及實(shí)例
這篇文章主要介紹了 Java異常處理運(yùn)行時(shí)異常(RuntimeException)詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下http://time.qq.com/?pgv_ref=aiotime2017-05-05Java中方法優(yōu)先調(diào)用可選參數(shù)還是固定參數(shù)
這篇文章主要介紹了Java中方法優(yōu)先調(diào)用可選參數(shù)還是固定參數(shù),可選參數(shù)是?JDK?5?中新增的特性,也叫變長參數(shù)或可變參數(shù),固定參數(shù)的概念恰好與可選參數(shù)相反,固定參數(shù)也就是普通的參,下文更多詳細(xì)內(nèi)容需要的小伙伴可以參考一下2022-05-05Java SpringBoot+vue+實(shí)戰(zhàn)項(xiàng)目詳解
這篇文章主要介紹了SpringBoot+VUE實(shí)現(xiàn)前后端分離的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-09-09詳解Java的Hibernate框架中的緩存與原生SQL語句的使用
這篇文章主要介紹了Java的Hibernate框架中的緩存與原生SQL語句的使用,Hibernate是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下2015-12-12使用Jackson來實(shí)現(xiàn)Java對(duì)象與JSON的相互轉(zhuǎn)換的教程
這篇文章主要介紹了使用Jackson來實(shí)現(xiàn)Java對(duì)象與JSON的互相轉(zhuǎn)換的教程,文中羅列了3中Jackson的使用方式,需要的朋友可以參考下2016-01-01PowerJob的TimingStrategyHandler工作流程源碼解讀
這篇文章主要為大家介紹了PowerJob的TimingStrategyHandler工作流程源碼解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01JSON.toJSONString()方法在Java中的使用方法及應(yīng)用場景
這篇文章主要給大家介紹了關(guān)于JSON.toJSONString()方法在Java中的使用方法及應(yīng)用場景,JSON.toJSONString是將對(duì)象轉(zhuǎn)化為Json字符串,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-04-04Java遠(yuǎn)程調(diào)用Shell腳本并獲取輸出信息【推薦】
這篇文章主要介紹了Java遠(yuǎn)程調(diào)用Shell腳本并獲取輸出信息,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-09-09