#include <iostream>
using namespace std; // 插入排序开始=====================
void insert_sort(int a[], int n)
{
for (int cur = 1; cur < n; ++cur)
{
int j = cur - 1;
int t = a[cur];
while (j >= 0)
{
if (a[j] > t)
a[j+1] = a[j];
else
break;
--j;
}
a[j+1] = t;
}
}
// 插入排序结束===================== // 选择排序开始=====================
void select_sort(int a[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
int k = i;
for (int j = i + 1; j < n; ++j)
if (a[j] < a[k])
k = j;
swap(a[i], a[k]);
}
}
// 选择排序结束===================== // 冒泡排序开始=====================
void buble_sort(int a[], int n)
{
for (int k = 1; k <= n - 1; ++k)
{
int noswap = 1; //表示这一次没有交换
for (int j = n - 1; j >= k; --j)
if (a[j] < a[j-1])
{
swap(a[j], a[j-1]);
noswap = 0;
}
if (noswap) break;
}
}
// 冒泡排序结束===================== // 快速排序开始=====================
int quick_sort_partion(int a[], int p, int q)
{
int i = p - 1;
for (int j = p; j <= q - 1; ++j)
{
if (a[j] < a[q])
swap(a[j], a[++i]);
}
swap(a[++i], a[q]);
return i;
}
void quick_sort_helper(int a[], int b, int e)
{
if (b < e)
{
int mid = quick_sort_partion(a, b, e);
quick_sort_helper(a, b, mid - 1);
quick_sort_helper(a, mid + 1, e);
}
}
void quick_sort(int a[], int n)
{
quick_sort_helper(a, 0, n-1);
}
// 快速排序结束===================== // 归并排序开始=====================
void merge_sort_helper(int a[], int copy[], int b, int e)
{
if (b < e)
{
int mid = (e-b) / 2 + b;
merge_sort_helper(copy, a, b, mid);
merge_sort_helper(copy, a, mid + 1, e); int i = b, j = mid + 1, k = b;
while (i <= mid && j <= e)
{
a[k++] = (copy[i] < copy[j] ? copy[i++] : copy[j++]);
}
while (i <= mid)
a[k++] = copy[i++];
while (j <= e)
a[k++] = copy[j++];
}
}
void merge_sort(int a[], int n)
{
int *copy = new int[n];
memcpy(copy, a, sizeof(a[0])*n);
merge_sort_helper(a, copy, 0, n-1);
delete[] copy;
}
// 归并排序结束===================== // 堆排序开始=======================
void heap_sort_adjust(int a[], int n, int i)
{ if (i <= n/2 - 1) //判断是否是叶子结点
{
int left = 2*i+1;
int right = 2*i+2;
int maxIndex = i;
if (a[left] > a[maxIndex])
maxIndex = left;
if (right < n && a[right] > a[maxIndex])
maxIndex = right;
swap(a[i], a[maxIndex]);
if (i != maxIndex) //一定要判断，否则死循环
heap_sort_adjust(a, n, maxIndex);
}
}
void heap_sort_build(int a[], int n)
{
for (int i = n/2 -1; i >= 0; --i)
heap_sort_adjust(a, n, i); }
void heap_sort(int a[], int n)
{
heap_sort_build(a, n);
for (int i = n-1; i >= 1; --i)
{
swap(a[i], a[0]);
heap_sort_build(a, i);
}
}
// 堆排序结束======================= // 希尔排序开始=====================
void shell_sort(int a[], int n)
{
int d[3] = {5, 3, 1};
for (int k = 0; k < 3; ++k)
{
for (int cur = d[k]; cur < n; cur += d[k])
{
int j = cur - d[k];
int t = a[min(cur, n-1)];
while (j >= 0)
{
if (a[j] > t)
a[min(j+d[k], n-1)] = a[j];
else
break;
j -= d[k];
}
a[min(j+d[k], n-1)] = t;
}
}
}
// 希尔排序结束===================== // 基数排序开始=====================
//L表示关键码的个数
void radix_sort(int a[], int n, int L)
{
int *bucket = new int[n];
int count[10];
int power = 1; for (int k = 1; k <= L; ++k)
{
memset(count, 0, sizeof(count[0]) * n);
//统计每个桶的右边界
for (int i = 0; i < n; ++i) ++count[(a[i]/power)%10];
for (int i = 1; i < 10; ++i) count[i] += count[i-1];
//装桶,这里从后往前扫描是因为边界值是从右往左递减的
for (int i = n-1; i >= 0; --i) bucket[--count[(a[i]/power)%10]] = a[i];
//收集
memcpy(a, bucket, sizeof(a[0]) * n);
power *= 10;
}
delete bucket;
}
// 基数排序结束=====================
int main()
{
int a[10]={100,19,222,10,37,83,36,344,576,82};
radix_sort(a, 10, 3);
for (int i = 0; i < 10; ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
最后，贴出几大排序的平均时间复杂度和最坏时间复杂度，以供参考
关于排序的稳定性
稳定的排序有
插入排序：（每次插入都是从后往前，两个数一样的话不会交换位置）
冒泡排序：（每次冒上去的都是最小的，两个数相同不会交换）
归并排序：（如果两个相等的数在同一个区间，显然后面的数不会跑到前面去，如果在不同的区间，后半个区间在归并后显然也是排在后面，可对照上面的代码）
基数排序：（两个数相同，如果从左到右扫描，那么前面的数肯定先被扔进桶内，如果从右往左扫描，那么先将右边的数扔到桶的后面，上面排序过程即是如此）
如果记不住的话，那么鬼插鸡毛，还记得住啊？记住，鬼插鸡毛很稳定哦，其他的都不稳定
鬼：归并排序，插：插入排序，鸡：基数排序，毛：冒泡排序
来，和我一起读，鬼插鸡毛很稳定，鬼插鸡毛很稳定，鬼插鸡毛很稳定……读个99遍
关于时间复杂度，除了快速排序，其他排序的最低时间复杂度和最坏时间复杂度相同，因为逆序的数组每次划分都需要O(i)(i = n, n-1,...)的时间，所以快速排序最坏为O(n^2)
好了，就到这里吧，看不懂的留言，楼主保证秒回~