下面对多种常见排序算法进行编程实现：
1、冒泡排序：
每轮 i 将前len-i-1个数的最大值通过索引 j 冒泡交换到数组最后，时间复杂度为
int* Bubble_Sort(int arr[], const int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
}
return arr;
}
2. 选择排序
一种直观的排序算法。从遍历，将数中最小的数与第i个数交换， 时间复杂度为。
int* Select_Sort(int arr[],const int len)
{
for (int i = 0; i < len-1; i++)
{
int minIndex = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3. 插入排序
对遍历，将arr[i]分别与之前的数对比，找到合适的位置插入，对比后的数组索引向后顺延。
int* Insert_Sort(int arr[], const int len)
{
for(int i=1;i=0 && current
4. 希尔排序
希尔排序(Shell's Sort)在插入排序算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进。其算法的基本思想是：先将待排记录序列分割成为若干子序列分别进行插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。
int* Shell_Sort(int arr[], const int len)
{
int increasement = len;
int i, j, k;
do
{ // 确定分组的增量
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++)
{
for(j=i+increasement;j= 0 && temp < arr[k]; k -= increasement)
{
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
} while (increasement > 1);
return arr;
}
5. 快速排序
快速排序（Quick sort）是对冒泡排序的一种改进，是非常重要且应用比较广泛的一种高效率排序算法。
快速排序是通过多次比较和交换来实现排序，在一趟排序中把将要排序的数据分成两个独立的部分，对这两部分进行排序使得其中一部分所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序。
大致步骤如下：
1.首先设置一个分界值也就是基准值又是也称为监视哨，通过该分界值将数据分割成两部分。
2.将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素。
3.然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
当左右两部分都有序时，整个数据就完成了排序。
void Quick_Sort(int* num, int l, int r) {
//如果小于等于1个数据元素·直接返回结束快排函数 r为数组元素总个数-1
if (l >= r)
return;
int first = l, last = r, key = num[first];
//从后往前找比key小的数
while(first= key)
last--;
//如果值小于 key分界值
num[first] = num[last];
//从前往后找比key大的数
while (first < last && num[first] < key)
first++;
//如果值大于key分界值
num[last] = num[first];
}
num[first] = key;
//递归左右部分进行快排
Quick_Sort(num, l, first);
Quick_Sort(num, first + 1, r);
}
主函数测试：
int main()
{
int arr[20] = {};
const int n=size(arr);
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100 + 1;
cout << arr[i] << ' ';
}
cout << endl;
int* A = Select_Sort(arr, n);
for (int i = 0; i < n; i++) {
cout << A[i] << ' ';
}
cout << endl;
int* B = Insert_Sort(arr, n);
for (int i = 0; i < n; i++) {
cout << B[i] << ' ';
}
cout << endl;
int* C = Bubble_Sort(arr, n);
for (int i = 0; i < n; i++) {
cout << C[i] << ' ';
}
cout << endl;
int* D = Shell_Sort(arr, n);
for (int i = 0; i < n; i++) {
cout << D[i] << ' ';
}
cout << endl;
Quick_Sort(arr, 0, n-1);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
cout << endl;
}
输出结果：
