插入排序
每次選擇一個元素K插入到之前已排好序的部分A[1…i]中搓蚪，由后向前移動元素直到找到一個合適的位置。
插入排序是穩(wěn)定的（相等的時候表示找到合適位置了，就不需要再移動元素了）。
void InsertSort(RecType R[], int n){
int i, j;
RecType temp;
for(i = 1; i<n; ++i){
temp = R[i];
j = i - 1;//從后往前找到一個合適的位置
while(j >= 0 && temp.key < R[j].key){
R[j + 1] = R[j];
j--;
}
R[j + 1] = temp;//將元素放置到該合適位置
}
}
冒泡排序
通過交換元素，使關鍵字最大的記錄如氣泡一般逐漸往上“漂浮”直至“水面”创淡。
排序過程中只交換相鄰兩個元素的位置。因此南吮，當兩個數(shù)相等時琳彩，是沒必要交換兩個數(shù)的位置的。所以部凑，它們的相對位置并沒有改變露乏，冒泡排序算法是穩(wěn)定的
void BubbleSort(RecType R[], int n){
int i, j;
RecType temp;
for(i=0; i<n-1; i++){//每個元素
bool flag = false;
for(j=n-1;j > i; j--){//對每個元素進行冒泡
if(R[j].key < R[j - 1].key){
temp = R[j];
R[j] = R[j - 1];
R[j - 1] = temp;
flag = true;
}
if(!flag){//如果沒有交換，說明已經(jīng)有序了
return;
}
}
}
}
選擇排序
搜索無序數(shù)組涂邀，找到當前最小的元素瘟仿，并與無序數(shù)組首元素交換，縮小整個無序數(shù)組比勉，并重復操作劳较。直到整個數(shù)組有序。
由于每次都是選取未排序序列A中的最小元素x與A中的第一個元素交換浩聋，因此跨距離了观蜗，很可能破壞了元素間的相對位置，因此選擇排序是不穩(wěn)定的赡勘！
void SelectSort(RecType R[], int n){
int i, j, k;
RecType temp;
for(i = 0; i < n - 1; ++i){
k = i;
//便利無序數(shù)組嫂便，找到最小的元素
for(j = i + 1; j < n; j++){
if(R[j].key < R[k].key){
k = j;
}
}
if(k != i){
swap(R[i], R[k]);
}
}
希爾排序
思想：希爾排序也是一種插入排序方法,實際上是一種分組插入方法捞镰。先取定一個小于n的整數(shù)d1作為第一個增量,把表的全部記錄分成d1個組,所有距離為d1的倍數(shù)的記錄放在同一個組中,在各組內(nèi)進行直接插入排序闸与；然后,取第二個增量d2(＜d1),重復上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。
希爾排序時間復雜度平均為O(nlogn)
