基本概念與分類

假設含有n個記錄的序列為 { r 1 , r 2 , . . . , r n } \{r_1,r_2,...,r_n\} {r1?,r2?,...,rn?}，其相應的關鍵字分別為 { k 1 , k 2 , . . . , k n } \{k_1,k_2,...,k_n\} {k1?,k2?,...,kn?}，需確定1，2，…，n的一種排列$p_1,p_2,...,p_n$，使其相應的關鍵字滿足$k_{p1}\le k_{p2}\le ...\le k_{pn}$（非遞減或遞增）關系，即使得序列成為一個按關鍵字有序的序列 { r p 1 , r p 2 , . . . , r p n } \{r_{p1},r_{p2},...,r_{pn}\} {rp1?,rp2?,...,rpn?}，這樣的操作稱為排序。

排序的穩定性

假設$r_i=r_j(1\le i\le n,i\le j\le n,i\ne j)$，且在排序前的序列中$r_i$領先與$r_j$。如果排序后$r_i$仍然領先與$r_j$，則稱所用的排序方法是穩定的；反之則是不穩定的。

內排序與外排序

內排序是在排序整個過程中，待排序的所有記錄全部被就置在內存中 。外排序是由于排序的記錄個數太多 ， 不能同時放置在內存，整個排序過程需要在內外存之間多次交換數據才能進行。

排序用到的結構與函數

#define MAXSIZE 10    /* 用于要排序數組個數最大值，可以根據需要修改 */
typedef struct
{int r[MAXSIZE+1]; /* 存儲要排序的數組，r[0]用作哨兵或臨時變量 */int length;       /* 用于記錄順表的長度 */
}SqList;

/* 交換L中數組r的下標為i和j的值 */
void swap(SqList * L,int i,int j) 
{int temp=L->r[i];L->r[i]=L->r[j];L->r[j]=temp;
}

冒泡排序

冒泡排序（Bubble Sort）一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

/* 對順序表L作交換排序（冒泡排序初級版） */
void BubbleSort0(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作交換排序（冒泡排序改進版） */
void BubbleSort(SqList *L)
{int i,j;for(i=1;i<L->length;i++){for(j=L->length-1;j>=i;j--) /* 注意j是從后向前循環 */{if(L->r[j]>L->r[j+1])   /* 若前者大于后者（注意這里與上一算法的差異） */{swap(L,j,j+1);}}}
}

/* 對順序表L作交換排序（冒泡排序優化版） */
void BubbleSort2(SqList *L)
{int i,j;bool flag = true;				/* flag用來作為標記 */for(i=1;i<L->length && flag ;i++) /* flag為false，則退出循環 */{flag = false;				/* 初始化false */for(j=L->length-1;j>=i;j--) {if(L->r[j]>L->r[j+1])   {swap(L,j,j+1);flag = true; /* 如果有數據交換，則flag為true */}}}
}

冒泡排序算法的時間復雜度：KaTeX parse error: Expected group after '_' at position 5: \sum_?\limits{i=2}^{n…，總的時間復雜度為$O(n^2)$

簡單選擇排序

簡單選擇排序法（Simple Selection Sort）就是通過 $n?i$ 次關鍵字間的比較，從 $n?i+1$ 記錄中選出關鍵字最小的記錄，并和第 $i(1\le i\le 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->length;j++){ /* 循環之后的數據 */if(L->r[min]>L->r[j])      /* 如果有小于當前最小值的關鍵字 */min = j;   			   /* 將此關鍵字的下標賦值給min */}if(i != min)				   /* 若min不等于i，說明找到最小值，交換 */swap(L,i,min)			   /* 交換L->r[i]與L->r[min]的值 */}
}

簡單選擇排序算法的時間復雜度：KaTeX parse error: Expected group after '_' at position 5: \sum_?\limits{i=1}^{n…，總的時間復雜度為$O(n^2)$。

盡管與冒泡排序同為$O(n^2)$，但簡單選擇排序的性能上還是略優于冒泡排序。

直接插入排序

直接插入排序（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->r[i]插入有序子表 */L->r[0]=L->r[i];	 /* 設置哨兵 */for(j=i-1;L->r[j]>L->r[0];j--)L->r[j+1] = L->r[j]; /* 記錄后移 */L->r[j+1] = L->r[0];     /* 插入到正確位置 */}}
}

最好情況（有序表本身有序）下的算法復雜度：$n?1({\sum }_{i=2}^{n}1)$ ，時間復雜度為O(n)

最壞情況（有序表是逆序）下的算法復雜度：比較 KaTeX parse error: Expected group after '_' at position 5: \sum_?\limits{(i=2)}^…次，記錄移動KaTeX parse error: Expected group after '_' at position 5: \sum_?\limits{i=2}^{n…次

如果排序記錄是隨機的，那么根據概率相同的原則，平均比較和移動次數約為$\frac{n^2}{4}$。直接插入排序法的時間復雜度為$O(n^2)$ ，直接插入排序法比冒炮和簡單選擇排序的性能要好一些。

希爾排序算法

1. 將原本有大量記錄數的記錄進行分組，分割成若干個子序列。

2. 在這些子序列內進行插入排序，當整個序列基本有序時，再對全體記錄進行一次直接插入排序

   所謂的基本有序，就是小的關鍵字基本在前面，大的基本在后面，不大不小的基本在中間。

/* 對順序表L作希爾排序 */
void ShellSort(SqList * L)
{int i,j;int increment = L->length;do{increment = increment/3 +1;  /*增量序列*/for(i = increment +1;i<=L->length;i++){if(L->r[i] < L->r[i-increment]){/* 需將L->r[i] 插入有序增量子表 */L->r[0] = L->r[i]; /* 暫存在L->r[0] */for(j=i-increment;j>0 && L->r[0]< L->r[j];j-=increment)L->r[j+increment] = L->r[j]; /* 記錄后移，查找插入位置 */L->r[j+increment] = L->r[0]; /* 插入 */}}        }while(increment > 1);
}

希爾排序的關鍵并不是隨便分組后各自排序，而是將相隔某個"增最’'的記錄組成一個子序列， 實現跳躍式的移動，使得排序的效率提高 。

這里"增量"的選取就非常關鍵，當增量序列為 $dlta[k]=2^{t?k+1}?1(0\le k\le t\le [lo{g}_2(n+1)])$ 時，可以獲得不錯的效率。

希爾排序并不是一直穩定排序，時間復雜度為$O(n^{3/2})$。