1. 冒泡排序
基本思想：每次比較兩個相鄰的元素嘹裂，如果他們的順序錯誤就把他們交換過來如输。
時間復雜度：
- 最好的情況下，待排序記錄已經(jīng)有序茉继，只需要一趟排序就可以完成，所以冒泡排序的最好時間復雜度為 O(n)蚀乔。
- 最壞的情況下烁竭，待排序記錄反序，這時需要 n - 1 趟排序乙墙，每趟排序需要比較 n - i 次比較操作颖变，這時比較和移動的次數(shù)達到最大值生均，所以冒泡排序的最壞時間復雜度為 O(n ^ 2)。
- 平均時間復雜度為 O(n ^ 2)腥刹。因為它移動的次數(shù)較多马胧，其平均時間性能還不如直接插入排序。
void bubble_sort(int s[],int n)
{
for (int i=0;i<n;i++)
{
for (int j=n-1;j>i;j--)
{
if (s[j-1]>s[j])
{
swap(s[j-1],s[j]);
}
}
}
}
冒泡排序的優(yōu)化：在算法中增加一個標志exchange衔峰，用以標識本趟冒泡結(jié)果是否發(fā)生了交換佩脊；如果沒有發(fā)生交換則exchange=false，表示全部元素已經(jīng)排好垫卤，因而可以結(jié)束算法威彰；如果exchange=true，表示本趟有元素發(fā)生交換穴肘，還需執(zhí)行下一趟排序歇盼。
void new_bubble_sort(int s[],int n)
{
bool exchange;
for (int i=0;i<n;i++)
{
exchange = false;
for (int j=n-1;j>i;j--)
{
if (s[j-1]>s[j])
{
swap(s[j-1],s[j]);
exchange =true;
}
}
if(exchange == false) return;
}
}
2. 插入排序
基本思想：每次將一個待排序元素按其大小插入到前面已經(jīng)排好的序列中的適當位置，直至元素全部插入為止
時間復雜度分析： 直接插入排序算法主要進行有兩個操作评抚，查找比較豹缀，移動記錄。這兩個操作均和記錄長度n相關慨代。其平均時間復雜度為O(n^2)邢笙。這在排序算法里面算慢的，但是當記錄較少時侍匙，它的效率還是可以不錯的氮惯。
空間復雜度分析：直接插入排序只需要一個元素的輔助空間，用于元素的位置交換O(1)想暗。
直接插入排序是穩(wěn)定排序妇汗。它在元素基本有序的情況下（接近最好情況），比較和移動的次數(shù)都較少，效率是很高的。
2.1 直接插入排序
void insert_sort(int s[],int n)
{
for (int i=1;i<n;i++)
{
if (s[i]<s[i-1])
{
int temp = s[i], j=i-1;
do
{
s[j+1] = s[j];
j--;
}
while (j>=0 && temp<s[j]);
s[j+1] = temp;
}
}
}
2.2 二分插入排序
利用二分查找澈驼，查找待插入元素應插入前面有序序列的位置胃榕。
3. 選擇排序
基本思想：每次（第i次）在后面待排序元素中選出排序碼最小的元素，作為有序元素序列的第i個元素。待n-2趟作完，待排序元素只剩下1個，就不用排序了擒悬。
時間復雜度分析：無論待排序記錄的初始狀態(tài)如何，在第i趟排序中選出最小關鍵字的記錄稻艰，需做n-i次比較懂牧，因此，總的比較次數(shù)為：n*(n-1) /2=O(n^2)，當待排序記錄的初始狀態(tài)為正序時僧凤，移動次數(shù)為 0畜侦；當初始狀態(tài)為反序時，每趟排序均要執(zhí)行交換操作躯保，總的移動次數(shù)取最大值3 *(n-1)旋膳。所以，直接選擇排序的平均時間復雜度為O(n^2)途事。
非穩(wěn)定排序验懊。
void select_sort(int s[],int left,int right)
{
for (int i=left;i<right;i++)
{
int min = i;
for (int j=i+1;j<=right;j++)
{
if(s[j]<s[min]) min = j;
}
if(min != i) swap(s[i],s[min]);
}
}
4. 快速排序
時間復雜度分析：
- 最壞情況：每次劃分選取的基準都是當前無序區(qū)中關鍵字最小(或最大)的記錄，劃分的結(jié)果是基準左邊的子區(qū)間為空(或右邊的子區(qū)間為空)尸变，而劃分所得的另一個非空的子區(qū)間中記錄數(shù)目义图，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。此時召烂，時間復雜度為 O(n ^ 2)碱工。
- 最好情況：每次劃分所取的基準都是當前無序區(qū)的"中值"記錄，劃分的結(jié)果是基準的左奏夫、右兩個無序子區(qū)間的長度大致相等痛垛。總的關鍵字比較次數(shù)：0(nlgn)桶蛔。
- 盡管快速排序的最壞時間為 O(n ^ 2)，但就平均性能而言漫谷，它是基于關鍵字比較的內(nèi)部排序算法中速度最快者仔雷，快速排序亦因此而得名。它的平均時間復雜度為 O(nlgn)舔示。
空間復雜度分析：快速排序需要一個棧來實現(xiàn)遞歸碟婆。若每次劃分較為均勻（也就是對半分，基準值總是中值）惕稻，則其遞歸樹的高度為O(lgn)竖共，故遞歸后需棧空間為O(lgn)俺祠。最壞情況下公给，遞歸樹的高度為O(n)，所需的椫┰空間為O(n)淌铐。
int partition(int s[],int low,int high)
{
int key = s[high];
int piv = low;
for (int i=low;i<high;i++)
{
if (s[i]<=key)
{
swap(s[piv],s[i]);
piv++;
}
}
swap(s[piv],s[high]);
return piv;
}
void quick_sort(int s[],int left,int right)
{
if (left<right)
{
int piv = partition(s,left,right);
quick_sort(s,left,piv-1);
quick_sort(s,piv+1,right);
}
}
5. 歸并排序
歸并排序是采用分治法的一個非常典型的應用，它要做兩件事情：
- “分”, 就是將數(shù)組盡可能的分蔫缸，一直分到原子級別腿准；
- “并”，將原子級別的數(shù)兩兩合并排序拾碌，最后產(chǎn)生結(jié)果吐葱。
至于二個有序數(shù)列合并街望，只要比較二個數(shù)列的第一個數(shù)，誰小就先取誰安放到臨時隊列中弟跑，取了后將對應數(shù)列中這個數(shù)刪除灾前，直到一個數(shù)列為空，再將另一個數(shù)列的數(shù)據(jù)依次取出即可窖认。
void merge(int* array, int tempArray, int left, int middle, int right)
{
for(int i=left;i<=right;i++) tempArray[i] = array[i];
int s1 = left, s2 = mid +1, temp = left;
while(s1 <=mid && s2 <= right)
{
if(tempArray[s1] <= tempArray[s2])
array[temp++] = tempArray[s1++];
else array[temp++] = tempArray[s2++];
}
while(s1 <= mid) array[temp++] = tempArray[s1++];
while(s2 <= right) array[temp] = tempArray[s2++];
}
void merge_sort(int* array, int* tempArray, int left, int right)
{
if(left >= right) return ;
int mid = left + (right - left)/2;
int tempArray = new int[right-left+1];
merge_sort(array,tempArray,left,mid);
merge_sort(array,tempArray,mid+1,right);
merge(array,tempArray,left,mid,right);
}
