注： ①第一个算法给出了完整的测试程序，其余的为避免重复及节省空间，只显示排序算法部分代码 ②运行结果的程序耗时每次运行略有不同，仅供大致对比参考
1.冒泡排序
时间复杂度：O(n)[最好]，O(n^2^)[平均]，O(n^2^)[最差]空间复杂度：O(1)代码：
代码语言：javascript复制#include<iostream>
#include<windows.h>//计时用
using namespace std;
//冒泡排序算法
void bubbleSort(int data[], int n)
{
//打印原始数据信息
cout << "n 待排序数据为：";
for (int i = 0; i < n; i )
cout << data[i] << " ";
//算法计时
LARGE_INTEGER nFreq, t1, t2;
double dt;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&t1);
//排序算法
int count = 0;
for (int i = 0; i < n - 1; i )
{
bool flag = true;//排序提前完成标志
for (int j = 0; j < n - i - 1; j )
{
if (data[j] > data[j 1])//改成'<'则为降序
{
swap(data[j], data[j 1]);
count ;
flag = false;
}
}
if (flag) break;
}
//打印结果信息
QueryPerformanceCounter(&t2);
dt = (t2.QuadPart - t1.QuadPart) / (double)nFreq.QuadPart;
cout << "n 此次排序耗时: " << dt * 1000000 << "us";
cout << "n 执行了"<<count<<"次swap交换";
cout << "n 排序结果为：";
for (int i = 0; i < n; i )
cout << data[i] << " ";
cout << endl;
}
//主函数
int main(void)
{
int testdata1[10] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
bubbleSort(testdata1, 10);
int testdata2[10] = { 0, 1, 2, 3, 4, 9, 8, 7, 6, 5 };
bubbleSort(testdata2, 10);
return 0;
}运行结果：
代码语言：javascript复制 待排序数据为：1 3 5 7 9 2 4 6 8 0
此次排序耗时: 2us
执行了19次swap交换
排序结果为：0 1 2 3 4 5 6 7 8 9
待排序数据为：0 1 2 3 4 9 8 7 6 5
此次排序耗时: 1.1us
执行了10次swap交换
排序结果为：0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .2.选择排序
时间复杂度：O(n^2^)[最好]，O(n^2^)[平均]，O(n^2^)[最差]空间复杂度：O(1)主要代码：
代码语言：javascript复制//n-1次外循环，每次选出最大的放在最右边
//内循环与最大值比较，记录最大值的标签
void selectSort(int data[], int n)
{
//打印原始数据信息（代码略，同上）
//算法计时（代码略）
//排序算法
//int count = 0;
for (int i = n - 1; i > 0; i--)
{
int max = i;
for (int j = i - 1; j >= 0; j--)//从后向前推，有点绕
{
if (data[j] > data[max])//改成'<'则为降序
max = j;
}
swap(data[max], data[i]);
//count ;
}
//打印结果信息（代码略）
}运行结果：
代码语言：javascript复制 待排序数据为：1 3 5 7 9 2 4 6 8 0
此次排序耗时: 1.1us
执行了9次swap交换
排序结果为：0 1 2 3 4 5 6 7 8 9
待排序数据为：0 1 2 3 4 9 8 7 6 5
此次排序耗时: 1us
执行了9次swap交换
排序结果为：0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .3.插入排序
时间复杂度：O(n)[最好]，O(n^2^)[平均]，O(n^2^)[最差]空间复杂度：O(1)主要代码：
代码语言：javascript复制//插入排序
void insertionSort(int* data, int n)
{
//打印原始数据信息（代码略，同上）
//算法计时（代码略）
//排序算法
int i, j;
for (i = 1; i < n; i )
{
int tmp = data[i];//待插入的值
j = i;//待插入的位置
while (j > 0 && data[j - 1] > tmp)//待插入的数较小
{
data[j] = data[j - 1];//前面的依次后移
j--;
}
data[j] = tmp;//插入值
}
//打印结果信息（代码略）
}运行结果：
代码语言：javascript复制 待排序数据为：1 3 5 7 9 2 4 6 8 0
此次排序耗时: 0.3us
排序结果为：0 1 2 3 4 5 6 7 8 9
待排序数据为：0 1 2 3 4 9 8 7 6 5
此次排序耗时: 0.2us
排序结果为：0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .4.快速排序
时间复杂度：O(nlogn)[最好]，O(nlogn)[平均]，O(n^2^)[最差]空间复杂度：O(logn)主要代码：
代码语言：javascript复制//轴点构造算法
int partition(int x[], int lo, int hi)
{
swap(x[lo], x[lo rand() % (hi - lo 1)]);//任选一个元素与首元素交换
int pivot = x[lo];//以首元素为候选轴点————经以上交换，等效于随机选取
while (lo < hi)//从向量两端交替向中间扫描
{
while ((lo < hi) && (pivot <= x[hi])) hi--;//不小于pivot下，向左拓展右端子向量
x[lo] = x[hi];//小于pivot者归入左侧序列
while ((lo < hi) && (x[lo] <= pivot)) lo ;//不大于pivot下，向右拓展左端子向量
x[hi] = x[lo];//大于pivot者归入右侧序列
}//assert:lo==hi
x[lo] = pivot;//将备份的轴点记录置于前后子向量之间
return lo;//返回轴点的秩
}
//整体快速算法
void quicksort(int x[], int lo, int hi)
{
if (hi - lo < 2) return;//单元素区间自然有序
int mi = partition(x, lo, hi - 1);//在[lo,hi-1]内构造轴点
quicksort(x, lo, mi);//对前缀递归排序
quicksort(x, mi 1, hi);//对后缀递归排序
}运行结果：
代码语言：javascript复制 待排序数据为：1 3 5 7 9 2 4 6 8 0
此次排序耗时: 5.1us
排序结果为：0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .5.归并排序
时间复杂度：O(nlogn)[最好]，O(nlogn)[平均]，O(nlogn)[最差]空间复杂度：O(n)主要代码：
代码语言：javascript复制//合并两个有序数组
void merge(int x[], int lo, int mi, int hi)
{
int *A = x lo;//设合并后为A(B C=A)
int lb = mi - lo;//B的长度
int *B = new int[lb];//先复制出一份B
for (int i = 0; i < lb; B[i] = A[i ]);
int lc = hi - mi;//C的长度
int *C = x mi;//C的指针起始位置（不用重新复制C）
for (int i = 0, j = 0, k = 0; j < lb; )//B未排完情况
{
if (k < lc && C[k] < B[j]) A[i ] = C[k ];//C也未完 且 C小（即两个都未完，复制小的C）
if (k >= lc || B[j] <= C[k]) A[i ] = B[j ];//C已完(只能复制B了) 或 B小(肯定要复制B)
}
delete[] B;
}
//整体归并算法
void mergesort(int x[], int lo, int hi)
{
if (hi - lo < 2) return;
int mi = (hi lo) / 2;
mergesort(x, lo, mi);
mergesort(x, mi, hi);
merge(x, lo, mi, hi);
}运行结果：
代码语言：javascript复制 待排序数据为：1 3 5 7 9 2 4 6 8 0
此次排序耗时: 4.4us
排序结果为：0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .此文首发于我的CSDN：https://blog.csdn.net/hbsyaaa/article/details/89765323
