常用排序算法的C++实现

排序是将一组”无序”的记录序列调整为”有序”的记录序列。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

冒泡排序：依次比较相邻的两个数，按照从小到大或者从大到小的顺序进行交换。

插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

选择排序：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

希尔排序：先将整个待排序记录序列分割成若干个子序列，再在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

归并排序：采用分治法，通过对若干个有序结点序列的归并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

堆排序：是一个完全二叉树。

快速排序：采用分治法，使数组中的每个元素与基准值比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程。

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

各种排序算法的时间复杂度如下：

下面是从其他文章中copy的测试代码，详细内容介绍可以参考对应的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;
}

GitHub： https://github.com/fengbingchun/Messy_Test