排序算法可以說是資料結構與算法系列中的精華，常用的排序算法一般來說有十種，包括插入排序、選擇排序、冒泡排序、梳排序、希爾排序、堆排序、快速排序、歸并排序、基數排序以及計數排序。接下來，我将根據自己的了解對這10種排序算法進行簡單的分析總結。為了統一，以下排序都遵循從小到大的原則。
-
插入排序
1.算法分析
插入排序排序其實跟後面的排序有些不一樣，它是從數組建立的角度去考慮的，每一次對數組插入新的元素時都會對插入的元素進行評估，觀察是否放在正确的位置。需要注意的是，對新插入元素進行評估并正确放置的前提是前面的元素已經全部正确放置。
舉例來說，向一個數組a分别插入2,3,1，要求順序是從小到大。最先向a[0]插入2，再向a[1]插入3時， 将3與2比較，順序沒有問題，再插入1，進行比較發現1比2還要小，是以要将2和3都往後移一位到a[1]與a[2]，再将1放到2原來的位置，也就是a[0]。
2.程式
void insertsort(int *data,int N)
{
for(int i=1;i<N;i++)
{
int T=data[i];//儲存目前要插入的資料（實際上現在并不是在建立數組，而是在假想在将資料插入數組）
for(int j=i-1;j>=0;j--)//所有比待插入的資料大的數全都往後移一位
if(data[j]>data[i]) data[j+1]=data[j];
data[j]=T; //将待插入資料的資料放置到正确位置
}
}
3.複雜度與穩定分析：
首先是空間複雜度，顯然整個排序過程并沒有額外占用空間，是以空間複雜度是O(1)。再看時間複雜度。最優的情況下，自然是所有資料都已經排好了。這樣的話，隻需要比較N-1次（除第一個資料外，每個資料都與前面一個資料比較一次），最差的情況下是資料完全按相反的順序排列，那麼需要比較的次數是
，而需要移動（指派）的次數是：
。平均情況下，比較複雜度是
,大概是最差情況下的一般，移動的複雜度同樣。
穩定性方面顯然如果兩個資料相同，插入排序不會改變兩者順序，是以插入排序是穩定的。
-
選擇排序
1.算法分析
選擇排序的思想比較簡單，就是依次找到最小的數，将其放在合适的位置上。舉例來說，數組a[4]中有2,1，4,3四個元素，首先找到最小的元素1，将其與第一個元素2交換，然後在剩下的元素2,4,3中找到最小的數2，降低與第二個元素交換（實際上已經在正确的位置了），以此類推，直至所有元素都找到自己的位置。事實上，我們在将一個隊伍按身高從低到高排序時就經常會利用這樣的思想。
2.程式
void selectionsort(int *data,int N)
{
for(int i=0;i<N;i++)
{ for(int j=i+1,least=i;j<N;j++)
if(data[j]<data[least])
least=j;
swap(data[i],data[least]);
}
}
3.複雜度與穩定性分析
首先是空間複雜度，排序過程中并沒有用到額外空間，是以空間複雜度是O(1)。時間複雜度方面，很顯然，不管什麼情況，指派次數
（這是書上的說法，實際上這裡好像隻考慮了對元素的指派，而忽略了元素下标的指派，難道在找最小元素的過程中，least=j就不算指派？是以我對這種說法保留意見），而如果想減少無用的指派次數（例如資料本身已經在合适的位置上），可以對swap函數添加一個條件。而對于比較複雜度，很顯然，不管順序怎麼樣比較的複雜度都是
。
穩定性方面，如果遇到有相同的數，排在前面的數，會先找到自己的位置，是以選擇排序也是穩定的。
-
冒泡排序
1、算法分析
冒泡排序實際上我覺得跟選擇排序很相似，都是為了依次将最小的資料差別在于前者從數組尾開始操作，并且一直在進行元素交換，而後者是從數組頭開始操作，并且在找到最小的元素之前，進行的僅僅是下标的指派，隻有等真正找到了最小的元素後，才進行元素的交換。
冒泡排序的過程就像其名字描述的那樣形象，以數組a[4]={2,3,1,4}為例，首先是找到數組尾的a[3]=4，将其與前一個元素1比較，發現4>1，是以按兵不動，接下來将a[2]=1與a[1]=3 比較，發現1<3，是以将1與3交換，現在a[1]=1,再将a[1]=1與a[0]=2比較，發現1<2，于是交換兩者，現在a[0]=1，也就是通過這樣一個兩兩交換的過程，将最小的數浮到了最上層，就像一個氣泡慢慢往上冒一樣。剩下的的元素按照一樣的操作就可以完成排序
2、程式
void bubbblesort(int *data,int N)
{
for(int i=N-1;i>0;i--)
for(int j=N-2;j>0;j--)
{
if(data[j]<data[j-1])
swap(data[j],data[j-1]);
}
}
3、複雜度以及穩定性分析
顯然冒泡排序的空間複雜度為O(1)，時間複雜度方面，最好情況下是資料已經按順序排列，這時隻需要進行比較比較的複雜度為
，而最差情況下，比較複雜度與指派複雜度均為
。平均情況下也是這樣，不過複雜度比最差情況下要小就是了。
穩定性方面，相同的資料在比較過程中不會改變相對的位置，是以冒泡排序是穩定的。
-
梳排序
1、算法分析
梳排序是對冒泡排序的一種改進，因為冒泡排序裡比較和交換的步長是1，也就是說每次資料隻會跟其相鄰的元素比較，這樣資料上升的速度比較慢， 而梳排序采取的方法我覺得更形象的來說應該是篩子排序，先用大篩子篩一遍，再用小篩子一層一層的往下篩。比如 說先将比較交換的步長設定為10，也就是說比較交換相差下标10的兩個元素，操作完成後，縮小步長，再進行同樣的操作，直到步長小于1。其實梳排序最本質的原理我還沒有搞清楚，目前看到的書籍也是直接甩出結論：每次将步長除以1.3就可以得到最佳結果，姑且按照這種做法操作吧。
2、程式
void CombSort(int* data,int N)
{
int path = N / 1.3;
while(path >=1)
{
for (int i= 0; i<L-path; i++)
{
if (*(data+i)>*(data +i+ path))
swap(data+i, data + i+path);
}
path = path / 1.3;
}
}
3、算法複雜度與穩定性分析
梳排序的空間複雜度為O(1)，時間複雜度平均情況為O(NlogN)，最壞情況下還是
.
-
希爾排序
-
堆排序
1、算法分析
堆排序實際上是利用完全二叉樹來實作排序的一種方法，我們講的資料結構上的堆本身就是一種完全二叉樹，是以這種方法就被稱作堆排序。
2、程式
3、複雜度與穩定性分析
-
快速排序
1、算法分析
快速排序的原理就是先選擇一個元素作為标杆，将小于該數的元素都放在左邊，将大于該數的元素都放在右邊。然後将左右兩邊視作是新的數組，進行同樣的操作。這樣就有一個問題，該選哪個數作為标杆？當然選哪個數是由你自己決定的，但是如果選的不好就會導緻排序的效果很差。例如如果選的數正好是最大的那個數或者最小的那個數，那麼會導緻其左右兩邊形成的新數組極度不均衡，算法複雜度并沒有降下來。一般來說會選數組中間的那個數作為标杆，這時需要先将中間那個數與數組第一個數交換。
2、程式
void quicksort(int *data, int first, int last)
{
int lower = first + 1;//向右移找比基準點小的數
int upper = last ;//向左移找比基準點大的數
int bound = (first + last) /2;
swap(data[first], data[bound]);
int tmp = data[first];//挖第一個蘿蔔
while (lower < upper)
{
while (data[upper]>tmp)
upper--;
while (data[lower] < tmp)
lower++;
if (lower < upper)
swap(data[lower], data[upper]);
}
swap(data[upper], data[first]);
if (first <upper)
quicksort(data, first, upper-1);
if (upper < last)
quicksort(data, upper, last);
}
void QuickSort(int *data,int L)
{
quicksort(data, 0, L);
}
3、複雜度與穩定性分析
-
歸并排序
歸并排序的思路很牛逼，其實就是分治的思想，具體來說就是從最小的元素開始1+1,2+2,4+4.....這樣一步一步合起來知道合并成最後的數組。用下面一張圖表示可能更加清晰。
2.程式
template<class T>
void merge(T array1[], T temp[], int first, int last) {
int mid = (first + last) / 2;
int i1 = 0, i2 = first, i3 = mid + 1;
while (i2 <= mid && i3 <= last)
if (array1[i2] < array1[i3])
temp[i1++] = array1[i2++];
else temp[i1++] = array1[i3++];
while (i2 <= mid)
temp[i1++] = array1[i2++];
while (i3 <= last)
temp[i1++] = array1[i3++];
for (i1 = 0, i2 = first; i2 <= last; array1[i2++] = temp[i1++]);
}
template<class T>
void mergesort(T data[], T temp[], int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
mergesort(data, temp, first, mid);
mergesort(data, temp, mid + 1, last);
merge(data, temp, first, last);
}
}
template<class T>
void mergesort(T data[], const int n) {
T *temp = new T[n];
mergesort(data, temp, 0, n - 1);
}
3、複雜度與穩定性分析
-
基數排序
1、算法分析
其實我覺得叫基數排序不如叫索引排序那樣形象。實際上基數排序的原理就像你在圖書館裡根據索引找書差不多，有一級索引、二級索引、三級索引.......在基數排序中一級索引可能就是個位數，二級索引就是十位數，依次類推下去。先根據一級索引對所有數排列遍，一級索引相同放在用一個隊列中，一級索引排完之後再根據二級索引排一遍，一直這樣擦偶做下去直至将數組按順序排列。很顯然，在排序之前，需要将數組中最大的資料跳出來，以供确定到底有幾級索引。
2、程式
void radixsort(int *data, int N)
{
int max = GetMax(data, N);
int INDEX = 1;//位數
queue<int> temp[10];
int fac = pow(10,INDEX);
while (max / fac)
{
INDEX++;
fac = pow(10, INDEX);
}
int factor = 1;
for (; INDEX > 0; INDEX--,factor *= 10)
{
for (int i = 0; i < N; i++)
temp[(data[i] / factor) % 10].push(data[i]);
int k = 0;
for (int j = 0; j < 10;j++)
while(!temp[j].empty())
{
data[k++] = temp[j].front();
temp[j].pop();
}
}
3、複雜度與穩定性分析
-
計數排序
1、算法分析
2、程式
3、複雜度與穩定性分析