一、希尔排序

思路：

希尔排序是属于插入排序，先对数组进行预排序，使数组相对有序，再进行直接插入排序
预排序的gap值可以取任意>=1的值，经测试效率最高的 gap取值为 gap/3 + 1，初始值为size
初始的有序度越高的数组，进行插入排序的效率就越高

时间复杂度：不稳定，与数组的初始有序度及gap的计算方法有关，介于O(n) ~ O(n^2)

void ShellSort(int* arr, int size) 
{int gap = size;while (gap > 1) {gap = gap / 3 + 1;int i = 0;for (i = 0; i < size - gap; ++i) {int end = i;int tmp = arr[end + gap];while (end >= 0 && tmp < arr[end]) {arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = tmp;}}
}

二、堆排序

思路：

将数组建堆，输出要升序就建大根堆，输出要降序就建小根堆
将堆顶的元素与与最后一个元素交换，从堆顶进行向下调整，调整的范围为size依次递减
堆可视为顺序存储的完全二叉树

时间复杂度：稳定，每次从堆顶向下调整为 lg(n)，总复杂度为 n * lg(n)

#include <stdio.h>void Swap(int* arr, int pi, int pj) 
{int tmp = arr[pi];arr[pi] = arr[pj];arr[pj] = tmp;
}//大根堆：升序
//小根堆：降序
void AdjustDown(int* arr, int parent, int size) 
{int child = parent * 2 + 1;while (child < size) {if (child + 1 < size && arr[child + 1] > arr[child]) ++child;if (arr[parent] < arr[child]) {Swap(arr, parent, child);parent = child;child = parent * 2 + 1;}else {break;}}
}void HeapSort(int* arr, int size) 
{int parent = (size - 2) / 2;int i;for (i = parent; i >= 0; --i) {AdjustDown(arr, i, size);   //构建大根堆}while (size) {Swap(arr, 0, --size);AdjustDown(arr, 0, size);}}

三、归并排序

思路：

递归思想，将一个数组从中间分为两个子数组，分别对两个子数组递归进行归并排序
子数组的最小长度为2或3，此时设置4个角标，begin1，end1，begin2，end2
begin1、end1代表左子数组的首尾，begin2、end2代表右子数组的首尾
同时遍历左右两个子数组，对比begin1和begin2对应的值，小的存入count数组
遍历结束之后，将count按地址按字节拷贝到arr，空间换时间

时间复杂度：稳定，递归的复杂度为 lg(n)，每个数都会遍历一次，总复杂度为 n * lg(n)

void _MergeSort(int* arr, int begin, int end, int* count) 
{if (begin >= end) return;int mid = (begin + end) / 2;_MergeSort(arr, begin, mid, count);_MergeSort(arr, mid + 1, end, count);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) count[i++] = arr[begin1++];else count[i++] = arr[begin2++];}while (begin1 <= end1) {count[i++] = arr[begin1++];}while (begin2 <= end2) {count[i++] = arr[begin2++];}memcpy(arr + begin, count + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* arr, int size) 
{int* count = (int*)malloc(sizeof(int) * size);int mid = size / 2;_MergeSort(arr, 0, mid, count);_MergeSort(arr, mid + 1, size - 1, count);free(count);count = NULL;
}

四、快速排序

思路：

递归思想，数组取一个关键字key值，将比key小的数排在key左边，比key大的数排在key右边
然后从key值处将数组切分为两个子数组，再分别对两个子数组进行快排递归
key值取首位、中间位、末尾的中位数，提高效率
前后指针法，先将中位数关键字放在首位，后指针的值每次都与首位关键字比较，最后返回front
为提高效率，可在end - begin < n 时使用直接插入排序而放弃快排递归，n根据数据量取值

时间复杂度：不稳定，平均复杂度是O(n * lg(n))

void Swap(int* arr, int pi, int pj) 
{int tmp = arr[pi];arr[pi] = arr[pj];arr[pj] = tmp;
}//取中位数
int MidNum(int* arr, int l, int m, int r) 
{if (arr[l] < arr[r]) {if (arr[m] < arr[l])return l;else if (arr[m] < arr[r])return m;elsereturn r;}else {if (arr[m] > arr[l])return l;else if (arr[m] > arr[r])return m;elsereturn r;}
}//前后指针法
int PtrPrt(int* arr, int begin, int end) 
{int mid = (begin + end) / 2;int keyi = MidNum(arr, begin, mid, end);Swap(arr, keyi, begin);int front = begin;int back = begin + 1;while (back <= end) {if (arr[back] < arr[begin] && ++front != back) Swap(arr, front, back);++back;}Swap(arr, begin, front);return front;
}void QuickSort(int* arr, int begin, int end) 
{if (begin >= end) return;int keyi = PtrPrt(arr, begin, end);QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);
}

五、计数排序

思路：

哈希思想，用空间换时间，找到arr数组中的最大值max和最小值min
创建(max - min + 1)个元素的count数组并置零，用于统计arr数组中每个数字的出现次数
遍历原数组，count[arr[i] - min]++，可用count记录原数组中每个数出现的次数
再遍历count数组，从小到大将数值写入arr数组中，完成排序
适用于arr数组中的最大值和最小值相差不大的情况

复杂度：不稳定，介于O(n) ~ O(n^2)

void CountSort(int* arr, int size) 
{int min = arr[0], max = arr[0];int i;for (i = 0; i < size; ++i) {if (arr[i] < min) min = arr[i];if (arr[i] > max) max = arr[i];}int* count = (int*)malloc(sizeof(int) * (max - min + 1));memset(count, 0, max - min + 1);for (i = 0; i < size; ++i) {count[arr[i] - min]++;}int j = 0;for (i = 0; i < max - min + 1; ++i) {while (count[i]--) {arr[j++] = i + min;}}
}

六、基数排序

思路：

为了代码方便使用C++，利用队列进行数据收发
创建一个队列数组，数组大小为10，每个元素都是一个队列，存储取模为 1 ~ 9 的数
从低位到高位进行数据收发，完成排序
适用于数据位数不高的情况

时间复杂度：与最大值的位数K有关，K * O(n)，所以时间复杂度为O(n)

#include <iostream>
#include <queue>
using namespace std;#define K 3     //数组中最大数据的位数
#define RADIX 10//定义基数
queue<int> g_q[RADIX];int GetKey(int val, int k) 
{int key = val % 10;while (k--) {val /= 10;key = val % 10;}return key;
}void Distribute(int* arr, int left, int right, int k) 
{for (int i = left; i <= right; ++i) {int key = GetKey(arr[i], k);g_q[key].push(arr[i]);}
}void Collect(int* arr) 
{int j = 0;for (int i = 0; i < RADIX; ++i) {while (!g_q[i].empty()) {arr[j++] = g_q[i].front();g_q[i].pop();}}
}void RadixSort(int* arr, int size) 
{for (int i = 0; i < K; ++i) {Distribute(arr, 0, size - 1, i);    //分发数据Collect(arr);       //收集数据}
}