排序-总结
排序?
排序:重點在于對于記錄的關鍵字進行排序,得到按關鍵字有序記錄序列
分為:
?? ?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;
?? ??? ??? ?else
?? ??? ??? ??? ?low = 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.簡單選擇排序:
直接從數組中選擇最小的記錄和第一個記錄交換位置,循環
void SelectSort(int r[], int b){
?? ?int i, j, k;
?? ?int x;
?? ?
?? ?for(i = 1; i < n; i++){
?? ??? ?k = i;
?? ??? ?for(j = i+1; j <= n; j++){
?? ??? ??? ?if(r[j] < r[k])//選擇最小的記錄,得到在數組中的位置?
?? ??? ??? ??? ?k = j;
?? ??? ?}
?? ??? ?if(k != i){
?? ??? ??? ?x = r[i];
?? ??? ??? ?r[i] = r[k];
?? ??? ??? ?r[k] = x;
?? ??? ?}//交換位置?
?? ?}
}?
時間復雜度:O(n^2).
2.樹形選擇排序(錦標賽排序):
與簡單選擇排序不同點是,占用空間更多,保留了之前的比較結果
每一個記錄看作葉子節點,兩兩比較,選出最小的為雙親,進一步遞歸向上,找出根,比較成功后,
該記錄對應的葉子節點置為無窮;
進一步兩兩比較重復上述過程,直到記錄全部輸出
時間復雜度:O(nlog2(n)).?
3.堆排序:
排序過程中把向量中儲存的數據看作一顆完全二叉樹來進行操作
重建堆:
?? ?大堆,篩選最大的元素出去,然后最后的元素補根節點,調整堆使最大的元素在最上面?
void sift(Type r[], int k, int m){
?? ?//r[k...m]是以r[k]為根的完全二叉樹,調整r[k]使之滿足堆的性質?
?? ?int i, j, t, x;
?? ?
?? ?t = r[k];
?? ?x = r[k].key;?
?? ?i = k;
?? ?j = 2 * k;//j指向t的左孩子
?? ?bool finished = false;
?? ?
?? ?while(j <= m && !finished){
?? ??? ?if(j + 1 <= m && r[j].key < r[j+1].key){
?? ??? ??? ?j++;
?? ??? ?}//得到左右孩子中記錄關鍵字較大的位置坐標?
?? ??? ?if(x >= r[j].key) //如果滿足堆的性質,上面的比孩子大?
?? ??? ??? ?finished = true;
?? ??? ?else{
?? ??? ??? ?r[i] = r[j];
?? ??? ??? ?i = j;
?? ??? ??? ?j = 2 * i;
?? ??? ?}
?? ?}?
?? ?r[i] = t;
}?
建初堆:
void crt_heap(Type r[], int n)
{
?? ?//對r[]建立堆, n為數組長度
?? ?int i;
?? ?for(i = n / 2; i >= 1; i--)//i指向最后一個非葉子節點?
?? ??? ?sift(r, i, n);?
?}?
堆排序算法:
void HeapSort(Type r[], int n)
{
?? ?crt_heap(r, n);
?? ?
?? ?for(i = n; ?i>= 2 ;--i){
?? ??? ?r[0] = r[1];
?? ??? ?r[1] = r[i];
?? ??? ?r[i] = r[0];//最后一個元素和第一個元素交換位置,把最大的換到最后面去,以此達到升序排列x?
?? ??? ?sift(r, 1, i-1);
?? ?}
?}?
時間復雜度:O(nlog2(n)).
算法是不穩定的, 空間復雜度O(1) .
歸并類排序:將兩個或兩個以上的有序表合并成一個表
兩個有序子序列合并算法:?
void Merge(Type r1[], int low, int mid, int high, Type r2[])
{
?? ?//r1[low...mid]和r1[mid+1,..high]分別按照關鍵字有序排列 ,合并存放在r2[]中
?? ?int i, j, k;
?? ?i = low;
?? ?j = mid + 1;
?? ?k = low;
?? ?
?? ?while(i <= mid && j <= high){
?? ??? ?if(r1[i].key <= r1[j].key)
?? ??? ??? ?r2[k++] = r[i++];
?? ??? ?else
?? ??? ??? ?r2[k++] = r[j++];
?? ?}
?? ?while(i <= mid){
?? ??? ?r2[k++] = r1[i++];
?? ?}
?? ?while(j <= high){
?? ??? ?r2[k++] = r1[j++];
?? ?}
?}?
路歸并排序的遞歸算法:
void MSort(Type r1[], int low, int high, Type r3[])
{
?? ?//r1[low...high]排序后放在r3[low...high] 中, r2為輔助空間
?? ?Type *r2;
?? ?int mid;
?? ?
?? ?
?? ?r2 = (Type *)malloc(sizeof(Type) * (high - low + 1));
?? ?if(low == high) r3[low] = r1[low];
?? ?//這個是遞歸最終退出條件
?? ?else{//r1前半段放到r2前半段中,同理對于后半段,再將r2合并排序?
?? ??? ?mid = (low + high) / 2;
?? ??? ?MSort(r1, low, mid, r2);
?? ??? ?MSort(r1, mid + 1, high, r2);?
?? ??? ?Merge(r2, low, mid, high, r3);
?? ?}?
?? ?free(r2);
?}?
調用:
void MergeSort(Type r[], int n){
?? ?MSort(r, 1, n, r);
}?
分配類排序:
核心是分配和收集,利用關鍵字的優先級進行排序的思想?
高位優先排序:
比如橋牌,先比較花色在比較面值;比如學號,比較級,院,班,號;
低位優先排序:
鏈式基數排序
思想:基于"分配"和"收集"的操作, 將單關鍵字轉化為多關鍵字排序
將鏈表作為存儲結構, 待排序記錄以指針相連,構成鏈表;
分配:按照關鍵字取值分配記錄到鏈隊列相應隊列中,每個隊列關鍵字取值相同
收集:按照關鍵字大小,從小到大,將隊列首尾相接連接成一個鏈表;
重復上述步驟..
定義:
//待排序記錄結點
typedef struct node{
?? ?int data;//比如說一個三位數?
?? ?struct node *next;
}TNode;
//隊列首尾指針
typedef struct{
?? ?node *front;
?? ?node *rear;
}TPointer;?
//根據數組R[](已經存在元素),構建帶頭結點待排序記錄鏈表
TNode *create_list(int R[], int n){
?? ?
?? ?TNode *p, *ph;
?? ?//p為每一個存了記錄的結點, ph為頭結點
?? ?ph = (TNode *)malloc(sizeof(TNode));
?? ?if(!ph) return NULL;?
?? ?ph->next = NULL;
?? ?
?? ?int i;
?? ?for(i = 0; i < n; i++){
?? ??? ?p = (TNode *)malloc(sizeof(TNode));
?? ??? ?if(!p) return NULL;
?? ??? ?
?? ??? ?p->data = R[i];
?? ??? ?//頭插法插入?
?? ??? ?p->next = ph->next;
?? ??? ?ph->next = p;
?? ?}
?? ?return ph;//返回頭結點?
}?
#define N 10
//分配算法,對三位數的記錄序列按照關鍵字低位排序分配?
void dispatch(TNode *ph, TPointer *Q, int d){?? ?
?? ?//ph存記錄, Q隊列:存指針,d根據關鍵字到那一趟取值不同?? ?
?? ?TNode *p = NULL;//作為輔助空間拆分ph?
?? ?int i, idx;
?? ?
?? ??
?? ?//初始化Q
?? ?for(i = 0; i < N; i++){
?? ??? ?Q[i].front = NULL;
?? ??? ?Q[i].rear = NULL;?
?? ?}?
?? ?
?? ?p = ph->next;
?? ?if(p){
?? ??? ?ph->next = p->next;
?? ??? ?p->next = NULL;
?? ?}//第一個記錄被單獨拆到p里面
?? ?
?? ?while(p){
?? ??? ?idx = p->data;
?? ??? ?for(i = 0; i < d; i++)
?? ??? ??? ?idx = idx / N;
?? ??? ?//第一趟排序,d = 0
?? ??? ?idx = idx % N;
?? ??? ?
?? ??? ?//根據關鍵字分配到Q中
?? ??? ?if(Q[idx].front = NULL){
?? ??? ??? ?Q[idx].front = p;
?? ??? ??? ?Q[idx].rear = p;
?? ??? ?}?
?? ??? ?else{//尾插法?
?? ??? ??? ?Q[idx].rear->next = p;
?? ??? ??? ?Q[idx].rear = p;
?? ??? ?}
?? ??? ?p = ph->next;
?? ??? ?if(p){//拆,直到拆完?
?? ??? ??? ?ph->next = p->next;
?? ??? ??? ?p->next = NULL;
?? ??? ?}
?? ?}?
}
void collect(TNode *ph, TPointer *Q){
?? ?TNode *p;
?? ?int i;
?? ?//ph為頭結點,最終可以傳出去
?? ?
?? ?for(i = 0; !Q[i].front; i++)
?? ??? ?;//找出第一個隊列中非空結點
?? ?ph->next = Q[i].front;
?? ?p = Q[i].rear;
?? ?i++;
?? ?
?? ?for(; i < N; i++){
?? ??? ?if(Q[i].front){
?? ??? ??? ?p->next = Q[i].front;
?? ??? ??? ?p = Q[i].rear;//注意的是Q[i]內部的結點是連接好的?
?? ??? ?}
?? ?}
?? ?p->next = NULL;
}?
void list_sort(int *R, int n){
?? ?int i;
?? ?TNode *ph, *p;
?? ?TPointer Q[N];
?? ?int m = max(R, n);
?? ?
?? ?ph = create_list(R, n);
?? ?
?? ?for(i = 0; m; i++, m /= N){
?? ??? ?dispatch(ph, Q, i);
?? ??? ?collect(ph, Q);
?? ?}
?? ?for(i = 0, p = ph->next; p; p = p->next){
?? ??? ?R[i] = p->data;
?? ?}
?? ?free(ph);
}
?
碼字不易, 贊贊啊!
歡迎評論交流!
?
總結
