溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

程序員必知必會(huì)的排序算法有哪些

發(fā)布時(shí)間:2021-10-23 16:21:30 來源:億速云 閱讀:132 作者:iii 欄目:web開發(fā)

這篇文章主要介紹“程序員必知必會(huì)的排序算法有哪些”,在日常操作中,相信很多人在程序員必知必會(huì)的排序算法有哪些問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”程序員必知必會(huì)的排序算法有哪些”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!

緒論

身為程序員,十大排序是是所有合格程序員所必備和掌握的,并且熱門的算法比如快排、歸并排序還可能問的比較細(xì)致,對算法性能和復(fù)雜度的掌握有要求。bigsai作為一個(gè)負(fù)責(zé)任的Java和數(shù)據(jù)結(jié)構(gòu)與算法方向的小博主,在這方面肯定不能讓讀者們有所漏洞。跟著本篇走,帶你捋一捋常見的十大排序算法,輕輕松松掌握!

首先對于排序來說大多數(shù)人對排序的概念停留在冒泡排序或者JDK中的Arrays.sort(),手寫各種排序?qū)芏嗳藖碚f都是一種奢望,更別說十大排序算法了,不過還好你遇到了本篇文章!

對于排序的分類,主要不同的維度比如復(fù)雜度來分、內(nèi)外部、比較非比較等維度來分類。我們正常講的十大排序算法是內(nèi)部排序,我們更多將他們分為兩大類:基于 「比較和非比較」 這個(gè)維度去分排序種類。

  • 「非比較類的有桶排序、基數(shù)排序、計(jì)數(shù)排序」。也有很多人將排序歸納為8大排序,那就是因?yàn)榛鶖?shù)排序、計(jì)數(shù)排序是建立在桶排序之上或者是一種特殊的桶排序,但是基數(shù)排序和計(jì)數(shù)排序有它特有的特征,所以在這里就將他們歸納為10種經(jīng)典排序算法。而比較類排序也可分為

  • 比較類排序也有更細(xì)致的分法,有基于交換的、基于插入的、基于選擇的、基于歸并的,更細(xì)致的可以看下面的腦圖。

程序員必知必會(huì)的排序算法有哪些

冒泡排序

冒泡排序,又稱起泡排序,它是一種基于交換的排序典型,也是快排思想的基礎(chǔ),冒泡排序是一種穩(wěn)定排序算法,時(shí)間復(fù)雜度為O(n^2).基本思想是: 「循環(huán)遍歷多次每次從前往后把大元素往后調(diào),每次確定一個(gè)最大(最小)元素,多次后達(dá)到排序序列?!?nbsp;(或者從后向前把小元素往前調(diào))。

具體思想為(把大元素往后調(diào)):

  • 從第一個(gè)元素開始往后遍歷,每到一個(gè)位置判斷是否比后面的元素大,如果比后面元素大,那么就交換兩者大小,然后繼續(xù)向后,這樣的話進(jìn)行一輪之后就可以保證 「最大的那個(gè)數(shù)被交換交換到最末的位置可以確定」 。

  • 第二次同樣從開始起向后判斷著前進(jìn),如果當(dāng)前位置比后面一個(gè)位置更大的那么就和他后面的那個(gè)數(shù)交換。但是有點(diǎn)注意的是,這次并不需要判斷到最后,只需要判斷到倒數(shù)第二個(gè)位置就行(因?yàn)榈谝淮挝覀円呀?jīng)確定最大的在倒數(shù)第一,這次的目的是確定倒數(shù)第二)

  • 同理,后面的遍歷長度每次減一,直到第一個(gè)元素使得整個(gè)元素有序。

例如 2 5 3 1 4 排序過程如下:

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)代碼為:

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;       }     }   } }

快速排序

快速排序是對冒泡排序的一種改進(jìn),采用遞歸分治的方法進(jìn)行求解。而快排相比冒泡是一種不穩(wěn)定排序,時(shí)間復(fù)雜度最壞是O(n^2),平均時(shí)間復(fù)雜度為O(nlogn),最好情況的時(shí)間復(fù)雜度為O(nlogn)。

對于快排來說, 「基本思想」 是這樣的

  • 快排需要將序列變成兩個(gè)部分,就是 「序列左邊全部小于一個(gè)數(shù)」 , 「序列右面全部大于一個(gè)數(shù)」 ,然后利用遞歸的思想再將左序列當(dāng)成一個(gè)完整的序列再進(jìn)行排序,同樣把序列的右側(cè)也當(dāng)成一個(gè)完整的序列進(jìn)行排序。

  • 其中這個(gè)數(shù)在這個(gè)序列中是可以隨機(jī)取的,可以取最左邊,可以取最右邊,當(dāng)然也可以取隨機(jī)數(shù)。但是 「通?!?/strong> 不優(yōu)化情況我們?nèi)∽钭筮叺哪莻€(gè)數(shù)。

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)代碼為:

public void quicksort(int [] a,int left,int right) {   int low=left;   int high=right;   //下面兩句的順序一定不能混,否則會(huì)產(chǎn)生數(shù)組越界!!!very important!?。?nbsp;  if(low>high)//作為判斷是否截止條件     return;   int k=a[low];//額外空間k,取最左側(cè)的一個(gè)作為衡量,最后要求左側(cè)都比它小,右側(cè)都比它大。   while(low<high)//這一輪要求把左側(cè)小于a[low],右側(cè)大于a[low]。   {     while(low<high&&a[high]>=k)//右側(cè)找到第一個(gè)小于k的停止     {       high--;     }     //這樣就找到第一個(gè)比它小的了     a[low]=a[high];//放到low位置     while(low<high&&a[low]<=k)//在low往右找到第一個(gè)大于k的,放到右側(cè)a[high]位置     {       low++;     }     a[high]=a[low];      }   a[low]=k;//賦值然后左右遞歸分治求之   quicksort(a, left, low-1);   quicksort(a, low+1, right);   }

插入類排序

直接插入排序

直接插入排序在所有排序算法中的是最簡單排序方式之一。和我們上學(xué)時(shí)候 從前往后、按高矮順序排序,那么一堆高低無序的人群中,從第一個(gè)開始,如果前面有比自己高的,就直接插入到合適的位置。 「一直到隊(duì)伍的最后一個(gè)完成插入」 整個(gè)隊(duì)列才能滿足有序。

直接插入排序遍歷比較時(shí)間復(fù)雜度是每次O(n),交換的時(shí)間復(fù)雜度每次也是O(n),那么n次總共的時(shí)間復(fù)雜度就是O(n^2)。有人會(huì)問折半(二分)插入能否優(yōu)化成O(nlogn),答案是不能的。因?yàn)槎种荒軠p少查找復(fù)雜度每次為O(logn),而插入的時(shí)間復(fù)雜度每次為O(n)級(jí)別,這樣總的時(shí)間復(fù)雜度級(jí)別還是O(n^2).

插入排序的具體步驟:

  • 選取當(dāng)前位置(當(dāng)前位置前面已經(jīng)有序) 目標(biāo)就是將當(dāng)前位置數(shù)據(jù)插入到前面合適位置。

  • 向前枚舉或者二分查找,找到待插入的位置。

  • 移動(dòng)數(shù)組,賦值交換,達(dá)到插入效果。

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)代碼為:

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;       }     }   }  }

希爾排序

直接插入排序因?yàn)槭荗(n^2),在數(shù)據(jù)量很大或者數(shù)據(jù)移動(dòng)位次太多會(huì)導(dǎo)致效率太低。很多排序都會(huì)想辦法拆分序列,然后組合,希爾排序就是以一種特殊的方式進(jìn)行預(yù)處理,考慮到了 「數(shù)據(jù)量和有序性」 兩個(gè)方面緯度來設(shè)計(jì)算法。使得序列前后之間小的盡量在前面,大的盡量在后面,進(jìn)行若干次的分組別計(jì)算,最后一組即是一趟完整的直接插入排序。

對于一個(gè) 長串 ,希爾首先將序列分割(非線性分割)而是 「按照某個(gè)數(shù)模」 ( 取余 這個(gè)類似報(bào)數(shù)1、2、3、4。1、2、3、4)這樣形式上在一組的分割先 「各組分別進(jìn)行直接插入排序」 ,這樣 「很小的數(shù)在后面」 可以通過 「較少的次數(shù)移動(dòng)到相對靠前」 的位置。然后慢慢合并變長,再稍稍移動(dòng)。

因?yàn)槊看芜@樣插入都會(huì)使得序列變得更加有序,稍微有序序列執(zhí)行直接插入排序成本并不高。所以這樣能夠在合并到最終的時(shí)候基本小的在前,大的在后,代價(jià)越來越小。這樣希爾排序相比插入排序還是能節(jié)省不少時(shí)間的。

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)代碼為:

public void shellsort (int a[]) {   int d=a.length;   int team=0;//臨時(shí)變量   for(;d>=1;d/=2)//共分成d組     for(int i=d;i<a.length;i++)//到那個(gè)元素就看這個(gè)元素在的那個(gè)組即可     {       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)是一種簡單直觀的排序算法。它的工作原理:首先在未排序序列中找到最?。ù螅┰?,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?,然后放到 「已排序序列的末尾」 。以此類推,直到所有元素均排序完畢。

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)代碼為:

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個(gè)位置進(jìn)行交換     }   } } private void swap(int[] arr, int i, int j) {   int temp = arr[i];   arr[i] = arr[j];   arr[j] = temp; }

對于堆排序,首先是建立在堆的基礎(chǔ)上,堆是一棵完全二叉樹,還要先認(rèn)識(shí)下大根堆和小根堆,完全二叉樹中所有節(jié)點(diǎn)均大于(或小于)它的孩子節(jié)點(diǎn),所以這里就分為兩種情況

  • 如果所有節(jié)點(diǎn) 「大于」 孩子節(jié)點(diǎn)值,那么這個(gè)堆叫做 「大根堆」 ,堆的最大值在根節(jié)點(diǎn)。

  • 如果所有節(jié)點(diǎn) 「小于」 孩子節(jié)點(diǎn)值,那么這個(gè)堆叫做 「小根堆」 ,堆的最小值在根節(jié)點(diǎn)。

程序員必知必會(huì)的排序算法有哪些

堆排序首先就是 「建堆」 ,然后再是調(diào)整。對于二叉樹(數(shù)組表示),我們從下往上進(jìn)行調(diào)整,從 「第一個(gè)非葉子節(jié)點(diǎn)」 開始向前調(diào)整,對于調(diào)整的規(guī)則如下:

建堆是一個(gè)O(n)的時(shí)間復(fù)雜度過程,建堆完成后就需要進(jìn)行刪除頭排序。給定數(shù)組建堆(creatHeap)

①從第一個(gè)非葉子節(jié)點(diǎn)開始判斷交換下移(shiftDown),使得當(dāng)前節(jié)點(diǎn)和子孩子能夠保持堆的性質(zhì)

②但是普通節(jié)點(diǎn)替換可能沒問題,對如果交換打破子孩子堆結(jié)構(gòu)性質(zhì),那么就要重新下移(shiftDown)被交換的節(jié)點(diǎn)一直到停止。

程序員必知必會(huì)的排序算法有哪些

堆構(gòu)造完成,取第一個(gè)堆頂元素為最小(最大),剩下左右孩子依然滿足堆的性值,但是缺個(gè)堆頂元素,如果給孩子調(diào)上來,可能會(huì)調(diào)動(dòng)太多并且可能破壞堆結(jié)構(gòu)。

①所以索性把最后一個(gè)元素放到第一位。這樣只需要判斷交換下移(shiftDown),不過需要注意此時(shí)整個(gè)堆的大小已經(jīng)發(fā)生了變化,我們在邏輯上不會(huì)使用被拋棄的位置,所以在設(shè)計(jì)函數(shù)的時(shí)候需要附帶一個(gè)堆大小的參數(shù)。

②重復(fù)以上操作,一直堆中所有元素都被取得停止。

程序員必知必會(huì)的排序算法有哪些

而堆算法復(fù)雜度的分析上,之前建堆時(shí)間復(fù)雜度是O(n)。而每次刪除堆頂然后需要向下交換,每個(gè)個(gè)數(shù)最壞為logn個(gè)。這樣復(fù)雜度就為O(nlogn).總的時(shí)間復(fù)雜度為O(n)+O(nlogn)=O(nlogn).

實(shí)現(xiàn)代碼為:

static void swap(int arr[],int m,int n) {   int team=arr[m];   arr[m]=arr[n];   arr[n]=team; } //下移交換 把當(dāng)前節(jié)點(diǎn)有效變換成一個(gè)堆(小根) static void shiftDown(int arr[],int index,int len)//0 號(hào)位置不用 {   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])//右孩子在范圍內(nèi)并且應(yīng)該交換   {     swap(arr, index, rightchild);//交換節(jié)點(diǎn)值     shiftDown(arr, rightchild, len);//可能會(huì)對孩子節(jié)點(diǎn)的堆有影響,向下重構(gòu)   }   else if(arr[leftchild]<arr[index])//交換左孩子   {     swap(arr, index, leftchild);     shiftDown(arr, leftchild, len);   } } //將數(shù)組創(chuàng)建成堆 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("原始數(shù)組為         :"+Arrays.toString(arr));   int val[]=new int[arr.length]; //臨時(shí)儲(chǔ)存結(jié)果   //step1建堆   creatHeap(arr);   System.out.println("建堆后的序列為  :"+Arrays.toString(arr));   //step2 進(jìn)行n次取值建堆,每次取堆頂元素放到val數(shù)組中,最終結(jié)果即為一個(gè)遞增排序的序列   for(int i=0;i<arr.length;i++)   {     val[i]=arr[0];//將堆頂放入結(jié)果中     arr[0]=arr[arr.length-1-i];//刪除堆頂元素,將末尾元素放到堆頂     shiftDown(arr, 0, arr.length-i);//將這個(gè)堆調(diào)整為合法的小根堆,注意(邏輯上的)長度有變化   }   //數(shù)值克隆復(fù)制   for(int i=0;i<arr.length;i++)   {     arr[i]=val[i];   }   System.out.println("堆排序后的序列為:"+Arrays.toString(arr));  }

歸并類排序

在歸并類排序一般只講歸并排序,但是歸并排序也分二路歸并、多路歸并,這里就講較多的二路歸并排序,且用遞歸方式實(shí)現(xiàn)。

歸并排序

歸并和快排都是 「基于分治算法」 的,分治算法其實(shí)應(yīng)用挺多的,很多分治會(huì)用到遞歸,但事實(shí)上 「分治和遞歸是兩把事」 。分治就是分而治之,可以采用遞歸實(shí)現(xiàn),也可以自己遍歷實(shí)現(xiàn)非遞歸方式。而歸并排序就是先將問題分解成代價(jià)較小的子問題,子問題再采取代價(jià)較小的合并方式完成一個(gè)排序。

至于歸并的思想是這樣的:

  • 第一次:整串先進(jìn)行劃分成一個(gè)一個(gè)單獨(dú),第一次是將序列中( 1 2 3 4 5 6--- )兩兩歸并成有序,歸并完( xx xx xx xx---- )這樣局部有序的序列。

  • 第二次就是兩兩歸并成若干四個(gè)( 1 2 3 4 5 6 7 8 ---- ) 「每個(gè)小局部是有序的」 。

  • 就這樣一直到最后這個(gè)串串只剩一個(gè),然而這個(gè)耗費(fèi)的總次數(shù)logn。每次操作的時(shí)間復(fù)雜的又是 O(n) 。所以總共的時(shí)間復(fù)雜度為 O(nlogn) .

程序員必知必會(huì)的排序算法有哪些

合并為一個(gè)O(n)的過程:

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xià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)//當(dāng)一個(gè)越界后剩余按序列添加即可   {     team[teamindex++]=array[lindex++];    }   while(rindex<=r)   {     team[teamindex++]=array[rindex++];   }    for(int i=0;i<teamindex;i++)   {     array[l+i]=team[i];   }  }

桶類排序

桶排序是一種用空間換取時(shí)間的排序,桶排序重要的是它的思想,而不是具體實(shí)現(xiàn),時(shí)間復(fù)雜度最好可能是線性O(shè)(n),桶排序不是基于比較的排序而是一種分配式的。桶排序從字面的意思上看:

  • 桶:若干個(gè)桶,說明此類排序?qū)?shù)據(jù)放入若干個(gè)桶中。

  • 桶:每個(gè)桶有容量,桶是有一定容積的容器,所以每個(gè)桶中可能有多個(gè)元素。

  • 桶:從整體來看,整個(gè)排序更希望桶能夠更勻稱,即既不溢出(太多)又不太少。

桶排序的思想為: 「將待排序的序列分到若干個(gè)桶中,每個(gè)桶內(nèi)的元素再進(jìn)行個(gè)別排序。」 當(dāng)然桶排序選擇的方案跟具體的數(shù)據(jù)有關(guān)系,桶排序是一個(gè)比較廣泛的概念,并且計(jì)數(shù)排序是一種特殊的桶排序,基數(shù)排序也是建立在桶排序的基礎(chǔ)上。在數(shù)據(jù)分布均勻且每個(gè)桶元素趨近一個(gè)時(shí)間復(fù)雜度能達(dá)到O(n),但是如果數(shù)據(jù)范圍較大且相對集中就不太適合使用桶排序。

程序員必知必會(huì)的排序算法有哪些

實(shí)現(xiàn)一個(gè)簡單桶排序:

import java.util.ArrayList; import java.util.List; //微信公眾號(hào):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++)//將待排序序列放入對應(yīng)桶中   {    int index=a[i]/10;//對應(yīng)的桶號(hào)    buckets[index].add(a[i]);   }   for(int i=0;i<buckets.length;i++)//每個(gè)桶內(nèi)進(jìn)行排序(使用系統(tǒng)自帶快排)   {    buckets[i].sort(null);    for(int j=0;j<buckets[i].size();j++)//順便打印輸出    {     System.out.print(buckets[i].get(j)+" ");    }   }   } }

計(jì)數(shù)排序

計(jì)數(shù)排序是一種特殊的桶排序,每個(gè)桶的大小為1,每個(gè)桶不在用List表示,而通常用一個(gè)值用來計(jì)數(shù)。

在 「設(shè)計(jì)具體算法的時(shí)候」 ,先找到最小值min,再找最大值max。然后創(chuàng)建這個(gè)區(qū)間大小的數(shù)組,從min的位置開始計(jì)數(shù),這樣就可以最大程度的壓縮空間,提高空間的使用效率。

程序員必知必會(huì)的排序算法有哪些
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];//對元素進(jìn)行計(jì)數(shù)   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才是真正值     }   } }

基數(shù)排序

基數(shù)排序是一種很容易理解但是比較難實(shí)現(xiàn)(優(yōu)化)的算法?;鶖?shù)排序也稱為卡片排序,基數(shù)排序的原理就是多次利用計(jì)數(shù)排序(計(jì)數(shù)排序是一種特殊的桶排序),但是和前面的普通桶排序和計(jì)數(shù)排序有所區(qū)別的是, 「基數(shù)排序并不是將一個(gè)整體分配到一個(gè)桶中」 ,而是將自身拆分成一個(gè)個(gè)組成的元素,每個(gè)元素分別順序分配放入桶中、順序收集,當(dāng)從前往后或者從后往前每個(gè)位置都進(jìn)行過這樣順序的分配、收集后,就獲得了一個(gè)有序的數(shù)列。

程序員必知必會(huì)的排序算法有哪些

如果是數(shù)字類型排序,那么這個(gè)桶只需要裝0-9大小的數(shù)字,但是如果是字符類型,那么就需要注意ASCII的范圍。

所以遇到這種情況我們基數(shù)排序思想很簡單,就拿 934,241,3366,4399這幾個(gè)數(shù)字進(jìn)行基數(shù)排序的一趟過程來看,第一次會(huì)根據(jù)各位進(jìn)行分配、收集:

程序員必知必會(huì)的排序算法有哪些

分配和收集都是有序的,第二次會(huì)根據(jù)十位進(jìn)行分配、收集,此次是在第一次個(gè)位分配、收集基礎(chǔ)上進(jìn)行的,所以所有數(shù)字單看個(gè)位十位是有序的。

程序員必知必會(huì)的排序算法有哪些

而第三次就是對百位進(jìn)行分配收集,此次完成之后百位及其以下是有序的。

程序員必知必會(huì)的排序算法有哪些

而最后一次的時(shí)候進(jìn)行處理的時(shí)候,千位有的數(shù)字需要補(bǔ)零,這次完畢后后千位及以后都有序,即整個(gè)序列排序完成。

程序員必知必會(huì)的排序算法有哪些

簡單實(shí)現(xiàn)代碼為:

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;//假設(shè)都是正數(shù)   for(int i=0;i<arr.length;i++)   {     if(arr[i]>max)       max=arr[i];   }   int divideNum=1;//1 10 100 100&hellip;&hellip;用來求對應(yīng)位的數(shù)字   while (max>0) {//max 和num 控制     for(int num:arr)     {       bucket[(num/divideNum)%10].add(num);//分配 將對應(yīng)位置的數(shù)字放到對應(yīng)bucket中     }     divideNum*=10;     max/=10;     int idx=0;     //收集 重新?lián)炱饠?shù)據(jù)     for(List<Integer>list:bucket)     {       for(int num:list)       {         arr[idx++]=num;       }       list.clear();//收集完需要清空留下次繼續(xù)使用     }   } }

當(dāng)然,基數(shù)排序還有字符串等長、不等長、一維數(shù)組優(yōu)化等各種實(shí)現(xiàn)需要需學(xué)習(xí),具體可以參考公眾號(hào)內(nèi)其他文章。

本次十大排序就這么瀟灑的過了一遍,我想大家都應(yīng)該有所領(lǐng)悟了吧!對于算法總結(jié),避免不必要的勞動(dòng)力,我分享這個(gè)表格給大家:

排序算法平均時(shí)間復(fù)雜度最好最壞空間復(fù)雜度穩(wěn)定性
冒泡排序O(n^2)O(n)O(n^2)O(1)穩(wěn)定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)不穩(wěn)定
插入排序O(n^2)O(n)O(n^2)O(1)穩(wěn)定
希爾排序O(n^1.3)O(n)O(nlog2n)O(1)不穩(wěn)定
選擇排序O(n^2)O(n^2)O(n^2)O(1)不穩(wěn)定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不穩(wěn)定
歸并排序O(nlogn)O(nlogn)O(nlogn)O(n)穩(wěn)定
桶排序O(n+k)O(n+k)O(n+k)O(n+k)穩(wěn)定
計(jì)數(shù)排序O(n+k)O(n+k)O(n+k)O(k)穩(wěn)定
基數(shù)排序O(n*k)O(n*k)O(n*k)O(n+k)穩(wěn)定

到此,關(guān)于“程序員必知必會(huì)的排序算法有哪些”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI