排序算法描述
1、概念
通过一定的方法将杂乱的数据按照一定的规则（比如升序，降序等）排列的过程叫做排序。
2、分类
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
3.比较
冒泡排序
冒泡排序，重复地走访过要排序的元素列，按照需要的顺序（比如升序或降序）依次比较两个相邻的元素，如果他们的顺序错误就交换位置。走访元素的工作是重复地进行直到没有相邻元素需要交换，即完成冒泡排序。
冒泡排序" />
算法实现
void BubbleSort(int a[], int size)
{
int temp = 0;
for (int i = 0; i < size; i++)
{
for (int j = 1; j<size; j++)
{
if (a[j]<a[j - 1])//升序
{
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}
从算法的实现思路展示的动图，我们可以对代码稍微进行减枝，去掉已经无需在进行排序的末尾端数据和数据是顺序的情况。
void BubbleSort(int a[], int size)
{
int temp = 0;
for (int i = 0; i < size; i++)
{
// 标志位，用于判断一轮查询里面是否全是顺序的情况
int flag = 0;
// size - i 剪枝，过滤已完成排序的末端
for (int j = 1; j < size - i; j++)
{
if (a[j] < a[j - 1])// < 升序， > 降序
{
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
flag = 1;
}
}
if (flag == 0) break;
}
}
选择排序
选择排序的实现原理，第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序" />
算法实现
// 方式一（和冒泡类似，注意区别）
void Selectsort(int a[], int n)
{
int temp = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[i] < a[j]) // < 降序，> 升序
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
// 方式二，减少替换次数
void Selectsort(int a[], int n)
{
int nMinIndex = 0;
int temp = 0;
for (int i = 0; i < n; i++)
{
nMinIndex = i; //找最小元素的位置
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[nMinIndex])
{
nMinIndex = j;
}
}
//将这个元素放到无序区的开头
temp = a[i];
a[i] = a[nMinIndex];
a[nMinIndex] = temp;
}
}
插入排序
插入排序，在要排序的元素中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
算法实现
void Insertionsort(int a[], int size)
{
//循环从第2个元素开始
int temp = 0;
for (int i = 1; i < size; i++)
{
if (a[i] < a[i - 1])
{
int j = i - 1;
temp = a[i];
for (; j >= 0 && a[j] > temp; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
}
希尔算法
1、概念
希尔排序，又称“缩小增量排序”，也是插入排序的一种，希尔排序在时间效率上其他排序有很大的改进。
2.实现思路
在使用直接插入排序算法时，如果表中的记录只有个别的是无序的，多数保持有序，这种情况下算法的效率也会比较高；除此之外，如果需要排序的记录总量很少，该算法的效率同样会很高。希尔排序就是从这两点出发对算法进行改进得到的排序算法。
希尔排序的具体实现：先将整个记录表分割成若干部分，分别进行直接插入排序，然后再对整个记录表进行一次直接插入排序。
算法实现
void ShellSort(int data[], int len)
{
//这里的初始增量是len/2，以后增量每次缩小一倍
int gap = len / 2;
while (gap > 0)
{
//对每个子序列进行直接插入排序
for (int i = gap; i < len; i++)
{
int temp = data[i];
int k = i - gap;
while (k >= 0 && data[k] > temp)
{
data[k + gap] = data[k];
k -= gap;
}
data[k + gap] = temp;
}
gap /= 2;
}
}
归并排序
1、概念
归并排序（英语：Merge sort，或mergesort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
2.实现思想
归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
③动图演示：
算法实现
void merge(int data[], int lt, int mid, int rt)
{
int len = rt - lt + 1;
//开辟一个新的数组，将原数组映射进去
int *temp = new int[len];
for (int m = lt; m <= rt; m++)
{
temp[m - lt] = data[m];
}
int i = lt, j = mid + 1;//i和j分别指向两个子数组开头部分
for (int k = lt; k <= rt; k++)
{
if (i > mid)
{
data[k] = temp[j - lt];
j++;
}
else if (j > rt)
{
data[k] = temp[i - lt];
i++;
}
else if (temp[i - lt] < temp[j - lt])
{
data[k] = temp[i - lt];
i++;
}
else
{
data[k] = temp[j - lt];
j++;
}
}
delete[] temp;
}
//递归的使用归并排序，对data[l....r]排序
void merge_sort(int data[], int l, int r)
{
if (l >= r)
return;
int mid = (l + r) / 2;
merge_sort(data, l, mid);
merge_sort(data, mid + 1, r);
merge(data, l, mid, r);
}
快速排序
1、概念
快速排序（Quicksort）是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2、时间复杂度
最好情况（待排序列接近无序）时间复杂度为O(nlog2n)，最坏情况（待排序列接近有序）时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。
3、实现思路
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
算法实现
void quickSort(int data[], int left, int right)
{
int i, j, temp;
if (left > right)
return;
temp = data[left]; //temp中存的就是基准数
i = left;
j = right;
while (i != j)
{
while (data[j] >= temp && i < j)//先从右边开始找
j--;
while (data[i] <= temp && i < j)//再找右边的
i++;
if (i < j)//交换两个数在数组中的位置
{
swap(data[i], data[j]);
}
}
//最终将基准数归位
data[left] = data[i];
data[i] = temp;
quickSort(data, left, i - 1);//继续处理左边的(递归)
quickSort(data, i + 1, right);//继续处理右边的(递归)
}
堆排序
1、概念
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2、实现思路
堆排序是将待排序的数组在排序开始时建成大顶堆或者小顶堆，而后将堆顶元素与数组最后一个元素交换，将剩下的元素作为新的堆进行调整，反复这一过程直到所有堆中只剩一个元素。通过大顶堆的方式得到的数据序列是升序序列，而小顶堆则相反。
算法实现
大顶堆算法实现：
//将子树调整为大根堆,升序序列
void adjustMaxHeap(int *arr, int adjustPoint, int len)
{
int son = adjustPoint * 2 + 1;//传入的是数组下标，需要+1修正，son是左子树的下标
int dad = adjustPoint;//父节点下标
while (son < len)
{
if (son + 1 < len && arr[son] < arr[son + 1])//找到子节点中最大的节点
{
son++;
}
if (arr[son] > arr[dad])//如果子节点大于父节点，交换父子节点
{
swap(arr[son], arr[dad]);
dad = son;//以当前节点为父节点向下调整
son = 2 * dad + 1;//获得下次检查的子节点下标
}
else{
break;
}
}
}
void myMaxHeapSort(int *arr, int len)
{
//step1 建立初始大根堆
//从最后一个叶子节点的父亲节点开始调整
for (int i = len / 2 - 1; i >= 0; i--)
{
adjustMaxHeap(arr, i, len);
}
//step2 将堆顶元素逐一调整到列表最后（输出）
swap(arr[0], arr[len - 1]);
for (int i = len - 1; i > 0; i--)
{
//将堆顶元素输出后对剩下的元素做大顶堆调整
adjustMaxHeap(arr, 0, i);
swap(arr[0], arr[i - 1]);
}
}
小顶堆算法实现：
//将数据调整为小顶堆
void adjustMinHeap(int *arr, int adjpoint, int len)
{
int dad = adjpoint;
int son = dad * 2 + 1;
while (son < len)
{
if (son + 1 < len && arr[son] > arr[son + 1])//获得较小的子节点
{
son++;
}
if (arr[son] < arr[dad])
{
swap(arr[son], arr[dad]);
dad = son;
son = dad * 2 + 1;
}
else{
break;
}
}
}
//小顶堆排序,降序
void myMinHeapSort(int *arr, int len)
{
int i;
//step 1 初始建立小顶堆
for (i = len / 2 - 1; i >= 0; i--)
{
adjustMinHeap(arr, i, len);
}
//step2 将小顶堆输出
swap(arr[len - 1], arr[0]);
for (i = len - 1; i > 0; i--)
{
adjustMinHeap(arr, 0, i);
swap(arr[i - 1], arr[0]);
}
}
基数排序
1、概念
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort。，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序有两种，一种是高位优先，一种是低位优先。
2.时间复杂度
基数排序的时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数
3、实现思路
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
算法实现
大顶堆算法实现：
int getDes(int data[], int n){
int max = data[0];
for (int i = 1; i < n; i++){
if (max < data[i]){
max = data[i];
}
}
int k = 0;
while (max) {
max /= 10;
k++;
}
return k;
}
void basesort(int date[], int n)
{
int maxx = getDes(date, n);//取得最大位数
int num = 1;
//位数决定排序循环次数
for (int i = 0; i < maxx; i++){
//for (int ct = 0; ct < n; ct++)
// printf("%d ", date[ct]);
// printf("\n");
int count[10] = { 0x0 };//声明count为了统计每个桶放了几个数
//int temp[10][len] = { 0x0 };//temp相当于桶，前一个数标记第几个篮子，后一个为了标记放的个数
//这里由于vs不支持动态数组，方便调试直接使用1024
int temp[10][1024] = { 0x0 };
for (int j = 0; j < n; j++){
//num是变量，因为每次循环比较的位是不同的
int mod = (date[j] / num) % 10;
count[mod]++;
int te = count[mod] - 1;
temp[mod][te] = date[j];//把数据放mod桶的te位上存储
}
int b = 0;
for (int h = 0; h < 10; h++){
if (count[h] > 0)
{
//count[h]是h桶的存储个数
for (int v = 0; v < count[h]; v++){
date[b] = temp[h][v];//把桶内排好的数全都倒给要排序的数组，进行下轮排序
b++;
}
}
}
num = num * 10;
}
}
参考资料
https://www.toutiao.com/a6593273307280179715/?iid=6593273307280179715
https://www.jianshu.com/p/cccf5b6e0e86
![新手疑惑的import导包 [golang 学习笔记1]](https://img-blog.csdnimg.cn/20200325111430697.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhbGx5ejk0NQ==,size_16,color_FFFFFF,t_70)