面試前必看的十大排序算法
緒論
身爲程序員,十大排序是是所有合格程序員所必備和掌握的,並且熱門的算法比如快排、歸併排序還可能問的比較細緻,對算法性能和複雜度的掌握有要求。bigsai 作爲一個負責任的 Java 和數據結構與算法方向的小博主,在這方面肯定不能讓讀者們有所漏洞。跟着本篇走,帶你捋一捋常見的十大排序算法,輕輕鬆鬆掌握!
首先對於排序來說大多數人對排序的概念停留在冒泡排序或者 JDK 中的 Arrays.sort(),手寫各種排序對很多人來說都是一種奢望,更別說十大排序算法了,不過還好你遇到了本篇文章!
對於排序的分類,主要不同的維度比如複雜度來分、內外部、比較非比較等維度來分類。我們正常講的十大排序算法是內部排序,我們更多將他們分爲兩大類:基於**「比較和非比較」**這個維度去分排序種類。
-
「非比較類的有桶排序、基數排序、計數排序」。也有很多人將排序歸納爲 8 大排序,那就是因爲基數排序、計數排序是建立在桶排序之上或者是一種特殊的桶排序,但是基數排序和計數排序有它特有的特徵,所以在這裏就將他們歸納爲 10 種經典排序算法。而比較類排序也可分爲
-
比較類排序也有更細緻的分法,有基於交換的、基於插入的、基於選擇的、基於歸併的,更細緻的可以看下面的腦圖。
交換類
冒泡排序
冒泡排序,又稱起泡排序,它是一種基於交換的排序典型,也是快排思想的基礎,冒泡排序是一種穩定排序算法,時間複雜度爲 O(n^2). 基本思想是:「循環遍歷多次每次從前往後把大元素往後調,每次確定一個最大 (最小) 元素,多次後達到排序序列。」(或者從後向前把小元素往前調)。
具體思想爲 (把大元素往後調):
-
從第一個元素開始往後遍歷,每到一個位置判斷是否比後面的元素大,如果比後面元素大,那麼就交換兩者大小,然後繼續向後,這樣的話進行一輪之後就可以保證**「最大的那個數被交換交換到最末的位置可以確定」**。
-
第二次同樣從開始起向後判斷着前進,如果當前位置比後面一個位置更大的那麼就和他後面的那個數交換。但是有點注意的是,這次並不需要判斷到最後,只需要判斷到倒數第二個位置就行 (因爲第一次我們已經確定最大的在倒數第一,這次的目的是確定倒數第二)
-
同理,後面的遍歷長度每次減一,直到第一個元素使得整個元素有序。
例如2 5 3 1 4
排序過程如下:
實現代碼爲:
public void maopaosort(int[] a) {
// TODO Auto-generated method stub
for(int i=a.length-1;i>=0;i--)
{
for(int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
int team=a[j];
a[j]=a[j+1];
a[j+1]=team;
}
}
}
}
快速排序
快速排序是對冒泡排序的一種改進,採用遞歸分治的方法進行求解。而快排相比冒泡是一種不穩定排序, 時間複雜度最壞是 O(n^2), 平均時間複雜度爲 O(nlogn), 最好情況的時間複雜度爲 O(nlogn)。
對於快排來說,**「基本思想」**是這樣的
-
快排需要將序列變成兩個部分,就是**「序列左邊全部小於一個數」**,**「序列右面全部大於一個數」**,然後利用遞歸的思想再將左序列當成一個完整的序列再進行排序,同樣把序列的右側也當成一個完整的序列進行排序。
-
其中這個數在這個序列中是可以隨機取的,可以取最左邊,可以取最右邊,當然也可以取隨機數。但是**「通常」**不優化情況我們取最左邊的那個數。
實現代碼爲:
public void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
//下面兩句的順序一定不能混,否則會產生數組越界!!!very important!!!
if(low>high)//作爲判斷是否截止條件
return;
int k=a[low];//額外空間k,取最左側的一個作爲衡量,最後要求左側都比它小,右側都比它大。
while(low<high)//這一輪要求把左側小於a[low],右側大於a[low]。
{
while(low<high&&a[high]>=k)//右側找到第一個小於k的停止
{
high--;
}
//這樣就找到第一個比它小的了
a[low]=a[high];//放到low位置
while(low<high&&a[low]<=k)//在low往右找到第一個大於k的,放到右側a[high]位置
{
low++;
}
a[high]=a[low];
}
a[low]=k;//賦值然後左右遞歸分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}
插入類排序
直接插入排序
直接插入排序在所有排序算法中的是最簡單排序方式之一。和我們上學時候 從前往後、按高矮順序排序,那麼一堆高低無序的人羣中,從第一個開始,如果前面有比自己高的,就直接插入到合適的位置。**「一直到隊伍的最後一個完成插入」**整個隊列才能滿足有序。
直接插入排序遍歷比較時間複雜度是每次 O(n), 交換的時間複雜度每次也是 O(n), 那麼 n 次總共的時間複雜度就是 O(n^2)。有人會問折半 (二分) 插入能否優化成 O(nlogn), 答案是不能的。因爲二分只能減少查找複雜度每次爲 O(logn), 而插入的時間複雜度每次爲 O(n)級別,這樣總的時間複雜度級別還是 O(n^2).
插入排序的具體步驟:
-
選取當前位置 (當前位置前面已經有序) 目標就是將當前位置數據插入到前面合適位置。
-
向前枚舉或者二分查找,找到待插入的位置。
-
移動數組,賦值交換,達到插入效果。
實現代碼爲:
public void insertsort (int a[])
{
int team=0;
for(int i=1;i<a.length;i++)
{
System.out.println(Arrays.toString(a));
team=a[i];
for(int j=i-1;j>=0;j--)
{
if(a[j]>team)
{
a[j+1]=a[j];
a[j]=team;
}
else {
break;
}
}
}
}
希爾排序
直接插入排序因爲是 O(n^2), 在數據量很大或者數據移動位次太多會導致效率太低。很多排序都會想辦法拆分序列,然後組合,希爾排序就是以一種特殊的方式進行預處理,考慮到了**「數據量和有序性」**兩個方面緯度來設計算法。使得序列前後之間小的儘量在前面,大的儘量在後面,進行若干次的分組別計算,最後一組即是一趟完整的直接插入排序。
對於一個長串
,希爾首先將序列分割 (非線性分割) 而是**「按照某個數模」**(取餘
這個類似報數 1、2、3、4。1、2、3、4) 這樣形式上在一組的分割先**「各組分別進行直接插入排序」**, 這樣**「很小的數在後面」**可以通過**「較少的次數移動到相對靠前」**的位置。然後慢慢合併變長,再稍稍移動。
因爲每次這樣插入都會使得序列變得更加有序,稍微有序序列執行直接插入排序成本並不高。所以這樣能夠在合併到最終的時候基本小的在前,大的在後,代價越來越小。這樣希爾排序相比插入排序還是能節省不少時間的。
實現代碼爲:
public void shellsort (int a[])
{
int d=a.length;
int team=0;//臨時變量
for(;d>=1;d/=2)//共分成d組
for(int i=d;i<a.length;i++)//到那個元素就看這個元素在的那個組即可
{
team=a[i];
for(int j=i-d;j>=0;j-=d)
{
if(a[j]>team)
{
a[j+d]=a[j];
a[j]=team;
}
else {
break;
}
}
}
}
選擇類排序
簡單選擇排序
簡單選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到**「已排序序列的末尾」**。以此類推,直到所有元素均排序完畢。
實現代碼爲:
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; // 最小位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j; // 更換最小位置
}
}
if (min != i) {
swap(arr, i, min); // 與第i個位置進行交換
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
堆排序
對於堆排序,首先是建立在堆的基礎上,堆是一棵完全二叉樹,還要先認識下大根堆和小根堆,完全二叉樹中所有節點均大於 (或小於) 它的孩子節點,所以這裏就分爲兩種情況
-
如果所有節點**「大於」**孩子節點值,那麼這個堆叫做**「大根堆」**,堆的最大值在根節點。
-
如果所有節點**「小於」**孩子節點值,那麼這個堆叫做**「小根堆」**,堆的最小值在根節點。
堆排序首先就是**「建堆」**,然後再是調整。對於二叉樹 (數組表示),我們從下往上進行調整,從**「第一個非葉子節點」**開始向前調整,對於調整的規則如下:
建堆是一個 O(n) 的時間複雜度過程,建堆完成後就需要進行刪除頭排序。給定數組建堆 (creatHeap)
①從第一個非葉子節點開始判斷交換下移 (shiftDown),使得當前節點和子孩子能夠保持堆的性質
②但是普通節點替換可能沒問題,對如果交換打破子孩子堆結構性質,那麼就要重新下移 (shiftDown) 被交換的節點一直到停止。
堆構造完成,取第一個堆頂元素爲最小 (最大),剩下左右孩子依然滿足堆的性值,但是缺個堆頂元素,如果給孩子調上來,可能會調動太多並且可能破壞堆結構。
①所以索性把最後一個元素放到第一位。這樣只需要判斷交換下移 (shiftDown), 不過需要注意此時整個堆的大小已經發生了變化,我們在邏輯上不會使用被拋棄的位置,所以在設計函數的時候需要附帶一個堆大小的參數。
②重複以上操作,一直堆中所有元素都被取得停止。
而堆算法複雜度的分析上,之前建堆時間複雜度是 O(n)。而每次刪除堆頂然後需要向下交換,每個個數最壞爲 logn 個。這樣複雜度就爲 O(nlogn). 總的時間複雜度爲 O(n)+O(nlogn)=O(nlogn).
實現代碼爲:
static void swap(int arr[],int m,int n)
{
int team=arr[m];
arr[m]=arr[n];
arr[n]=team;
}
//下移交換 把當前節點有效變換成一個堆(小根)
static void shiftDown(int arr[],int index,int len)//0 號位置不用
{
int leftchild=index*2+1;//左孩子
int rightchild=index*2+2;//右孩子
if(leftchild>=len)
return;
else if(rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild])//右孩子在範圍內並且應該交換
{
swap(arr, index, rightchild);//交換節點值
shiftDown(arr, rightchild, len);//可能會對孩子節點的堆有影響,向下重構
}
else if(arr[leftchild]<arr[index])//交換左孩子
{
swap(arr, index, leftchild);
shiftDown(arr, leftchild, len);
}
}
//將數組創建成堆
static void creatHeap(int arr[])
{
for(int i=arr.length/2;i>=0;i--)
{
shiftDown(arr, i,arr.length);
}
}
static void heapSort(int arr[])
{
System.out.println("原始數組爲 :"+Arrays.toString(arr));
int val[]=new int[arr.length]; //臨時儲存結果
//step1建堆
creatHeap(arr);
System.out.println("建堆後的序列爲 :"+Arrays.toString(arr));
//step2 進行n次取值建堆,每次取堆頂元素放到val數組中,最終結果即爲一個遞增排序的序列
for(int i=0;i<arr.length;i++)
{
val[i]=arr[0];//將堆頂放入結果中
arr[0]=arr[arr.length-1-i];//刪除堆頂元素,將末尾元素放到堆頂
shiftDown(arr, 0, arr.length-i);//將這個堆調整爲合法的小根堆,注意(邏輯上的)長度有變化
}
//數值克隆複製
for(int i=0;i<arr.length;i++)
{
arr[i]=val[i];
}
System.out.println("堆排序後的序列爲:"+Arrays.toString(arr));
}
歸併類排序
在歸併類排序一般只講歸併排序,但是歸併排序也分二路歸併、多路歸併,這裏就講較多的二路歸併排序,且用遞歸方式實現。
歸併排序
歸併和快排都是**「基於分治算法」**的,分治算法其實應用挺多的,很多分治會用到遞歸,但事實上**「分治和遞歸是兩把事」**。分治就是分而治之,可以採用遞歸實現,也可以自己遍歷實現非遞歸方式。而歸併排序就是先將問題分解成代價較小的子問題,子問題再採取代價較小的合併方式完成一個排序。
至於歸併的思想是這樣的:
-
第一次:整串先進行劃分成一個一個單獨,第一次是將序列中 (
1 2 3 4 5 6---
) 兩兩歸併成有序,歸併完 (xx xx xx xx----
) 這樣局部有序的序列。 -
第二次就是兩兩歸併成若干四個 (
1 2 3 4 5 6 7 8 ----
)「每個小局部是有序的」。 -
就這樣一直到最後這個串串只剩一個,然而這個耗費的總次數 logn。每次操作的時間複雜的又是
O(n)
。所以總共的時間複雜度爲O(nlogn)
.
合併爲一個 O(n) 的過程:
實現代碼爲:
private static void mergesort(int[] array, int left, int right) {
int mid=(left+right)/2;
if(left<right)
{
mergesort(array, left, mid);
mergesort(array, mid+1, right);
merge(array, left,mid, right);
}
}
private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;
while (lindex<=mid&&rindex<=r) {//先左右比較合併
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
}
else {
team[teamindex++]=array[rindex++];
}
}
while(lindex<=mid)//當一個越界後剩餘按序列添加即可
{
team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{
array[l+i]=team[i];
}
}
桶類排序
桶排序
桶排序是一種用空間換取時間的排序,桶排序重要的是它的思想,而不是具體實現,時間複雜度最好可能是線性 O(n),桶排序不是基於比較的排序而是一種分配式的。桶排序從字面的意思上看:
-
桶:若干個桶,說明此類排序將數據放入若干個桶中。
-
桶:每個桶有容量,桶是有一定容積的容器,所以每個桶中可能有多個元素。
-
桶:從整體來看,整個排序更希望桶能夠更勻稱,即既不溢出 (太多) 又不太少。
桶排序的思想爲:「將待排序的序列分到若干個桶中,每個桶內的元素再進行個別排序。」 當然桶排序選擇的方案跟具體的數據有關係,桶排序是一個比較廣泛的概念,並且計數排序是一種特殊的桶排序,基數排序也是建立在桶排序的基礎上。在數據分佈均勻且每個桶元素趨近一個時間複雜度能達到 O(n), 但是如果數據範圍較大且相對集中就不太適合使用桶排序。
實現一個簡單桶排序:
import java.util.ArrayList;
import java.util.List;
//微信公衆號:bigsai
public class bucketSort {
public static void main(String[] args) {
int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
List[] buckets=new ArrayList[5];
for(int i=0;i<buckets.length;i++)//初始化
{
buckets[i]=new ArrayList<Integer>();
}
for(int i=0;i<a.length;i++)//將待排序序列放入對應桶中
{
int index=a[i]/10;//對應的桶號
buckets[index].add(a[i]);
}
for(int i=0;i<buckets.length;i++)//每個桶內進行排序(使用系統自帶快排)
{
buckets[i].sort(null);
for(int j=0;j<buckets[i].size();j++)//順便打印輸出
{
System.out.print(buckets[i].get(j)+" ");
}
}
}
}
計數排序
計數排序是一種特殊的桶排序,每個桶的大小爲 1,每個桶不在用 List 表示,而通常用一個值用來計數。
在**「設計具體算法的時候」**,先找到最小值 min,再找最大值 max。然後創建這個區間大小的數組, 從 min 的位置開始計數,這樣就可以最大程度的壓縮空間,提高空間的使用效率。
public static void countSort(int a[])
{
int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;
for(int i=0;i<a.length;i++)//找到max和min
{
if(a[i]<min)
min=a[i];
if(a[i]>max)
max=a[i];
}
int count[]=new int[max-min+1];//對元素進行計數
for(int i=0;i<a.length;i++)
{
count[a[i]-min]++;
}
//排序取值
int index=0;
for(int i=0;i<count.length;i++)
{
while (count[i]-->0) {
a[index++]=i+min;//有min纔是真正值
}
}
}
基數排序
基數排序是一種很容易理解但是比較難實現 (優化) 的算法。基數排序也稱爲卡片排序,基數排序的原理就是多次利用計數排序(計數排序是一種特殊的桶排序),但是和前面的普通桶排序和計數排序有所區別的是,「基數排序並不是將一個整體分配到一個桶中」,而是將自身拆分成一個個組成的元素,每個元素分別順序分配放入桶中、順序收集,當從前往後或者從後往前每個位置都進行過這樣順序的分配、收集後,就獲得了一個有序的數列。
如果是數字類型排序,那麼這個桶只需要裝 0-9 大小的數字,但是如果是字符類型,那麼就需要注意 ASCII 的範圍。
所以遇到這種情況我們基數排序思想很簡單,就拿 934,241,3366,4399 這幾個數字進行基數排序的一趟過程來看,第一次會根據各位進行分配、收集:
分配和收集都是有序的,第二次會根據十位進行分配、收集,此次是在第一次個位分配、收集基礎上進行的,所以所有數字單看個位十位是有序的。
而第三次就是對百位進行分配收集,此次完成之後百位及其以下是有序的。
而最後一次的時候進行處理的時候,千位有的數字需要補零,這次完畢後後千位及以後都有序,即整個序列排序完成。
簡單實現代碼爲:
static void radixSort(int[] arr)//int 類型 從右往左
{
List<Integer>bucket[]=new ArrayList[10];
for(int i=0;i<10;i++)
{
bucket[i]=new ArrayList<Integer>();
}
//找到最大值
int max=0;//假設都是正數
for(int i=0;i<arr.length;i++)
{
if(arr[i]>max)
max=arr[i];
}
int divideNum=1;//1 10 100 100……用來求對應位的數字
while (max>0) {//max 和num 控制
for(int num:arr)
{
bucket[(num/divideNum)%10].add(num);//分配 將對應位置的數字放到對應bucket中
}
divideNum*=10;
max/=10;
int idx=0;
//收集 重新撿起數據
for(List<Integer>list:bucket)
{
for(int num:list)
{
arr[idx++]=num;
}
list.clear();//收集完需要清空留下次繼續使用
}
}
}
當然,基數排序還有字符串等長、不等長、一維數組優化等各種實現需要需學習,具體可以參考公衆號內其他文章。
結語
本次十大排序就這麼瀟灑的過了一遍,我想大家都應該有所領悟了吧!對於算法總結,避免不必要的勞動力,我分享這個表格給大家:
原創不易,bigsai 請你幫兩件事幫忙一下:
-
點贊、在看、分享支持一下, 您的肯定是我創作的源源動力。
-
微信搜索「「bigsai」」,關注我的公衆號,不僅免費送你電子書,我還會第一時間在公衆號分享知識技術。加我還可拉你進力扣打卡羣一起打卡 LeetCode。
記得關注、咱們下次再見!
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/w4xxz8vqR8Bceor8-bKK-Q