作者：billy
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。十大排序算法用一张图概括：
冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用
void BSortMethod::bubbleSort(int *vec, int len)
{
// 每次遍历找到最大的数放在最右边，最后一个数不用比较，所以一共进行 len - 1 次遍历
for ( int i = 1; i < len; ++i )
{
for ( int j = 0; j < len - i; ++j )
{
if ( vec[j] > vec[j+1] ) {
int temp = vec[j];
vec[j] = vec[j+1];
vec[j+1] = temp;
}
}
}
}
选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧
void BSortMethod::selectionSort(int *vec, int len)
{
for ( int i = 0; i < len - 1; ++i )
{
int minIndex = i;
// 每次遍历找到最小值的索引
for ( int j = i + 1; j < len; ++j )
{
if ( vec[j] < vec[minIndex] ) {
minIndex = j;
}
}
// 把最小值放在有序序列的最后
if ( minIndex != i ) {
int temp = vec[minIndex];
vec[minIndex] = vec[i];
vec[i] = temp;
}
}
}
插入排序（Insertion Sort）的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
void BSortMethod::insertionSort(int *vec, int len)
{
for ( int i = 0; i < len; ++i )
{
int preIndex = i - 1;
int currentValue = vec[i];
// 从后往前遍历有序列表，直到找到比当前数值小或者相等的数的索引，我们在这个索引后插入 currentValue
while ( preIndex >= 0 && vec[preIndex] > currentValue )
{
vec[preIndex + 1] = vec[preIndex];
preIndex--;
}
vec[preIndex+1] = currentValue;
}
}
希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
这是博主网上找的图片，更方便理解递减增量排序的流程
void BSortMethod::shellSort(int *vec, int len)
{
// 初始增量 gap = len / 2，逐渐缩小增量 gap = gap / 2 直到变为 1
for ( int gap = len / 2; gap >=1; gap = gap / 2 )
{
// 每一组进行排序
for ( int i = gap; i < len; ++i )
{
int temp = vec[i];
int j = i - gap;
while ( j >= 0 && vec[j] > temp )
{
vec[j+gap] = vec[j];
j -= gap;
}
vec[j+gap] = temp;
}
}
}
归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间
void BSortMethod::merge(int *vec, int len)
{
int mid = len / 2; // mid将数组从中间分割
int *arr = new int[len]; // 临时数组（额外的内存空间）
int s = 0; // 临时数组的起始位置
int first = 0, second = mid; // 两个数组的起始位置
while ( first < mid && second < len )
{
// 比较大小
if ( vec[first] <= vec[second] ) {
arr[s++] = vec[first++];
} else {
arr[s++] = vec[second++];
}
}
// 将剩余项复制到临时数组中
while ( first < mid )
{
arr[s++] = vec[first++];
}
while ( second < len )
{
arr[s++] = vec[second++];
}
// 临时数组复制到原数组
for (int i = 0; i < len; ++i)
{
vec[i] = arr[i];
}
// 内存释放
delete []arr;
}
void BSortMethod::mergeSort(int *vec, int len)
{
// 递归出口
if ( len < 2 ) {
return;
}
mergeSort(vec, len / 2); // 对前半部分进行归并排序
mergeSort(vec + len / 2, len - len / 2); // 对后半部分进行归并排序
merge(vec, len); // 归并两部分
}
快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法。速排序又是一种分而治之思想在排序算法上的典型应用。它的基本思想是通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列
void BSortMethod::swap(int *vec, int i, int j)
{
int temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
int BSortMethod::partition(int *vec, int left, int right)
{
int pivot = left;
int index = pivot + 1;
int i = index;
while ( i <= right )
{
if ( vec[i] < vec[pivot] ) {
swap(vec, i, index);
index += 1;
}
i += 1;
}
swap(vec, pivot, index - 1);
// 返回最终划分完成后基准元素所在的位置
return index - 1;
}
void BSortMethod::quickSort(int *vec, int left, int right)
{
if ( left < right ) {
int mid = partition(vec, left, right);
quickSort(vec, left, mid - 1);
quickSort(vec, mid + 1, right);
}
}
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
堆排序的平均时间复杂度为 Ο(nlogn)
void BSortMethod::heapify(int *vec, int i, int len)
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if ( left < len && vec[left] > vec[largest] ) {
largest = left;
}
if ( right < len && vec[right] > vec[largest] ) {
largest = right;
}
if ( largest != i ) {
swap(vec, i, largest);
heapify(vec, largest, len);
}
}
void BSortMethod::heapSort(int *vec, int len)
{
// 从最后一个非叶子节点开始向上遍历，创建堆
for ( int i = len / 2 - 1; i >= 0; i-- )
{
heapify(vec, i, len);
}
for ( int j = len - 1; j > 0; j-- )
{
swap(vec, 0, j);
heapify(vec, 0, j);
}
}
计数排序（Counting Sort）的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
void BSortMethod::countingSort(int *vec, int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 根据找到的最大值来确定统计数组的长度
int arrayLen = max + 1;
// 动态申请内存，并初始化为 0
int *array = new int[arrayLen] {0};
// 遍历数组，填充统计数组（把原数组中的数据变为统计数组的索引，值都是1）
for ( int j = 0; j < len; ++j )
{
array[vec[j]]++;
}
int index = 0;
for ( int k = 0; k < arrayLen; ++k )
{
// 遍历统计数组，再把排序后的索引变回数值存在原来数组中
while ( array[k] > 0 )
{
vec[index++] = k;
array[k]--;
}
}
// 释放内存
delete []array;
}
桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要
// 方法一
void BSortMethod::bucketSort(int *vec, int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 设置10个桶
const int bucketNum = 10;
// 定义二维数组
std::vector<int> buckets[bucketNum];
// 计算桶的最大尺寸
int bucketSize = 1;
while (max) {
max /= 10;
bucketSize *= 10;
}
bucketSize /= 10;
// 数据存入桶中
for ( int i = 0; i < len; ++i )
{
// 定义元素存放的桶号
int index = vec[i] / bucketSize;
buckets[index].push_back(vec[i]);
// 对该桶使用插入排序
for ( int j = int(buckets[index].size()) - 1; j > 0; --j )
{
if ( buckets[index][j] < buckets[index][j-1] ) {
int temp = buckets[index][j];
buckets[index][j] = buckets[index][j-1];
buckets[index][j-1] = temp;
}
}
}
// 顺序访问桶，得到有序数组
for ( int i = 0, k = 0; i < bucketNum; ++i )
{
for ( int j = 0; j < int(buckets[i].size()); ++j )
{
vec[k++] = buckets[i][j];
}
}
}
// 方法二
void BSortMethod::bucketSort2(int *vec, int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值，最小值
int min = vec[0];
int max = vec[0];
for ( int i = 1; i < len; ++i)
{
if ( vec[i] < min ) min = vec[i];
if ( vec[i] > max ) max = vec[i];
}
// 桶的大小
int bucketNum = (max - min) / len + 1;
// 二维数组动态分配内存
int **buckets = new int* [bucketNum];
for ( int i = 0; i < bucketNum; ++i )
{
buckets[i] = new int[bucketNum] {0};
}
// 动态分配内存，存储每个桶的元素个数
int *array = new int[bucketNum] {0};
// 数据存入桶中
for ( int i = 0; i < len; ++i )
{
// 定义元素存放的桶号
int index = (vec[i] - min) / len;
// 参考计数排序，填充统计数组
buckets[index][array[index]++] = vec[i];
}
int index = 0;
for ( int i = 0; i < bucketNum; ++i )
{
// 使用快速排序
quickSort(buckets[i], 0, array[i] - 1);
cout << i << "号桶的元素个数：" << array[i] << endl;
// 遍历桶中元素，依次存入原数组
for ( int j = 0; j < array[i]; ++j )
{
vec[index++] = buckets[i][j];
}
}
// 释放内存
delete[] buckets;
delete[] array;
}
基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
void BSortMethod::radixSort(int *vec, int len)
{
if ( len <= 0 ) {
return;
}
// 找到数组最大值
int max = vec[0];
for ( int i = 1; i < len; ++i )
{
if ( vec[i] > max ) {
max = vec[i];
}
}
// 计算最大值的位数
int maxBit = 1;
while ( max > 10 * maxBit )
{
maxBit++;
}
for ( int k = 0; k < maxBit; ++k )
{
// 定义桶（二维数组）
std::vector<std::vector<int>> bucket;
for ( int i = 0; i < 10; ++i )
{
std::vector<int> temp;
bucket.push_back(temp);
}
// 对每一位进行排序
for ( int i = 0; i < len; ++i )
{
// 得到每位的基数
int radix = int((vec[i] / (int)pow(10, k)) % 10);
// 将对应的数组元素添加到相应位基数的桶中
bucket[radix].push_back(vec[i]);
}
int index = 0;
for ( int i = 0; i < 10; ++i )
{
// 计算桶的元素个数
int size = (int)bucket[i].size();
if ( size != 0 ) {
// 桶不为空时，将桶中每个元素放回到数组中
for ( int j = 0; j < size; ++j )
{
vec[index++] = bucket[i][j];
}
}
}
}
}
#include "bsortmethod.h"
#include "iostream"
using namespace std;
int main()
{
int vec[15] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
int len = sizeof(vec) / sizeof(*vec);
BSortMethod sortM;
// sortM.bubbleSort(vec, len); // 冒泡排序
// sortM.selectionSort(vec, len); // 选择排序
// sortM.insertionSort(vec, len); // 插入排序
// sortM.shellSort(vec, len); // 希尔排序
// sortM.mergeSort(vec, len); // 归并排序
// sortM.quickSort(vec, 0, len-1); // 快速排序
// sortM.heapSort(vec, len); // 堆排序
// sortM.countingSort(vec, len); // 计数排序
// sortM.bucketSort(vec, len); // 桶排序1
// sortM.bucketSort2(vec, len); // 桶排序2
sortM.radixSort(vec, len); // 基数排序
for(int i = 0; i < 15; ++i)
cout << vec[i] << " ";
cout << endl;
}