大廠面試???快速排序冒泡排序算法
基本排序方式詳圖:
一、概念
快速排序,顧名思義就是一種以效率快為特色的排序算法,快速排序(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),希望通過這篇文章,讓你對快速排序知識點有一定的了解,在日后面試或各種考試中對你有所幫助,希望大家以后多多支持腳本之家!
相關文章
Java異常處理運行時異常(RuntimeException)詳解及實例
這篇文章主要介紹了 Java異常處理運行時異常(RuntimeException)詳解及實例的相關資料,需要的朋友可以參考下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ù)也就是普通的參,下文更多詳細內(nèi)容需要的小伙伴可以參考一下2022-05-05Java SpringBoot+vue+實戰(zhàn)項目詳解
這篇文章主要介紹了SpringBoot+VUE實現(xiàn)前后端分離的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-09-09詳解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)換的教程,文中羅列了3中Jackson的使用方式,需要的朋友可以參考下2016-01-01PowerJob的TimingStrategyHandler工作流程源碼解讀
這篇文章主要為大家介紹了PowerJob的TimingStrategyHandler工作流程源碼解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01JSON.toJSONString()方法在Java中的使用方法及應用場景
這篇文章主要給大家介紹了關于JSON.toJSONString()方法在Java中的使用方法及應用場景,JSON.toJSONString是將對象轉(zhuǎn)化為Json字符串,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-04-04Java遠程調(diào)用Shell腳本并獲取輸出信息【推薦】
這篇文章主要介紹了Java遠程調(diào)用Shell腳本并獲取輸出信息,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下2019-09-09