下面是范文網(wǎng)小編整理的排序算法的算法思想和使用場景總結(jié)共3篇(快速排序算法應(yīng)用場景)，供大家品鑒。
排序算法的算法思想和使用場景總結(jié)共1
一、冒泡排序
已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數(shù)據(jù)中最大的。再對a[1]~a[n- 1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1輪后a[1]、a[2]、……a[n]就以升序排列了。
優(yōu)點：穩(wěn)定；
缺點：慢，每次只能移動相鄰兩個數(shù)據(jù)。
二、選擇排序
每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。
選擇排序是不穩(wěn)定的排序方法。
n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。
②第1趟排序
在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。
……
③第i趟排序
第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。
這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。
優(yōu)點：移動數(shù)據(jù)的次數(shù)已知（n-1次）；
缺點：比較次數(shù)多。
三、插入排序
已知一組升序排列數(shù)據(jù)a[1]、a[2]、……a[n]，一組無序數(shù)據(jù)b[1]、 b[2]、……b[m]，需將二者合并成一個升序數(shù)列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大于a[2]，則繼續(xù)跳過，直到b[1]小于a數(shù)組中某一數(shù)據(jù)a[x]，則將a[x]~a[n]分別向后移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數(shù)組a，可將b[1]當(dāng)作n=1的數(shù)組a）
優(yōu)點：穩(wěn)定，快；
缺點：比較次數(shù)不一定，比較次數(shù)越少，插入點后的數(shù)據(jù)移動越多，特別是當(dāng)數(shù)據(jù)總量龐大的時候，但用鏈表可以解決這個問題。
四、縮小增量排序
由希爾在1959年提出，又稱希爾排序(shell排序)。
已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。發(fā)現(xiàn)當(dāng)n不大時，插入 排序的效果很好。首先取一增量d(d 優(yōu)點：快，數(shù)據(jù)移動少； 缺點：不穩(wěn)定，d的取值是多少，應(yīng)取多少個不同的值，都無法確切知道，只能憑經(jīng)驗來取。 五、快速排序 快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。 已知一組無序數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數(shù)據(jù)a[x] 作為基準(zhǔn)。比較a[x]與其它數(shù)據(jù)并排序，使a[x]排在數(shù)據(jù)的第k位，并且使a[1]~a[k-1]中的每一個數(shù) 據(jù)a[x]，然后采用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數(shù)據(jù)進行快速排序。 優(yōu)點：極快，數(shù)據(jù)移動少； 缺點：不穩(wěn)定。 六、箱排序 已知一組無序正整數(shù)數(shù)據(jù)a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數(shù)組x[m],且m>=a[1]、a[2]、……a[n]，接著循環(huán)n次，每次x[a]++. 優(yōu)點：快，效率達(dá)到O(1) 缺點：數(shù)據(jù)范圍必須為正整數(shù)并且比較小 六、歸并排序 歸并排序是多次將兩個或兩個以上的有序表合并成一個新的有序表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。 歸并排序是穩(wěn)定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關(guān)鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數(shù)據(jù)包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優(yōu)勢的地方. 歸并排序：歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸并，將有無比的優(yōu)勢。其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數(shù)據(jù)的有序性不敏感。若數(shù)據(jù)節(jié)點數(shù)據(jù)量大，那將不適合。但可改造成索引操作，效果將非常出色。 堆排序：由于它在直接選擇排序的基礎(chǔ)上利用了比較結(jié)果形成。效率提高很大。它完成排序的總比較次數(shù)為O(nlog2n)。它是對數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰鰞蓚€步驟：－是建堆，二是排序（調(diào)整堆）。所以一般在小規(guī)模的序列中不合適，但對于較大的序列，將表現(xiàn)出優(yōu)越的性能。 排序算法總結(jié) 所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。當(dāng)待排序記錄的關(guān)鍵字都不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。 在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。 要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。 一.插入排序 插入排序的基本思想是每步將一個待排序的記錄按其排序碼值的大小，插到前面已經(jīng)排好的文件中的適當(dāng)位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。 ①.直接插入排序(穩(wěn)定) 接插入排序的過程為：在插入第i個記錄時，R1,R2,..Ri-1已經(jīng)排好序，將第i個記錄的排序碼Ki依次和R1,R2,..,Ri-1的排序碼逐個進行比較，找到適當(dāng)?shù)奈恢谩Ｊ褂弥苯硬迦肱判?，對于具有n個記錄的文件，要進行n-1趟排序。 代碼如下: void Dir_Insert(int A[],int N) //直接插入排序 { int j,t; for(int i=1;i 1 ②.希爾排序(不穩(wěn)定)： 希爾(Shell)排序的基本思想是：先取一個小于n的整數(shù)d1作為第一個增量把文件的全部記錄分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取得第二個增量d2 一般取d1=n/2，di+1=di/2。如果結(jié)果為偶數(shù)，則加1，保證di為奇數(shù)。 希爾排序是不穩(wěn)定的，希爾排序的執(zhí)行時間依賴于增量序列，其平均時間復(fù)雜度為O(n^). 代碼如下: void Shell(int A[],int n) //Shell排序 { int i,j,k,t; (n/2)%2 == 0 ? k = n/2+1 : k = n/2; //保證增量為奇數(shù) while(k > 0) { for(j=k;j 二.選擇排序 選擇排序的基本思想是每步從待排序的記錄中選出排序碼最小的記錄，順序存放在已排序的記錄序列的后面，直到全部排完。選擇排序中主要使用直接選擇排序和堆排 2 序。 ①.直接選擇排序(不穩(wěn)定) 直接選擇排序的過程是：首先在所有記錄中選出序碼最小的記錄，把它與第1個記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個記錄交換......依次類推，直到所有記錄排完為止。 無論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需要做n-i次比較，因此，總的比較次數(shù)為n(n-1)/2=O(n^2)。當(dāng)初始文件為正序時，移動次數(shù)為0；文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數(shù)取最大值3(n-1)。直接選擇排序的平均時間復(fù)雜度為O(n^2)。直接選擇排序是不穩(wěn)定的。 代碼如下: void Dir_Choose(int A[],int n) //直接選擇排序 { int k,t; for(int i=0;i 堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。n個關(guān)鍵字序列 K1,K2,...,Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根結(jié)點(堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者，稱為小根堆；根結(jié)點的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。 3 若將此序列所存儲的向量R[1..n]看作是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。 堆排序的關(guān)鍵步驟有兩個：一是如何建立初始堆；二是當(dāng)堆的根結(jié)點與堆的最后一個結(jié)點交換后，如何對少了一個結(jié)點后的結(jié)點序列做調(diào)整，使之重新成為堆。堆排序的最壞時間復(fù)雜度為O(nlog2n),堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較 次數(shù)較多，所以堆排序不適宜于記錄較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。 代碼略.. 三.交換排序 交換排序的基本思想是：兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那寫偶對，直到滿足條件為止。交換排序的主要方法有冒泡排序和快速排序. ①.冒泡排序(穩(wěn)定的) 冒泡排序?qū)⒈慌判虻挠涗洈?shù)組R[1..n]垂直排列，每個記錄R[i]看作是重量為ki的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R；凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。 冒泡排序的具體過程如下： 第一步，先比較k1和k2，若k1>k2，則交換k1和k2所在的記錄，否則不交換。繼續(xù)對k2和k3重復(fù)上述過程，直到處理完kn-1和kn。這時最大的排序碼記錄轉(zhuǎn)到了最后位置，稱第1次起泡，共執(zhí)行n-1次比較。 與第一步類似，從k1和k2開始比較，到kn-2和kn-1為止，共執(zhí)行n-2次比較。 依次類推，共做n-1次起泡，完成整個排序過程。 若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需關(guān)鍵字比較次數(shù)為n-1次，記錄移動次數(shù)為0。因此，冒泡排序最好的時間復(fù)雜度為O(n)。 若初始文件是反序的，需要進行n-1趟排序。每趟排序要進行n-i次關(guān)鍵字的比較(1<=i<=n-1),且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較次數(shù)達(dá)到最大值n(n-1)/2=O(n^2),移動次數(shù)也達(dá)到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最壞時間復(fù)雜度為O(n^2)。 雖然冒泡排序不一定要進行n-1趟，但由于它的記錄移動次數(shù)較多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是穩(wěn)定的。 代碼如下: 4 void QP(int A[],int n) //優(yōu)化的冒泡排序 { int count=0,t,flag; for(int i=0;i 快速排序采用了一種分治的策略，通常稱其為分治法，其基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 快速排序的具體過程如下： 第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準(zhǔn)，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2組各記錄的排序碼都大于該排序碼，并把該記錄排在這兩組中間。 第二步，采用同樣的方法，對左邊的組和右邊的組進行排序，直到所有記錄都排到相應(yīng)的位置為止。 代碼如下: void Quick_Sort(int A[],int low,int high) //low和high是數(shù)組的下標(biāo) { if(low 5 { int temp,t=A[low]; int l=low,h=high; while(l 四.歸并排序 歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。初始時，把含有n個結(jié)點的待排序序列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸并得到長度為2的若干有序子表，再對它們兩兩合并。直到得到長度為n的有序表，排序結(jié)束。 歸并排序是一種穩(wěn)定的排序，可用順序存儲結(jié)構(gòu)，也易于在鏈表上實現(xiàn)，對長度為n的文件，需進行l(wèi)og2n趟二路歸并，每趟歸并的時間為O(n),故其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。歸并排序需要一個輔助向量來暫存兩個有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為O(n),顯然它不是就地排序。 代碼略... 五.基數(shù)排序 設(shè)單關(guān)鍵字的每個分量的取值范圍均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值個數(shù)rd稱為基數(shù)．基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異． (1).若關(guān)鍵字是十進制整數(shù)，則按個、十等位進行分解，基數(shù)rd=10,C0=0,C9=9,d為最長整數(shù)的位數(shù)． (2).若關(guān)鍵字是小寫的英文字符串，則rd=26,C0='a',C25='z',d為最長字符串的長度． 基數(shù)排序的基本思想是：從低位到高位依次對待排序的關(guān)鍵碼進行分配和收集，經(jīng)過d趟分配和收集，就可以得到一個有序序列． 按平均時間將排序分為四類： （1）平方階(O(n2))排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序； （2）線性對數(shù)階(O(nlgn))排序 如快速、堆和歸并排序； （3）O(n1+￡)階排序 ￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序； （4）線性階(O(n))排序 如基數(shù)排序。 各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時，直接插入和冒泡均最佳。 影響排序效果的因素 因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素： ①待排序的記錄數(shù)目n； ②記錄的大小(規(guī)模)； ③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)； ④對穩(wěn)定性的要求； ⑤語言工具的條件； ⑥存儲結(jié)構(gòu)； ⑦時間和輔助空間復(fù)雜度等。 不同條件下，排序方法的選擇 7 (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。 (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜； (3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或 歸并排序。 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短； 堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。 若要求排序穩(wěn)定，則可選用歸并排序。但從單個記錄起進行兩兩歸并的 排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進后的歸并排序仍是穩(wěn)定的。 《選擇排序》教學(xué)心得 教學(xué)內(nèi)容： 選擇排序的算法思想 選擇排序的實現(xiàn)過程 選擇排序的編碼實現(xiàn) 總結(jié)和思考：大數(shù)據(jù)背景下的排序 排序(Sort) 是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個關(guān)鍵字有序的序列。排序方法分為兩大類：一類是內(nèi)排序：冒泡排序、選擇排序、插入排序、希爾排序、交換排序、快速排序等；另一類是外排序。 從教學(xué)理念上看，本節(jié)課利用維果斯基的“最近發(fā)展區(qū)理論”，把學(xué)生的現(xiàn)有水平和興趣點，結(jié)合教學(xué)的目標(biāo)，形成最近發(fā)展區(qū)。教學(xué)著眼于學(xué)生的最近發(fā)展區(qū)，提供帶有難度的內(nèi)容，調(diào)動學(xué)生的積極性，發(fā)揮其潛能，超越其最近發(fā)展區(qū)而達(dá)到下一發(fā)展階段的水平，然后在此基礎(chǔ)上進行下一個發(fā)展區(qū)的發(fā)展。 從教學(xué)方法來看，主要使用案例分析法、講授法等，從分析當(dāng)前流行的冒泡排序算法的案例開始，由淺入深的介紹選擇排序的基本概念,算法思想以及編碼過程。 從教學(xué)過程來看，首先從回顧冒泡排序的內(nèi)容導(dǎo)入，在改進冒泡排序的過程中，提出選擇排序的概念和思想。用直觀的動畫方式展現(xiàn)選擇排序思想和過程，總結(jié)分析出關(guān)鍵代碼，引導(dǎo)學(xué)生寫出完整代碼，最后分析選擇排序的關(guān)鍵點，并提出思考，大數(shù)據(jù)背景下的排序改進方法。 在整個過程中一直都力求讓學(xué)生在已知的知識結(jié)構(gòu)中推導(dǎo)、歸納出需要掌握的知識點。但是上完課程后感覺案例還不夠多，相對于非計算機的學(xué)生來說，算法的分析比編碼的過程更加重要。所以學(xué)生感到有些難，本來已經(jīng)調(diào)動起來的積極性沒能保持到整節(jié)課。非計算機專業(yè)的學(xué)生思考計算機問題深度不夠，在以后的備課中要更多的挖掘教學(xué)案例的廣度和深度，給他們更多的思維訓(xùn)練。 排序算法的算法思想和使用場景總結(jié)共3篇(快速排序算法應(yīng)用場景)相關(guān)文章：排序算法的算法思想和使用場景總結(jié)共2
排序算法的算法思想和使用場景總結(jié)共3
相關(guān)熱詞搜索：排序算法的算法思想和使用場景總結(jié)（共5篇