概述
排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。
我們這里說說八大排序就是內部排序。
當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
快速排序：是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
1.插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。
直接插入排序示例：
如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。
算法的實現：
void?print(int?a[],?int?n?,int?i){
cout<
for(int?j=?0;?j<8;?j++){
cout<
}
cout<
}
void?InsertSort(int?a[],?int?n)
{
for(int?i=?1;?i
if(a[i]?
int?j=?i-1;
int?x?=?a[i];????????//復制為哨兵，即存儲待排序元素
a[i]?=?a[i-1];???????????//先后移一個元素
while(x?
a[j+1]?=?a[j];
j--;?????????//元素后移
}
a[j+1]?=?x;??????//插入到正確位置
}
print(a,n,i);???????????//打印每趟排序的結果
}
}
int?main(){
int?a[8]?=?{3,1,5,7,2,4,9,6};
InsertSort(a,8);
print(a,8,8);
}
效率：
時間復雜度：O(n^2).
其他的插入排序有二分插入排序，2-路插入排序。
2. 插入排序—希爾排序(Shell`s Sort)
希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序
基本思想：
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
操作方法：
選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個數k，對序列進行k 趟排序；
每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
希爾排序的示例：
算法實現：
我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1}n為要排序數的個數
即：先將要排序的一組記錄按某個增量d(n/2,n為要排序數的個數)分成若干組子序列，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量(d/2)對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，最后使用直接插入排序完成排序。
void?print(int?a[],?int?n?,int?i){
cout<
for(int?j=?0;?j<8;?j++){
cout<
)
