研究算法的人知道，排序算法真的很重要，也是算法研究中的最基礎的東西，研究算法先研究排序算法，排序的問題無處不在..........
排序的定義：
輸入：n個數：a1,a2,a3, ...,an
輸出：n個數的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。
In-place sort（不占用額外記憶體或占用常數的記憶體）：插入排序、選擇排序、冒泡排序、堆排序、快速排序。
Out-place sort：歸并排序、計數排序、基數排序、桶排序。
stable sort：插入排序、冒泡排序、歸并排序、計數排序、基數排序、桶排序。
unstable sort：選擇排序(5 8 5 2 9)、快速排序、堆排序。
一、插入排序
插入排序對于少量的元素的排序，它是一個有效的算法。
特點：stable_sort 、in-place sort
最優複雜度：當屬數組本來是有序的時候，其複雜度為O(n),二快速排序在這種情況下會産生O(n^2)的複雜度。
最差複雜度：當輸入的數組為倒序的時候，其複雜度為O(n^2)。
void insert_sort3(vector<int> &a)
{
size_t len = a.size();
int j;
for (int i = 1; i < len; i++)
{
int key = a[i];
j = i - 1;
while (j >=0 && a[j]>key)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
} 二、冒泡排序算法
特點：stable sort、In-place sort
思想：通過兩兩交換，像水中的泡泡一樣，小的先冒出來，大的後冒出來。
最壞運作時間：O(n^2)
最佳運作時間：O(n^2)（當然，也可以進行改進使得最佳運作時間為O(n)）
其思想是交換相鄰的兩個數，把大數沉到後面去。
void BubbleSort(vector<int> &a)
{
size_t n = a.size();
size_t temp;
for (int i = 0; i < n-1; ++i)
{
for (int j = 0; j < n-1-i; ++j)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
} 在算法導論思考題中又問了”冒泡排序和插入排序哪個更快“呢？
一般的人回答：“差不多吧，因為漸近時間都是O(n^2)”。
但是事實上不是這樣的，插入排序的速度直接是逆序對的個數，而冒泡排序中執行“交換“的次數是逆序對的個數，是以冒泡排序執行的時間至少是逆序對的個數，是以插入排序的執行時間至少比冒泡排序快。
三、選擇排序算法
思想是，每一輪比較中選擇最小的一個與第一個資料進行交換，有n個數，從第2到n數中選擇比第一個小的數進行交換.......
特性：In-place sort，unstable sort。
思想：每次找一個最小值。
最好情況時間：O(n^2)。
最壞情況時間：O(n^2)。
#include<iostream>
#include<vector>
using namespace std;
void swap(int* a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void select_sort(vector<int> &a)
{
int len = a.size();
for (int i = 0; i < len; i++)
{
int min = i;
for (int j = i + 1; j < len; j++)
{
if (a[j] < a[i])
{
min = j;
}
}
if (i != min)
{
swap(&a[i], &a[min]);
}
}
}
int main()
{
vector<int> a = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
select_sort(a);
for (auto i : a)
cout << i << " ";
cout << endl;
return 0;
} 四、歸并排序
歸并排序采用了算法設計中的分治法，分治法的思想是将原問題分解成n個規模較小而結構與原問題相似的小問題，遞歸的解決這些子問題，然後再去合并其結果，得到原問題的解。分治模式在每一層遞歸上有三個步驟：
分解（divide）：将原問題分解成一系列子問題。
解決（conquer）：遞歸地解答各子問題，若子問題足夠小，則直接求解。
合并（combine）：将子問題的結果合并成原問題的解。
歸并排序（merge sort）算法按照分治模式，操作如下：
分解：将n個元素分解成各含n/2個元素的子序列
解決：用合并排序法對兩個序列遞歸地排序
合并：合并兩個已排序的子序列以得到排序結果
在對子序列排序時，長度為1時遞歸結束，單個元素被視為已排序好的。歸并排序的關鍵步驟在于合并步驟中的合并兩個已經有序的子序列，引入了一個輔助過程，merge(A,p,q,r)，将已經有序的子數組A[p...q]和A[q+1...r]合并成為有序的A[p...r]。書中給出了采用哨兵實作merge的僞代碼，課後習題要求不使用哨兵實作merge過程。在這個兩種方法中都需要引入額外的輔助空間，用來存放即将合并的有序子數組，總的空間大小為n。
#include<iostream>
using namespace std;
//merge two array：對兩個有序列進行合并
void merge(int a[], int temp[], int first, int mid, int end)
{
int i = first, j = mid + 1;
int m = mid, n = end;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (int i = 0; i < k; i++)/*把存儲在temp中排好的序列copy到a中對應的下标上*/
a[first + i] = temp[i];
}
void merge_sort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
merge_sort(a, first, mid, temp); //it's let letf have a regular
merge_sort(a, mid + 1, last, temp); //it's let right have a regular
merge(a, temp, first, mid, last); //merge two in one
}
}
int main()
{
int a[] = { 1, 8, 6, 7, 9, 45, 68, 100, 5 };
int k = (sizeof(a) / sizeof(int));
int *p = new int[k];
merge_sort(a, 0, k - 1, p);
delete[] p;
for (int i = 0; i < k; i++)
cout << a[i] << " ";
return 0;
} 問：歸并排序的缺點是什麼？
答：他是Out-place sort，是以相比快排，需要很多額外的空間。
問：為什麼歸并排序比快速排序慢？
答：雖然漸近複雜度一樣，但是歸并排序的系數比快排大。
問：對于歸并排序有什麼改進？
答：就是在數組長度為k時，用插入排序，因為插入排序适合對小數組排序。在算法導論思考題中介紹了。複雜度為O(nk+nlg(n/k)) ，當k=O(lgn)時，複雜度為O(nlgn)
五、快速排序
Tony Hoare爵士在1962年發明，被譽為“20世紀十大經典算法之一”。
算法導論中講解的快速排序的PARTITION是Lomuto提出的，是對Hoare的算法進行一些改變的，而算法導論7-1介紹了Hoare的快排。
特性：unstable sort、In-place sort。
最壞運作時間：當輸入數組已排序時，時間為O(n^2)，當然可以通過随機化來改進（shuffle array 或者 randomized select pivot）,使得期望運作時間為O(nlgn)。
最佳運作時間：O(nlgn)
快速排序的思想也是分治法。
當輸入數組的所有元素都一樣時，不管是快速排序還是随機化快速排序的複雜度都為O(n^2)，而在算法導論第三版的思考題7-2中通過改變Partition函數，進而改進複雜度為O(n)。
注意：隻要partition的劃分比例是常數的，則快排的效率就是O(nlgn)，比如當partition的劃分比例為10000:1時（足夠不平衡了），快排的效率還是O(nlgn)
僞代碼：
PARTITION(A,p,r)
x = A[r] //将最後一個元素作為主元素
i = p-1
for j=p to r-1 //從第一個元素開始到倒數第二個元素結束，比較确定主元的位置
do if A[j] <= x
i = i+1
exchange A[i] <-> A[j]
exchange A[i+1]<->A[r] //最終确定主元的位置
return i+1 //傳回主元的位置
#include<iostream>
using namespace std;
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//劃分數組
int partition(int a[], int begin, int last)
{
int x = a[last];
int i = begin - 1;
for (int j = begin; j < last; j++)
{
if (x <= a[j])
{
i=i+1;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[last]);
return (i + 1);
}
//利用遞歸排序
void quick_sort(int a[], int begin, int last)
{
if (begin < last)
{
int q = partition(a, begin, last);
quick_sort(a, begin, q-1);
quick_sort(a, q + 1, last);
}
}
int main()
{
int i;
int a[] = { 88, 1, 22, 99, 55, 77, 33, 66, 44, 70 };
cout << "After the quick sort,the data is:" << endl;
quick_sort(a, 0, 9);
for (const auto i : a)
cout << i << " ";
cout << endl;
return 0;
} 1964年Williams提出。
特性：unstable sort、In-place sort。
最優時間：O(nlgn)
最差時間：O(nlgn)
此篇文章介紹了堆排序的最優時間和最差時間的證明：javascript:void(0)
思想：運用了最小堆、最大堆這個資料結構，而堆還能用于建構優先隊列。
優先隊列應用于程序間排程、任務排程等。
堆資料結構應用于Dijkstra、Prim算法。
1、建堆
建立最大堆的過程是自底向上地調用最大堆調整程式将一個數組A[1.....N]變成一個最大堆。将數組視為一顆完全二叉樹，從其最後一個非葉子節點（n/2）開始調整。調整過程如下圖所示：
2、排序：
堆排序算法過程為：先調用建立堆函數将輸入數組A[1...n]造成一個最大堆，使得最大的值存放在數組第一個位置A[1]，然後用數組最後一個位置元素與第一個位置進行交換，并将堆的大小減少1，并調用最大堆調整函數從第一個位置調整最大堆。給出堆數組A={4,1,3,16,9,10,14,8,7}進行堆排序簡單的過程如下：
（1）建立最大堆，數組第一個元素最大，執行後結果下圖：
（2）進行循環，從length(a)到2，并不斷的調整最大堆，給出一個簡單過程如下：
/*****************************************************************************/
/*time:2014.11.15 author:chen stallman */
/*1.建立最大堆 */
/*2.把數組轉換成最大堆 */
/*3.把建好的堆中資料與原數組進行資料交換 */
/*****************************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//建立以root為i(即根節點為i)的最大堆，利用了遞歸的思想防止調整之後以largest為父節點的子樹不是最大堆
void max_heapify(int a[], int i, int heapsize)
{
int l = 2 * i;//取其左孩子的坐标
int r = 2 * i + 1;//取其右孩子的坐标
int largest;//臨時變量，用來儲存r、l、r三個節點中最大的值
if (l<=heapsize&&a[l]>a[i])
largest = l;
else
largest = i;
if (r<=heapsize&&a[r]>a[largest])
largest = r;
if (largest != i)
{
swap(&a[i], &a[largest]);
max_heapify(a, largest, heapsize);
}
}
//***********************************************
//用自底向上的方法把數組轉換成最大堆
void buil_max_heap(int a[], int heapsize)
{
int i;
//從heapsize/2+1到heapsize的節點都是葉節點，是以我們可以把他們都看成是包含一個元素的最大堆了
//是以從數組1到heapsize的有葉節點的節點建立最大堆
for (i = heapsize / 2; i >= 1; i--)
{
max_heapify(a, i, heapsize);
}
}
//有了上面這個兩個輔助功能函數就可以對數組進行堆排序了
void heap_sort(int a[], int len)
{
int i;
buil_max_heap(a, len);
for (i = len; i >= 2; i--)
{
swap(&a[1], &a[len]);
len--;
max_heapify(a, 1, len);
}
}
int main()
{
//這裡數組下标從1開始，數組第一個元素沒有使用
int a[] = { 0,12,-3,88,52,6,4,33,2,100,5,20};
max_heapify(a, 1, 11);
for (auto i : a)
cout << i << endl;
heap_sort(a, 11);
for (auto i : a)
cout << i << " ";
cout << endl;
return 0;
} 七、計數排序
特性：stable sort、out-place sort。
最壞情況運作時間：O(n+k)
最好情況運作時間：O(n+k)
計數排序假設n個輸入元素中的每一個都介于0和k之間的整數，k為n個數中最大的元素。當k=O(n)時，計數排序的運作時間為θ(n)。計數排序的基本思想是：對n個輸入元素中每一個元素x，統計出小于等于x的元素個數，根據x的個數可以确定x在輸出數組中的最終位置。此過程需要引入兩個輔助存放空間，存放結果的B[1...n]，用于确定每個元素個數的數組C[0...k]。算法的具體步驟如下：
（1）根據輸入數組A中元素的值确定k的值，并初始化C[1....k]= 0；
（2）周遊輸入數組A中的元素，确定每個元素的出現的次數，并将A中第i個元素出現的次數存放在C[A[i]]中，然後C[i]=C[i]+C[i-1]，在C中确定A中每個元素前面有多個元素；
（3）逆序周遊數組A中的元素，在C中查找A中出現的次數，并結果數組B中确定其位置，然後将其在C中對應的次數減少1。
舉個例子說明其過程，假設輸入數組A=<2,5,3,0,2,3,0,3>，計數排序過程如下：
#include<iostream>
using namespace std;
void count_sort(int a[], int b[], int k, int length)
{
int i, j;
//each element in A between 0 and k [0,k],total k+1 elements;
// int *c = new int[k + 1];
int *c = (int*)malloc(sizeof(int)*(k+1));
memset(c, 0, (k+1)*sizeof(int));
//c[i] now contains the number of element equal to i;
for (i = 0; i < length; ++i)
c[a[i]] = c[a[i]] + 1;
//c[i] now contains the number of elements less than or equal to i;
for (j = 1; j <= k; ++j)
c[j] = c[j] + c[j - 1];
for (i = length - 1; i >= 0; i--)
{
b[c[a[i]] - 1] = a[i];
c[a[i]] = c[a[i]] - 1;
}//a[i]表示輸入的元素，c[a[i]]表示出現的次數，那麼b[c[a[i]] - 1]表示a[i]放到b數組中的位置
//放入之後，那麼c[a[i]]的次數應該減少
}
int main()
{
int a[] = { 5, 6, 9, 5, 0, 8, 2, 1, 6, 9, 8, 3, 4, 8, 6, 7, 6, 3, 3, 3, 3, 3, 8, 8, 8,11 };
int len = sizeof(a) / sizeof(int);
//cout << len << endl;
int b[26];
count_sort(a, b, 11, len);
for (int i = 0; i < len;i++)
cout << b[i] << " ";
} 八、基數排序
特性：stable sort、Out-place sort。
最壞情況運作時間：O((n+k)d)
最好情況運作時間：O((n+k)d)
從計數排序的思想及過程可以看出，當輸入數組A中的數較大的時候，就不适合。因為需要開辟最大元個輔助數組，統計每個元素的出現次數。通常計數排序用在基數排序中，作為一個子程式。
計數排序最重要的性質就是它是穩定的：具有相同值的元素在輸出數組中的相對次序與它們在輸入數組中的次序相同。
基數排序排序過程無須比較關鍵字，而是通過“配置設定”和“收集”過程來實作排序，它的時間複雜度可達到線性階：O(n)。對于十進制數來說，每一位的在[0,9]之中，d位的數，則有d列。基數排序首先按低位有效數字進行排序，然後逐次向上一位進行排序，直到最高位排序結束。舉例說明基數排序過程，如下圖所示：
#include<iostream>
using namespace std;
int get_digit_num(int data)
{
int size=0;
while (data)
{
size++;
data = data / 10;
}
return size;
}
int get_digit(int data, int size)
{
int tmp;
tmp= data;
while (size)
{
tmp = tmp / 10;
size--;
}
return (tmp % 10);
}
void radix_sort(int *datas, int len, int size)
{
int i, j, k;
int *num = (int*)malloc(len * sizeof(int));
int *counts = (int*)malloc(len * sizeof(int));
int *save = (int*)malloc(len * sizeof(int));
//memset(temps, 0, 10 * sizeof(int));
//memset(tmpd, -1, 10 * sizeof(int));
//memset(rets, -1, 10 * sizeof(int));
for (i = 0; i < size; i++)
{
memset(num, 0, len * sizeof(int));
memset(counts, 0, len * sizeof(int));
memset(save, 0, len * sizeof(int));
for (j = 0; j < len; j++)
num[j] = get_digit(datas[j], i);
for (j = 0; j < len; j++)
counts[num[j]] = counts[num[j]] + 1;
for (k = 1; k < 10; k++)
counts[k] = counts[k] + counts[k - 1];
for (j = len - 1; j >= 0; j--)
{
save[counts[num[j]] - 1] = datas[j];
counts[num[j]] = counts[num[j]] - 1;
}
memcpy(datas, save, sizeof(int)*len);
}
free(num);
free(counts);
free(save);
}
int max(int *datas, size_t length)
{
int k = datas[0];
int i;
for (i = 1; i<length; ++i)
if (datas[i] > k)
k = datas[i];
return k;
}
int main()
{
int i;
int datas[] = { 1, 11, 99, 55, 432, 578, 256, 782, 691, 206, 942, 387, 696, 374, 123, 55556, 888888888 };
int len = sizeof(datas) / sizeof(int);
int k = max(datas, len);
int size = get_digit_num(k);
radix_sort(datas, len, size);
printf("After radix sort the result is:\n");
for (i = 0; i<len; i++)
printf("%d ", datas[i]);
exit(0);
} 九、桶排序
假設輸入數組的元素都在[0,1)之間。
特性： out-place sort、stable sort
。
最壞情況運作時間：當分布不均勻時，全部元素都分到一個桶中，則O(n^2)，當然[算法導論8.4-2]也可以将插入排序換成堆排序、快速排序等，這樣最壞情況就是O(nlgn)。
最好情況運作時間：O(n)
桶排序的例子：
#include <iostream>
#include <vector>
#include <list>
#include <cstdlib>
using namespace std;
void bucket_sort(float *datas, size_t length)
{
int i, j;
int index;
float fvalue;
size_t lsize;
list<float> *retlist = new list<float>[length];
list<float>::iterator iter;
list<float>::iterator prioiter, enditer;
for (i = 0; i<length; ++i)
{
index = static_cast<int>(datas[i] * 10);
//insert a new element
retlist[index].push_back(datas[i]);
lsize = retlist[index].size();
if (lsize > 1)
{
//get the last element in the list[index]
iter = --retlist[index].end();
fvalue = *iter;
enditer = retlist[index].begin();
//insert the last element in right position
while (iter != enditer)
{
//get the second last element in the list[index]
prioiter = --iter;
//back up iter to the last element in the list[index]
iter++;
//compare two float values
if (*(prioiter)-*iter > 0.000001)
{
float temp = *(prioiter);
*(prioiter) = *iter;
*iter = temp;
}
iter--;
}
//the right inserted position
*(++iter) = fvalue;
}
}
//copy the result to datas
j = 0;
for (int i = 0; i<length; i++)
{
for (iter = retlist[i].begin(); iter != retlist[i].end(); ++iter)
datas[j++] = *iter;
}
delete[] retlist;
}
int main()
{
float datas[10] = { 0.78f, 0.17f, 0.39f, 0.76f, 0.23f, 0.67f, 0.48f, 0.58f, 0.92f, 0.12f };
bucket_sort(datas, 10);
cout << "after bucket_sort the result is:" << endl;
for (int i = 0; i<10; i++)
cout << datas[i] << " ";
cout << endl;
exit(0);
}