雖然現今越來越多的新技術湧現出來，但是基礎還是最重要的，這裡就和大家一起重溫一下排序算法。
排序是什麼？其是計算機程序設計當中的一個重要的操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。由於排序的記錄數量不同，是的-排序過程當中所涉及的存儲器不同，可將排序分為兩大咧：內部排序和外部排序。內部排序指的是待排記錄存放在計算機隨機存儲器中進行的排序過程；外部排序指的是待排序記錄的數量很大，以致內存一次不能容納全部記錄，再排序的過程中尚須對外存進行訪問的排序過程。這裡我們先主要先來看一下內部排序。
內部排序的結構請看這裡，我們先來看一下插入排序。插入排序有直接插入排序、折半插入排序、2-路插入排序等等，但是其都是在直接插入排序的基礎上改進而來。所以我們先來詳細的看一下直接插入排序。
直接插入排序實際上就是將第i個數插入到已經有序的前i-1個元素當中，那麼這i個元素也就成為有序的序列，如此往復循環，直至將整個序列變為有序的。，下面我們來看個例子：
L[0] L[1] L[2] L[3] L[4] L[5] L[6] L[7] L[8]
初始關鍵字 (49) 38 65 97 76 13 27 49
i=2 (38) (38 49) 65 97 76 13 27 49
I=3 (65) (38 49 65) 97 76 13 27 49
I=4 (97) (38 49 65 97) 76 13 27 49
I=5 (76) (38 49 65 76 97) 13 27 49
I=6 (13) (13 38 49 65 76 97) 27 49
I=7 (27) (13 27 38 49 65 76 97) 49
I=8 (49) (13 27 38 49 49 65 76 97)
上面就是一個直接插入排序的過程，每次比較完成後指針自加一次，然後指針指向的元素與前一個元素進行比較，如果比前一個元素小，那麼存入L[0]中，然後前一個元素存入到指針指向的位置，然後L[0]和前面已經排好的序列從後向前進行比較，比較過的元素都向後移動，直到L[0]大於比較的數，將L[0]中的數插入到其後面的單元中。算法代碼如下：
[cpp]
#include<stdio.h>
#define N 100
int L[N];
void insertsort(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
if(L[i]<L[i-1])
{
L[0] = L[i];
L[i] = L[i-1];
}
for(j=i-2;L[j]>L[0];j--)
L[j+1] = L[j];
L[j+1] = L[0];
}
for(i=1;1<=n;i++)
printf("L[%d]=%d",i,L[i]);
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&L[i]);
insertsort(n);
return 0;
}
上面就是直接插入排序的一個例子，它的時間復雜度為O(n2)。直接插入排序是穩定的。
下面我們來看一下插入排序的另外一種：希爾排序。它又稱作“縮小增量排序”，它較之直接插入排序，時間復雜度上有了較大的提高。其主要的算法思想是：先將整個序列分割成若干子序列進行直接插入排序，待整個序列中的記錄基本有序後，再對全體記錄進行一次直接插入排序，這樣他的時間復雜度就有了較大的提高。下面我們將一個序列進行一次希爾排序，如下：
初始關鍵字 49 38 65 97 76 13 27 49 55 04
第一趟排序 49 13
38 27
65 49
97 55
76 04
一趟排序結果 13 27 49 55 04 49 38 65 97 76 第一趟排序增量為5
第二趟排序 13 55 38 76
27 04 65
49 49 97
二趟排序結果 13 04 49 38 27 49 55 65 97 76 第二趟排序增量為3
第三趟排序 04 13 27 38 49 49 55 65 76 97
下面我們來看運用希爾排序的一個小例子，更加有助於大家對於希爾排序的理解：
[cpp]
#include<stdio.h>
#define N 100
int L[N];
void ShellInsert(int n,int dk)
{
int i,j;
for(i=dk+1;i<=n;i++)
{
if(L[i]<L[i-dk])
L[0] = L[i];
for(j=i-dk;j>0&&L[0]<L[j];j=j-dk)
L[j+dk] = L[j];
L[j] = L[0];
}
}
void Shellsort(int n,int dlta[],int t)
{
int k,i;
for(k=0;k<t;k++)
ShellInsert(n,dlta[k]);
for(i=1;i<=n;i++)
printf("L[%d]=%d\n",i,L[i]);
}
int main()
{
int i,n,t,dlta[5]={5,3,1};
scanf("%d",&n);
scanf("%d",&t);
for(i=1;i<=n;i++)
scanf("%d",&L[i]);
Shellsort(n,dlta,t);
return 0;
}
希爾排序的時間復雜度為O(n*ln n)。
由上面的算法可以看出，直接插入排序是穩定的排序算法，而希爾排序是不穩定的排序算法。
上面就是插入排序的一個大概的講解，下面我們還將進行余下排序算法的講解。
