第九章 內部排序?

排序:重點在于對于記錄的關鍵字進行排序,得到按關鍵字有序記錄序列
分為:
?? ?A.內部排序: 排序過程在內存中進行?
?? ?B.外部排序: 待排序記錄數據量過大,需要借助外部存儲設備
排序的穩定性:排序后有相同關鍵字的記錄順序不變就是穩定的排序

插入類排序:
1.直接插入排序:將新加入的記錄的關鍵字與之前的記錄關鍵字從后往前比較,
?? ??? ??? ? ? 若較小,則向前比較,同時進行比較的記錄后移一個位置,直到找到小于等于的關鍵字,插入在其后.?

實例代碼如下:?

void InsSort(int r[], int length){//r可以設置為結構數組,這里認為是數組 int i,j;for(i = 2; i < length; i++){ // i=2開始,i=1為第一個元素,認為是子表,i=0設置為監視哨 r[0] = r[i];//將待插入記錄存到監視哨中,臨時保存 j = i - 1; //i為初始待插入記錄位置,i-1為需要比較的記錄位置while(r[0] < r[j]){r[j+1] = r[j];j--;} r[j+1] = r[0];} }

優點:算法簡單,適用于記錄數目較少且基本有序
時間復雜度:O(n^2).

2.折半插入排序:類似于快排

示例代碼如下:

void BinSort(int r[], int length){int i, x, j;int low, high, mid;for(i = 2;i <= length; i++){x = r[i];low = 1;high = i - 1;while(low < high){//Attention!不取等,書上是錯的 mid = (low + high) / 2;if(x < r[mid])high = mid - 1;elselow = mid + 1;}for(j = i - 1; j >= low; j--)r[j+1] = r[j];r[low] = x; } }

時間復雜度:O(n^2).
需要比較的次數最大為其折半判定樹的深度log2(n)

3.希爾排序:排序結果,基本有序;又稱縮小增量排序;將關鍵字序列分為若干個子序列,對子序列插入排序

void f1(int r[], int length, int d){//d為這一輪子序列長度(增量) int i, j;for(i = 1+d; i <= length; i++){if(r[i] < r[i-d]){r[0] = r[i];for(j = i - d; j > 0 && r[j] > r[0]; j -= d){r[j + d] = r[j];}//如果子序列后者的記錄關鍵字比前小,就復制前者到后者 r[j + d] = r[0];//復制要交換的一個到適合的位置 }} } void f2(int r[], int length, int d[], int n){for(i = 0; i < n; i++)//d[]為增量數組,n為該數組長度 d[n-1] == 1; f1(r, length, d[i]); }

時間復雜度:O(n^1.5).
算法不是穩定的 .

交換類排序:

1.冒泡排序(相鄰比序法):反復掃描記錄序列,依次交換逆序記錄的位置

void BubbleSort(int r[], int n){bool change = true;int i,j;int x = 0;for(i = 1; i < n && change; i++){change = false;for(j = 1; j <= n - i; j++){if(r[j]>r[j+1]){x = r[j];r[j] = r[j+1];r[j+1] = x;change = true;}}} } //下面這種簡單些:上升法,不帶標記 void BubbleSort(int r[], int n){int i, j, k;for(i = 0; i < n; i++){for(j = n - 2; j >= i; j--){if(r[j] > r[j+1]){k = r[j];r[j] = r[j+1];r[j+1] = k;}}} }時間的復雜度:O(n^2).

2.快排:原理:一次性可以消除多個逆序來減少耗費時間
找到一個劃分元,關鍵字小的移到前面,大的移到后面,遞歸在子序列中找出劃分元.直到子表長度小于等于1

void QKSort(int r[], int low. int high){if(low < high){pos = QKPass(r, low, high);//再次快排QKSort(r, low, pos -1);QKSort(r, pos +1, high); } } 一趟快速排序算法: int QKPass(int r[], int low, int high){int x;while(low < high){while(low < high && r[high] > x)high--;if(low < high){r[low] = r[high];low++;} while(low < high && r[low] < x)low++;if(low < high){r[high] = r[low];high--;} }r[low] = x;return low; } 時間復雜度:O(nlog2(n))

?

總結

以上是生活随笔為你收集整理的数据结构-第九章 内部排序-知识点总结1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。