十大排序
排序方法有十种，分别是：一、冒泡排序；二、选择排序；三、堆排序；四、插入排序；五、希尔排序；六、归并排序；七、快速排序；八、计数排序；九、桶排序；十、基数排序。
O(n)都是理想情况，不用排序
一、冒泡排序
直接上代码。
//找到当前最大的数不断向后冒泡，直至最后一个最小的数
void bubbleSort(int a[],int len)
{
for(int i = 0; i<len; ++i)
//排在最后的数已比较过是最大的，不用再比较
for(int j = 0; j < len-i-1; ++j)
if(a[j] > a[j+1]) //升序
swap(a[j],a[j+1]); //c++交换两个数
}
模拟一下：
5 3 7 9 6 2 8
3 5 7 6 2 8 9
3 5 6 2 7 8 9
3 5 2 6 7 8 9
3 2 5 6 7 8 9
2 3 5 6 7 8 9
时间复杂度O(n)~O（n2）
二、选择排序
直接上代码。
//选择当前最小的数，将其排在当前对应的最小数的位置即可
void selectionSort(int a[], int len)
{
for (int i = 0; i < len - 1; ++i)
{
int minpos = i, temp = i;
for ( int j = i + 1; j < len; ++j)
if (a[j] < a[minpos]) //寻找最小的数
minpos = j; //将最小数的索引保存
swap(a[temp],a[minpos]);
}
}
模拟一下：
5 3 7 9 6 2 8
2 3 7 9 6 5 8
2 3 7 9 6 5 8
2 3 5 9 6 7 8
2 3 5 6 9 7 8
2 3 5 6 7 9 8
2 3 5 6 7 8 9
时间复杂度O(n)~O（n2）
三、堆排序
直接上代码。
//堆排序，近似二叉树的一种处理方法。
//大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
//小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。
//构建大顶堆
void heapmax(int a[], int i, int len)
{
// 调整i位置的结点
// 先保存当前结点的下标
int max = i;
int lchild = i * 2 + 1; //左节点
int rchild = i * 2 + 2; //右节点
if (lchild < len && a[lchild] > a[max]) max = lchild;
if (rchild < len && a[rchild] > a[max]) max = rchild;
// 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
if (max != i)
{
swap(a[max],a[i]);
heapmax(a, max, len);
}
}
// 堆排序
void heapSort(int a[], int len)
{
// 初始化堆
// len / 2 - 1是二叉树中最后一个非叶子结点的序号
for (int i = len / 2 - 1; i >= 0; --i)
{
heapmax(a, i, len);
}
// 交换堆顶元素和最后一个元素
for (int i = len - 1; i >= 0; --i)
{
swap(a[0],a[i]);
heapmax(a, 0, i);
}
}
具体如图：
时间复杂度：O(nlogn)。
四、插入排序
直接上代码。
//将当前数与前面的数进行比较，如果小，就插入
void insertionSort(int a[],int len)
{
for (int i = 1; i < len; ++i)
{
int pos = i - 1; //标记位置
int temp = a[i]; //记录当前数
while (pos >= 0 && a[pos] > temp) //找到插入的位置
{
arr[pos + 1] = arr[pos]; //将大的数向后移，但又不超过当前位置
--pos; //pos -= 1；
}
if(pos + 1 != i)
arr[pos + 1] = current;
}
return arr;
}
模拟一下：
5 3 7 9 6 2 8
3 5 7 9 6 2 8
3 5 7 9 6 2 8
3 5 7 9 6 2 8
3 5 6 7 9 2 8
2 3 5 6 7 9 8
2 3 5 6 7 8 9
时间复杂度O(n)~O（n2）
五、希尔排序
直接上代码。
//希尔排序建立在直接插入排序的基础上：直接插入排序 d=1，shell 排序 d=x;
//将直接排序分组进行；
//d:初始增量(分组数)
void shellSort(int a[], int len, int d)
{
for(int inc = d; inc > 0; inc /= 2) //d=1，相当于直接插入排序
{
for(int i = inc; i < len; ++i)
{
int pos = i - inc;
int temp = a[i];
while(pos >= 0 && a[pos] > temp) //对应直接插入排序，1 == inc
{
a[pos+inc] = a[pos];
pos -= inc;
}
if((pos + inc) != i)
a[pos + inc] = temp;
}
}
}
模拟一下：
d=4;如图：
时间复杂度： O(n）~O（n2),
六、归并排序（二路归并排序）
直接上代码。
// 两两归并比较大小，再两两合并比较大小交换，最后合在一起排序。
void mergeSort(int a[], int start, int end, int *temp)
{
if (start >= end) return ; //收尾相等，归并完毕
int mid = (start + end) / 2;
mergeSort(a, start, mid, temp);
mergeSort(a, mid + 1, end, temp);
// 合并两个有序序列
int len = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (a[i_start] < a[j_start]) temp[len++] = a[i_start++];
else temp[len++] = a[j_start++];
}
while (i_start <= i_end) temp[len++] = a[i_start++];
while (j_start <= j_end) temp[len++] = a[j_start++];
//把辅助空间的数据放到原空间
for (int i = 0; i < len; i++) a[start + i] = temp[i];
}
时间复杂度：O(nlogn)
七、快速排序
//建立在冒泡排序的基础上
//不断向两边扫并设定指定的值，将小、大的放在key的两边。
void quickSort(int a[],int l, int r)
{
if(l >= r) return;
int left = l, right = r;
int key = a[left]; /*用数组的第一个记录作为分区元素*/
while(left != right)
{
/*从右向左扫描，找第一个码值小于key的记录，并交换到key*/
while(left < right && a[right] >= key) --right;
a[left] = a[right];
/*从左向右扫描，找第一个码值大于key的记录，并交换到右边*/
while(left < right && a[left] <= key) ++left;
a[right] = a[left];
}
a[left] = key; /*分区元素放到正确位置*/
quickSort(a,l,left-1);
quickSort(a,left+1,r);
}
时间复杂度：O(nlogn）~O(n2)
八、计数排序
直接上代码：
//标记，输出，快，有局限性
#define MAXNUM 20 //待排序数的最大个数
#define MAX 100 //待排序数的最大值
int count[MAXNUM] = {0};
int ans[MAXNUM] = {0};
void countSort(int a[], int count[], int n)
{
//统计i的次数
for(int i = 0; i < n; ++i) ++count[ a[i] ];
//对所有的计数累加，作用是统计a数组值和小于a数组值出现的个数
for(int i = 1; i <= MAX; ++i) count[i] += count[i - 1];
//逆向遍历源数组（保证稳定性），根据计数数组中对应的值填充到新的数组中
for(i = n - 1; i >= 0; --i)
ans[ --count[ a[i] ] ] = a[i];
}
时间复杂度：O(n+k)
九、桶排序
直接上代码：
//分类，将一段内的数，放在“桶”内，进行桶内部排序，组合桶。
//代码仅供参考
typedef struct node
{
int keyNum; //桶中数的数量
int key; //存储的元素
struct node *next;
}KeyNode;
//keys待排序数组，size数组长度，bucket_size桶的数量
void incSort(int keys[],int size,int bucket_size)
{
KeyNode* k=(KeyNode *)malloc(sizeof(KeyNode)); //用于控制打印
int i,j,b;
KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *));
for(i = 0; i<bucket_size; i++)
{
bucket_table[i] = (KeyNode *)malloc(sizeof(KeyNode));
bucket_table[i]->keyNum = 0;//记录当前桶中是否有数据
bucket_table[i]->key = 0; //记录当前桶中的数据
bucket_table[i]->next = NULL;
}
for(j=0;j<size;j++)
{
int index;
KeyNode *p;
KeyNode *node = (KeyNode *)malloc(sizeof(KeyNode));
node->key = keys[j];
node->next = NULL;
index = keys[j]/10; //映射函数计算桶号
p = bucket_table[index]; //初始化P成为桶中数据链表的头指针
if(p->keyNum == 0)//该桶中还没有数据
{
bucket_table[index]->next = node;
//桶的头结点记录桶内元素各数，此处加一
++(bucket_table[index]->keyNum);
}
else //该桶中已有数据
{
//链表结构的插入排序
while(p->next != NULL && p->next->key <= node->key)
p = p->next;
node->next = p->next;
p->next = node;
++(bucket_table[index]->keyNum);
}
}
//打印结果
for(b=0; b < bucket_size; b++)
//判断条件是跳过桶的头结点，桶的下个节点为元素节点不为空
for(k=bucket_table[b]; k->next != NULL; k = k->next)
{
printf("%d ",k->next->key);
}
}
时间复杂度：O(n+k) k为桶内排序所需时间。
十、基数排序
按位（个十百千万…）对应的数，分类，计数，从高位开始，依次比较，高位相同，降位，到最后即可，
图解：
以【520 350 72 383 15 442 352 86 158 352】序列为例，排序过程描述如下：
代码：
//代码仅供参考
/********************************************************
*函数名称：GetDigitInPos
*参数说明：num 一个整形数据
* pos 表示要获得的整形的第pos位数据
*说明： 找到num的从低到高的第pos位的数据
*********************************************************/
inline int GetDigitInPos(int num,int pos)
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
/********************************************************
*函数名称：RadixSort
*参数说明：unorderArray无序数组；
* dataNum无序数据个数
*说明： 基数排序
*时间复杂度：O(dn),d无序数最大位数，n无序数个数
*********************************************************/
#define RADIX 10 //整形排序,基数为10,需要十个桶
#define KEYNUM 10 //关键字位数，这里为整形位数
inline void RadixSort(int* unorderArray, int dataNum)
{
int *radixArrays[RADIX]; //分别为0~9基数的存放空间
for (int i=0; i<10; i++)
{
radixArrays[i] = (int *)malloc(sizeof(int)*(dataNum + 1));
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos=1; pos<=KEYNUM; pos++) //从个位开始入桶并出桶
{
for (int i=0; i<dataNum; i++) //分配过程
{
int num = GetDigitInPos(unorderArray[i],pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = unorderArray[i];
}
for (int i=0, j=0; i<RADIX; i++)//收集
{
for (int k = 1; k <= radixArrays[i][0]; k++)
unorderArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0; //出桶完毕，复位
}
}
}
时间复杂度：O(k*n) k最多位数的位数。
资源参考：
链接一: https://blog.csdn.net/a20180825/article/details/76608531
链接二: https://blog.csdn.net/liang_gu/article/details/80627548
链接三: https://blog.csdn.net/k346k346/article/details/45576137