排序是將一組”無(wú)序”的記錄序列調(diào)整為”有序”的記錄序列。

???????? 假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

???????? 冒泡排序：依次比較相鄰的兩個(gè)數(shù)，按照從小到大或者從大到小的順序進(jìn)行交換。

???????? 插入排序：每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。

???????? 選擇排序：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小(大)元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

???????? 希爾排序：先將整個(gè)待排序記錄序列分割成若干個(gè)子序列，再在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

???????? 歸并排序：采用分治法，通過對(duì)若干個(gè)有序結(jié)點(diǎn)序列的歸并來(lái)實(shí)現(xiàn)排序。所謂歸并是指將若干個(gè)已排好序的部分合并成一個(gè)有序的部分。

???????? 堆排序：是一個(gè)完全二叉樹。

???????? 快速排序：采用分治法，使數(shù)組中的每個(gè)元素與基準(zhǔn)值比較，數(shù)組中比基準(zhǔn)值小的放在基準(zhǔn)值的左邊，形成左部；大的放在右邊，形成右部；接下來(lái)將左部和右部分別遞歸地執(zhí)行上面的過程。

???????? std::sort(std::stable_sort)：類似于快速排序。

各種排序算法的時(shí)間復(fù)雜度如下：

下面是從其他文章中copy的測(cè)試代碼，詳細(xì)內(nèi)容介紹可以參考對(duì)應(yīng)的reference：

#include "sort.hpp"
#include <iostream>
#include <vector>
#include <algorithm>const std::vector<int> array_src{ 12, -32, 138, -54, 34, 87, 200, -1, -901, 88 };static void print_result(const std::vector<int>& vec)
{for (int i = 0; i < vec.size(); i++)fprintf(stderr, "%d  ", vec[i]);fprintf(stderr, "\n");
}int test_sort_bubble() // 冒泡排序
{// reference: http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htmstd::vector<int> vec(array_src.begin(), array_src.end());int tmp = 0;for (int i = 1; i < vec.size(); i++) {for (int j = 0; j < vec.size() - 1; j++) {if (vec[j + 1] < vec[j]) {tmp = vec[j];vec[j] = vec[j + 1];vec[j + 1] = tmp;}}}fprintf(stderr, "bubble sort result: \n");print_result(vec);return 0;
}int test_sort_insertion() // 插入排序
{// reference: http://cforbeginners.com/insertionsort.htmlstd::vector<int> vec(array_src.begin(), array_src.end());int tmp = 0, j = 0;for (int i = 1; i < vec.size(); i++){j = i;while (j > 0 && vec[j] < vec[j - 1]){tmp = vec[j];vec[j] = vec[j - 1];vec[j - 1] = tmp;j--;}}fprintf(stderr, "insertion sort result: \n");print_result(vec);return 0;
}int test_sort_selection() // 選擇排序
{// reference: http://mathbits.com/MathBits/CompSci/Arrays/Selection.htmstd::vector<int> vec(array_src.begin(), array_src.end());int tmp = 0;for (int i = vec.size() - 1; i > 0; i--) {int first = 0;for (int j = 1; j <= i; j++) {if (vec[j] > vec[first])first = j;}tmp = vec[first];vec[first] = vec[i];vec[i] = tmp;}fprintf(stderr, "selection sort result: \n");print_result(vec);return 0;
}int test_sort_shell() // 希爾排序
{// reference: http://www.cplusplus.com/forum/general/123961/std::vector<int> vec(array_src.begin(), array_src.end());int tmp = 0, gap = 0;for (int gap = vec.size() / 2; gap > 0; gap /= 2) {for (int i = gap; i < vec.size(); i++) {for (int j = i - gap; j >= 0 && vec[j] > vec[j + gap]; j -= gap) {tmp = vec[j];vec[j] = vec[j + gap];vec[j + gap] = tmp;}}}fprintf(stderr, "shell sort result: \n");print_result(vec);return 0;
}// left is the index of the leftmost element of the subarray
// right is one past the index of the rightmost element
static void merge(std::vector<int>& vecSrc, int left, int right, std::vector<int>& vecDst)
{// base case: one elementif (right == left + 1) {return;} else {int i = 0;int length = right - left;int midpoint_distance = length / 2;/* l and r are to the positions in the left and right subarrays */int l = left, r = left + midpoint_distance;/* sort each subarray */merge(vecSrc, left, left + midpoint_distance, vecDst);merge(vecSrc, left + midpoint_distance, right, vecDst);/* merge the arrays together using scratch for temporary storage */for (i = 0; i < length; i++) {/* Check to see if any elements remain in the left array; if so,* we check if there are any elements left in the right array; if* so, we compare them.  Otherwise, we know that the merge must* use take the element from the left array */if (l < left + midpoint_distance && (r == right || std::min(vecSrc[l], vecSrc[r]) == vecSrc[l])) {vecDst[i] = vecSrc[l];l++;} else {vecDst[i] = vecSrc[r];r++;}}/* Copy the sorted subarray back to the input */for (i = left; i < right; i++) {vecSrc[i] = vecDst[i - left];}}
}int test_sort_merge() // 歸并排序
{// reference: http://www.cprogramming.com/tutorial/computersciencetheory/merge.htmlstd::vector<int> vecSrc(array_src.begin(), array_src.end());std::vector<int> vecDst(array_src.size());merge(vecSrc, 0, vecSrc.size(), vecDst);fprintf(stderr, "merge sort result: \n");print_result(vecDst);return 0;
}static void quick(std::vector<int>& vec, int left, int right)
{int i = left, j = right;int tmp;int pivot = vec[(left + right) / 2];// partitionwhile (i <= j) {while (vec[i] < pivot)i++;while (vec[j] > pivot)j--;if (i <= j) {tmp = vec[i];vec[i] = vec[j];vec[j] = tmp;i++;j--;}};// recursionif (left < j)quick(vec, left, j);if (i < right)quick(vec, i, right);
}int test_sort_quick() // 快速排序
{// reference: http://www.algolist.net/Algorithms/Sorting/Quicksortstd::vector<int> vec(array_src.begin(), array_src.end());quick(vec, 0, vec.size() - 1);fprintf(stderr, "quick sort result: \n");print_result(vec);return 0;
}static void max_heapify(std::vector<int>& vec, int i, int n)
{int temp = vec[i];int j = 2 * i;while (j <= n) {if (j < n && vec[j + 1] > vec[j])j = j + 1;if (temp > vec[j]) {break;} else if (temp <= vec[j]) {vec[j / 2] = vec[j];j = 2 * j;}}vec[j / 2] = temp;
}static void heapsort(std::vector<int>& vec, int n)
{for (int i = n; i >= 2; i--) {int temp = vec[i];vec[i] = vec[1];vec[1] = temp;max_heapify(vec, 1, i - 1);}
}static void build_maxheap(std::vector<int>& vec, int n)
{for (int i = n / 2; i >= 1; i--)max_heapify(vec, i, n);
}int test_sort_heap() // 堆排序
{// reference: http://proprogramming.org/heap-sort-in-c/std::vector<int> vec(array_src.begin(), array_src.end());vec.insert(vec.begin(), -1);build_maxheap(vec, vec.size()-1);heapsort(vec, vec.size()-1);std::vector<int> vecDst(vec.begin() + 1, vec.end());fprintf(stderr, "heap sort result: \n");print_result(vecDst);return 0;
}static bool cmp(int i, int j)
{return (i<j);
}int test_sort_STL() // std::sort
{// reference: http://www.cplusplus.com/reference/algorithm/sort/std::vector<int> vec(array_src.begin(), array_src.end());std::sort(vec.begin(), vec.end(), cmp);fprintf(stderr, "STL sort result: \n");print_result(vec);std::vector<int> vec1(array_src.begin(), array_src.end());std::stable_sort(vec1.begin(), vec1.end(), cmp);fprintf(stderr, "STL stable sort result: \n");print_result(vec1);return 0;
}