-
1 # 小嘟嘟熊
-
2 # 嵌入式IOT圈
一、排序演算法介紹：
排序演算法的效能主要是受 3 個方面影響:1.時間效能排序是資料處理中經常執行的一種操作，往往屬於系統的核心部分，因此排序演算法的時間開銷是衡量其好壞的最重要的標誌。在內排序中，主要進行兩種操作:比較和移動 。 比較指關鍵字之間的比較，這是要做排序最起碼的操作。 移動指記錄從一個位置移動到另一個位置，事實上，移動可以透過改變記錄的儲存方式來予以避免(這個我們在講解具體的演算法時再談)。總之，高效率的內排序演算法應該是具有儘可能少的關鍵字比較次數和儘可能少的記錄移動次數。2. 輔助空間評價排序演算法的另一個主要標準是執行演算法所需要的輔助儲存空間。輔助儲存空間是除了存放待排序所佔用的儲存空間之外，執行演算法所需要的其他儲存空間 。3 . 演算法的複雜性注意這裡指的是演算法本身的複雜度，而不是指演算法的時間複雜度。顯然演算法過於複雜也會影響排序的效能。根據排序過程中藉助的主要操作，我們把內排序分為:插入排序、交換排序、選擇排序和周並排序。 可以說，這些都是比較成熟的排序技術，已經被廣泛地應用於許許多多的程式語言或資料庫當中，甚至2們都已經封裝了關於排序演算法的實現程式碼。因此，我們學習這些排序演算法的目的更多並不是為了去在現實中編
程排序演算法，而是透過學習來提高我們編寫演算法的能力，以便於去解決更多複雜和靈活的應用性問題。
二、排序演算法種類：
(1) 氣泡排序 (Bubble Sort) 一種交換排序，宮的基本思想是:兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止.
/ *對順序表 L 作交換排序
void BubbleSortO (SqList *L )
{
int i , j;
for ({i=1; i < L->length; i++)
{
for (j=i+1;j <= L->length; j++)
{
if ( L->r [i] > L->r [j] )
{
swap (L ,i ,j); /*交換L->r[i]與 L->r[jl 的值*/
}
}
}
}
(2) 簡單選擇排序法 (Simple Selection Sort) 就是透過 n - i 次關鍵字間的比較，從n- j + 1 個記錄中選出關鍵字最小的記錄，並和第 i ( 1 < i <;n) 個記錄交換之。/*對順序表在 L 作簡單選擇排序*/void SelectSort (SqList *L){
int i,j,min; for (i=1 ;i<L->length; i++) {
min = i; for (j=i+1;j<=L->lenqth;j++) {
if (L->r [min] > L->r[j] )
min = j;
}
if( i != min) swap ( L, i , min) ; /*交換 L->r[i]與 L->r [min]的值*/}
}
(3) 直接插入排序(Straight Insertion Sort) 的基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增 1 的有序襲。顧名思義，從名稱上也可以知道它是一種插入排序的方法。我們來看直接插入排序法的程式碼。
/*對順序表 L 作直接插入排序 */
void InsertSort (SqList *L )
{
int i , j ;
for (i=2 ; i<-L->Length ; i++)
{
if (L->r[i] < L->r [i-1] )
{
L->[0] = L->r[i];
for (j=i-L ;L->r [j]>L->r[0]; j -- )
L->r[j+i]=L->r(j);
L->r[j+1]=L->r[0];
}
}
}
(4) 堆排序 (Heap Sort) 就是利用堆(假設利用大頂堆)進行排序的方法。它的基本思想是， 將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根結點。將官移走(其實就是將其與堆陣列的末尾元素交換，此時末尾元素就是最大值) .然後將剩餘的 n - 1 個序列重新構造成一個堆，這樣就劊尋到 n 個元素中的次小值。如此反覆執行， 便能得到一個有序序列了。
/"對順序表L進行堆排序*/
void HeapSort (SqList * L)
{
int i;
for (i=L-> Lenqth/2;i>0; i-- )
HeapAdjust(L, i , L-> Length) ;
for ( i=L-> Length; i>1; i- - )
{
swap (L ，1 ， i) ; /*呼叫交換函式*/
HeapAdjust (L, 1 , i-1); /*將 L→ r[1. .i- 1]，重新調整為大頂堆 */
}
}
(5) 快速排序 ( Quick Sort) 的基本思想是:透過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序目的。
/*對順序表 L 作快速排序*/
void QuickSort (SqList *L)
{
QSort ( L, 1,L->length) ;
}
//程式碼 QSort 的實現。
void QSort ( SqList *L,int Low,int high)
{
int pivot ;
if (Low<high )
{
p i vot=Parti tion (L, low, higb) ;
QSort (L, low,pivot- 1) ;
QSort (L, pivot+1 , high) ;
}
}
總結：以上就是基本的排序演算法，當然後面深層次的演算法也是基本演算法衍生的。學習演算法的基本思想就是要理解演算法的本質。
回覆列表
排序看情況，比如1到10個亂順序數，定義一個帶10個元素臨時陣列，把相應的值寫入相應的元素中，這種方法只需要一次就解決了，再比如50個亂數，其中最大是100，也可以建立下標100的陣列，迴圈原陣列把相應的值寫到相應的元素中，也只需要一次，然後把沒賦過值的刪除，我曾經試過用8w個數組做實驗，這個方法比冒泡快很多