1.插入排序
逐個(gè)處理待排序的記錄比伏，每個(gè)記錄與前面已排序已排序的子序列進(jìn)行比較，將它插入子序列中正確位置
代碼
template<class Elem>
void inssort(Elem A[],int n)
{
for(int i = 1;i < n;i++)
for(int j = i;j >= 1 && A[j] < A[j-1];j--)
swap(A,j,j-1);
}
性能
- 最佳：升序。時(shí)間復(fù)雜度為O(n)
- 最差：降序蔼啦。時(shí)間復(fù)雜度為O(n^2)
- 平均：對(duì)于每個(gè)元素辣吃，前面有一半元素比它大动遭。時(shí)間復(fù)雜度為O(n^2)
如果待排序數(shù)據(jù)已經(jīng)“基本有序”，使用插入排序可以獲得接近O(n)的性能
優(yōu)化
template<class Elem>
void inssort(Elem A[],int n)
{
for(int i = 1;i < n;i++){
int j = i;
int tp = A[j];
for(;j >= 1 && tp < A[j-1];j--)
A[j] = A[j - 1];
A[j] = tp;
}
}
2.冒泡排序
從數(shù)組的底部比較到頂部神得，比較相鄰元素厘惦。如果下面的元素更小則交換，否則循头，上面的元素繼續(xù)往上比較绵估。這個(gè)過程每次使最小元素像個(gè)“氣泡”似地被推到數(shù)組的頂部
代碼
template<class Elem>
void bubsort(Elem A[],int n)
{
for(int i = 0;i < n - 1;i++)
for(int j = n - 1;j > i;j--)
if(A[j] < A[j-1])
swap(A,j,j-1);
}
性能
冒泡排序是一種相對(duì)較慢的排序炎疆，沒有較好的最佳情況執(zhí)行時(shí)間。通常情況下時(shí)間復(fù)雜度都是O(n^2)
優(yōu)化
增加一個(gè)變量flag国裳，用于記錄一次循環(huán)是否發(fā)生了交換形入，如果沒發(fā)生交換說明已經(jīng)有序，可以提前結(jié)束
3.選擇排序
第i次“選擇”數(shù)組中第i小的記錄缝左，并將該記錄放到數(shù)組的第i個(gè)位置亿遂。換句話說，每次從未排序的序列中找到最小元素渺杉，放到未排序數(shù)組的最前面
代碼
template<class Elem>
void selsort(Elem A[],int n)
{
for(int i = 0;i < n - 1;i++){
int lowindex = i;
for(int j = i + 1;j < n;j++)
if(A[j] < A[lowindex])
lowindex = j;
swap(A,i,lowindex);//n次交換
}
}
性能
不管數(shù)組是否有序蛇数，在從未排序的序列中查找最小元素時(shí)，都需要遍歷完最小序列是越，所以時(shí)間復(fù)雜度為O(n^2)
優(yōu)化
每次內(nèi)層除了找出一個(gè)最小值耳舅，同時(shí)找出一個(gè)最大值（初始為數(shù)組結(jié)尾）。將最小值與每次處理的初始位置的元素交換倚评，將最大值與每次處理的末尾位置的元素交換浦徊。這樣一次循環(huán)可以將數(shù)組規(guī)模減小2，相比于原有的方案（減小1）會(huì)更快
4.shell排序
shell排序在不相鄰的元素之間比較和交換天梧。利用了插入排序的最佳時(shí)間代價(jià)特性盔性，它試圖將待排序序列變成基本有序的，然后再用插入排序來完成排序工作
在執(zhí)行每一次循環(huán)時(shí)呢岗，Shell排序把序列分為互不相連的子序列冕香，并使各個(gè)子序列中的元素在整個(gè)數(shù)組中的間距相同，每個(gè)子序列用插入排序進(jìn)行排序后豫。每次循環(huán)增量是前一次循環(huán)的1/2悉尾，子序列元素是前一次循環(huán)的2倍
最后一輪將是一次“正常的”插入排序（即對(duì)包含所有元素的序列進(jìn)行插入排序）
代碼
const int INCRGAP = 3;
template<class Elem>
void shellsort(Elem A[],int n)
{
for(int incr = n / INCRGAP;incr > 0;incr /= INCRGAP){//遍歷所有增量大小
for(int i = 0;i < incr;i++){
/*對(duì)子序列進(jìn)行插入排序，當(dāng)增量為1時(shí)硬贯，對(duì)所有元素進(jìn)行最后一次插入排序*/
for(int j = i + incr;j < n;j += incr){
for(int k = j; k > i && A[k] < A[k - incr];k -= incr){
swap(A,k,k - incr);
}
}
}
}
}
性能
選擇適當(dāng)?shù)脑隽啃蛄锌墒筍hell排序比其他排序法更有效焕襟，一般來說，增量每次除以2時(shí)并沒有多大效果饭豹，而“增量每次除以3”時(shí)效果更好
當(dāng)選擇“增量每次除以3”遞減時(shí)鸵赖，Shell排序的平均運(yùn)行時(shí)間是O(n^(1.5))
5.快速排序
首先選擇一個(gè)軸值，小于軸值的元素被放在數(shù)組中軸值左側(cè)拄衰，大于軸值的元素被放在數(shù)組中軸值右側(cè)它褪，這稱為數(shù)組的一個(gè)分割(partition)∏滔ぃ快速排序再對(duì)軸值左右子數(shù)組分別進(jìn)行類似的操作
選擇軸值有多種方法茫打。最簡(jiǎn)單的方法是使用首或尾元素。但是，如果輸入的數(shù)組是正序或者逆序時(shí)老赤，會(huì)將所有元素分到軸值的一邊轮洋。較好的方法是隨機(jī)選取軸值
代碼
template <class Elem>
int partition(Elem A[],int i,int j)
{
//這里選擇尾元素作為軸值,軸值的選擇可以設(shè)計(jì)為一個(gè)函數(shù)
//如果選擇的軸值不是尾元素，還需將軸值與尾元素交換
int pivot = A[j];
int l = i - 1;
for(int r = i;r < j;r++)
if(A[r] <= pivot)
swap(A,++l,r);
swap(A,++l,j);//將軸值從末尾與++l位置的元素交換
return l;
}
template <class Elem>
void qsort(Elem A[],int i,int j)
{
if(j <= i) return;
int p = partition<Elem>(A,i,j);
qsort<Elem>(A,i,p - 1);
qsort<Elem>(A,p + 1,j);
}
性能
- 最佳情況：O(nlogn)
- 平均情況：O(nlogn)
- 最差情況：每次處理將所有元素劃分到軸值一側(cè)抬旺，O(n^2)
快速排序平均情況下運(yùn)行時(shí)間與其最佳情況下的運(yùn)行時(shí)間很接近弊予，而不是接近其最壞情況下的運(yùn)行時(shí)間。快速排序是所有內(nèi)部排序算法中平均性能最優(yōu)的排序算法
優(yōu)化
-
最明顯的改進(jìn)之處是軸值的選取开财，如果軸值選取合適汉柒，每次處理可以將元素較均勻的劃分到軸值兩側(cè)：
三者取中法：三個(gè)隨機(jī)值的中間一個(gè)。為了減少隨機(jī)數(shù)生成器產(chǎn)生的延遲责鳍，可以選取首中尾三個(gè)元素作為隨機(jī)值
當(dāng)n很小時(shí)碾褂，快速排序會(huì)很慢。因此當(dāng)子數(shù)組小于某個(gè)長(zhǎng)度（經(jīng)驗(yàn)值：9）時(shí)历葛，什么也不要做正塌。此時(shí)數(shù)組已經(jīng)基本有序，最后調(diào)用一次插入排序完成最后處理
6.歸并排序
將一個(gè)序列分成兩個(gè)長(zhǎng)度相等的子序列恤溶，為每一個(gè)子序列排序传货，然后再將它們合并成一個(gè)序列。合并兩個(gè)子序列的過程稱為歸并
代碼
template<class Elem>
void mergesortcore(Elem A[],Elem temp[],int i,int j)
{
if(i == j) return;
int mid = (i + j)/2;
mergesortcore(A,temp,i,mid);
mergesortcore(A,temp,mid + 1,j);
/*歸并*/
int i1 = i,i2 = mid + 1,curr = i;
while(i1 <= mid && i2 <= j){
if(A[i1] < A[i2])
temp[curr++] = A[i1++];
else
temp[curr++] = A[i2++];
}
while(i1 <= mid)
temp[curr++] = A[i1++];
while(i2 <= j)
temp[curr++] = A[i2++];
for(curr = i;curr <= j;curr++)
A[curr] = temp[curr];
}
template<class Elem>
void mergesort(Elem A[],int sz)
{
Elem *temp = new Elem[sz]();
int i = 0,j = sz - 1;
mergesortcore(A,temp,i,j);
delete [] temp;
}
性能
logn層遞歸中宏娄，每一層都需要O(n)的時(shí)間代價(jià)，因此總的時(shí)間復(fù)雜度是O(nlogn)逮壁，該時(shí)間復(fù)雜度不依賴于待排序數(shù)組中數(shù)值的相對(duì)順序孵坚。因此，是最佳窥淆，平均和最差情況下的運(yùn)行時(shí)間
由于需要一個(gè)和帶排序數(shù)組大小相同的輔助數(shù)組卖宠，所以空間代價(jià)為O(n)
優(yōu)化
原地歸并排序不需要輔助數(shù)組即可歸并
void reverse(int *arr,int n)
{
int i = 0,j = n - 1;
while(i < j)
swap(arr[i++],arr[j--]);
}
void exchange(int *arr,int sz,int left)
{
reverse(arr,left);//翻轉(zhuǎn)左邊部分
reverse(arr + left,sz - left);//翻轉(zhuǎn)右邊部分
reverse(arr,sz);//翻轉(zhuǎn)所有
}
void merge(int *arr,int begin,int mid,int end)
{
int i = begin,j = mid,k = end;
while(i < j && j <= k){
int right = 0;
while(i < j && arr[i] <= arr[j])
++i;
while(j <= k && arr[j] <= arr[i]){
++j;
++right;
}
exchange(arr + i,j - i,j - i - right);
i += right;
}
}
7.堆排序
堆排序首先根據(jù)數(shù)組構(gòu)建最大堆，然后每次“刪除”堆頂元素（將堆頂元素移至末尾）忧饭。最后得到的序列就是從小到大排序的序列
代碼
這里直接使用C++ STL中堆的構(gòu)建與刪除函數(shù)
template <class Elem>
void heapsort(Elem A[],int n)
{
Elem mval;
int end = n;
make_heap(A,A + end);
for(int i = 0;i < n;i++){
pop_heap(A,A + end);
end--;
}
}
如果不能使用現(xiàn)成的庫(kù)函數(shù)：
/********************************************
* 向堆中插入元素
* hole：新元素所在的位置
********************************************/
template <class value>
void _push_heap(vector<value> &arr,int hole){
value v = arr[hole];//取出新元素扛伍，從而產(chǎn)生一個(gè)空洞
int parent = (hole - 1) / 2;
//建最大堆，如果建最小堆換成 arr[parent] > value
while(hole > 0 && arr[parent] < v){
arr[hole] = arr[parent];
hole = parent;
parent = (hole - 1) / 2;
}
arr[hole] = v;
}
/********************************************
* 刪除堆頂元素
********************************************/
template <class value>
void _pop_heap(vector<value> &arr,int sz)
{
value v = arr[sz - 1];
arr[sz - 1] = arr[0];
--sz;
int hole = 0;
int child = 2 * (hole + 1); //右孩子
while(child < sz){
if(arr[child] < arr[child - 1])
--child;
arr[hole] = arr[child];
hole = child;
child = 2 * (hole + 1);
}
if(child == sz){
arr[hole] = arr[child - 1];
hole = child - 1;
}
arr[hole] = v;
_push_heap(arr,hole);
}
/********************************************
* 建堆
* sz：刪除堆頂元素后的大小
* v： 被堆頂元素占據(jù)的位置原來的元素的值
********************************************/
template <class value>
void _make_heap(vector<value> &arr)
{
int sz = arr.size();
int parent = (sz - 2) / 2;
while(parent >= 0){
int hole = parent;
int child = 2 * (hole + 1); //右孩子
value v = arr[hole];
while(child < sz){
if(arr[child] < arr[child - 1])
--child;
arr[hole] = arr[child];
hole = child;
child = 2 * (hole + 1);
}
if(child == sz){
arr[hole] = arr[child - 1];
hole = child - 1;
}
arr[hole] = v;
_push_heap(arr,hole);
--parent;
}
}
template <class value>
void heap_sort(vector<value> &arr)
{
_make_heap(arr);
for(int sz = arr.size();sz > 1;sz--)
_pop_heap(arr,sz);
}
性能
根據(jù)已有數(shù)組構(gòu)建堆需要O(n)的時(shí)間復(fù)雜度词裤，每次刪除堆頂元素需要O(logn)的時(shí)間復(fù)雜度刺洒，所以總的時(shí)間開銷為，O(n+nlogn)吼砂，平均時(shí)間復(fù)雜度為O(nlogn)
注意根據(jù)已有元素建堆是很快的逆航，如果希望找到數(shù)組中第k大的元素，可以用O(n+klogn)的時(shí)間渔肩，如果k很小因俐，時(shí)間開銷接近O(n)
