1.直接插入排序(straight insertion sort)
思想:第一趟比較前兩個數,然後把第二個數按大小插入到有序表中;
第二趟對前兩個數從後向前掃描,把第三個數按大小插入到有序表中;依次進行下去,進行(n-1)趟掃描
以後就完成了整個排序過程
屬於穩定的排序,最壞時間復雜度O(n^2),空間復雜度為O(1)
#include <stdio.h> void move(int start,int end,int *s,int e) { for(int t=end;t>=start;t--) s[t+1] = s[t]; } void InsertSort(int *s,int n) { int t; for(int i=1;i<n;i++) { t = s[i]; for(int j=i-1;j>=0;j--) if(t >= s[j]) { move(j+1,i-1,s,t); s[j+1] = t; break; } if(j < 0)//當前比較的數應該插入到最前面 { move(0,i-1,s,t); s[0] = t; } } } int main() { int s[] = {6,3,1,5,7,2,8,4}; InsertSort(s,8); for(int i=0;i<8;i++) printf("%d ",s[i]); return 0; }
2二分歸並排序
屬於穩定排序,時間復雜度O(n log n) 空間復雜度O(n)
歸並排序的算法我們通常用遞歸實現
先把待排序區間[s,t]以中點二分,
接著把左邊子區間排序,再把右邊子區間排序,
最後把左區間和右區間用一次歸並操作合並成有序的區間[s,t]。
歸並操作的工作原理如下:
第一步:申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合並後的序列
第二步:設定兩個指針,最初位置分別為兩個已經排序序列的起始位置
第三步:比較兩個指針所指向的元素,選擇相對小的元素放入到合並空間,並移動指針到下一位置
重復步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復制到合並序列尾
#include <stdio.h> #include <stdlib.h> void Merge(int *s,int start,int mid,int end)//兩個順序表長度可能不一 { int *s1 = (int *)malloc(sizeof(int)*(end - start + 1)); int t = 0,i,j; i = start,j = mid + 1;//兩個指針指向兩個已經排序序列的起始位置 while(i <= mid && j <= end)//兩個指針都未超出序列尾 { if(s[i] > s[j]) { s1[t++] = s[j]; j ++; } else{ s1[t++] = s[i]; i ++; } } if(i > mid)//第一個順序表指針超出序列尾,則將第二個順序表剩下的所有元素直接復制到合並序列尾,反之亦然 { for(int k=j;k<=end;k++) s1[t++] = s[k]; } if(j > end) { for(int k=i;k<=mid;k++) s1[t++] = s[k]; } for(int k=0;k<t;k++)//將合並後的順序表又復制回去 { // s[start++] = s1[k];數組溢出 s[start] = s1[k]; start ++; } free(s1); } void MergeSort(int *s,int start,int end) { if(end - start == 0) return; else if(end - start == 1){ if(s[end] < s[start])//交換的前提 s[end] = s[start] + s[end] - (s[start] = s[end]);//swap return; } else{ MergeSort(s,start,(end-start)/2+start); MergeSort(s,(end-start)/2+start+1,end); Merge(s,start,(end-start)/2+start,end);//2-way Merge } } int main() { int s[] = {10,4,6,3,8,2,5,7}; MergeSort(s,0,7); for(int i=0;i<=7;i++) printf("%d ",s[i]); return 0; }
測試樣例:
//10,4,6,3,11,8,2,5,7
//10,4,6,3,8,2,5,7
//2,1,8,3,9,10,5,3,7