选择排序：
//通俗讲解：
//8 6 2 3 1 5 7 4
//从第一个开始往后遍历
//先把第一个8当作最小的元素，他的下标为minIndex
//从第二个开始往后遍历，查找比8小的数
//即6比8小，所以记录6的下标（为1），这时arr[minIndex]为6
//继续遍历，2比6小，所以minIndex=2了，这时arr[minIndex]为2，
//直到遍历结束，这时第一个位置（下标为0的位置）上一定是最小的数了，即为1；
//同上，继续。。。
template<typename T>
void selectionSort(T arr[], int n)
{
for (int i = 0; i < n; i++)//遍历数组
{
int minIndex = i;//记录下标（存放最小值的下标）
for (int j = i + 1; j < n; j++)//往后寻找比arr[min]小的元素
{
if (arr[j]<arr[minIndex])
{
minIndex = j;//更新下标
}
}
swap(arr[minIndex], arr[i]);//交换数据
}
}插入排序：
//通俗讲解：
//插入排序呢，顾名思义
//8 6 2 3 1 5 7 4
//有两个盒子A,B，一个存放已经排好序的元素，一个存放待排序的元素
//从第一个开始，由于未排序的盒子A为空，所以第一个元素不需要比较，直接就放入了未排序的盒子A
//第二个元素为6，与第一个元素（8）比较后小于，所以与8交换位置，序列变成了6 8 2 3 1 5 7 4
//第三个元素为2，交换后变成 2 6 8 3 1 5 7 4
//第四个元素为3，依次交换变成 2 3 6 8 1 5 7 4
//继续。。。。
template<typename T>
void insertionSort(T arr[], int n)
{
for (int i = 1; i < n; i++)
{
//1.
for (int j = i; j > 0; j--)
{
if (arr[j]<arr[j-1])
{
swap(arr[j],arr[j-1]);
}
else
{
break;//这样可以减少运算次数
}
}
//2.改进点：
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)//这样更简便
{
swap(arr[j], arr[j - 1]);
}
}**插入排序感觉是减少了运算量，但是给了一个int a[10000]的数组，
发现：
插入排序需要：2.5s左右；
选择排序需要：0.13s左右；
原因就是：插入排序需要交换的次数过多
//8 6 2 3 1 5 7 4
先复制一个6出来，让6与前面的进行比较
6小于8，所以，将8赋值给6，6继续往前比较，直到结束
复制出一个2；
//改进如下：，通过减少赋值操作来增大效率，每个swap就是3次交换，去除swap
for (int i = 1; i < n; i++)
{
int e = arr[i];//复制
int j;//存放要换的位置的下标
for ( j = i; j > 0&&arr[j-1]>e; j--)
{
arr[j] = arr[j-1];
}
arr[j - 1] = e;
}
}**改进后：
插入排序需要：0.11s左右；
选择排序需要：0.13s左右；
对于接近排好序的数组，则区别更加明显
插入排序需要：0.04s左右；
选择排序需要：0.13s左右；
**
冒泡排序
**
//代码：
template<typename T>
void bubbleSort(T arr[],int n)
{
//原始写法
/*for (int i = 0; i < n; i++) { for (int j =0; j < n-i-1; j++)//因为最大肯定在右边了，所以j只需要< n-i-1 { if (arr[j]>arr[j+1]) { swap(arr[j],arr[j+1]); } } }*/
//优化写法
bool swapped;
do
{
swapped = false;
for (int i = 1; i < n; i++)
{
if (arr[i]<arr[i-1])
{
swap(arr[i],arr[i-1]);
swapped = true;//如果将i到n遍历一遍后仍然没有交换，即swapped=false，则这个序列肯定已经排好序了，所以终止
}
}
n--;//因为最大的肯定在最右边，所以n--
} while (swapped);
}
优化前：
优化后：
**
希尔排序
**
增量依次减小
//代码：
template<typename T>
void shellSort(T arr[], int n){
int h = 1;
while( h < n/3 )
h = 3 * h + 1;
while( h >= 1 ){
// h-sort the array
for( int i = h ; i < n ; i ++ )
{
// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
//这下面跟插入排序大同小异，只是元素不同，这里的元素是arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]，即在arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]中查找最小值
T e = arr[i];
int j;
for( j = i ; j >= h && e < arr[j-h] ; j -= h )// j >= h 避免出现j<0
{
arr[j] = arr[j-h];
}
arr[j] = e;
}
h /= 3;//缩小增量因子
}
}
1W的数组测试：
100W的：
其他的已经需要很长很长时间了，长的都等不及了：
**
快速排序
**
//这个写法不像其他的写法一样，先从又往左找小于基数的，在从左往右找大于大于基数的，再两者换位置。（见第二种写法）
//这个写法是先遍历，找小于基数的，小于的话，交换位置，让小于的数，放在左边，大于的数不做改变，再稍加调整就会变成想要的效果。
// 对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r){
T v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for (int i = l + 1; i <= r; i++)
if (arr[i] < v){
j++;
swap(arr[j], arr[i]);
}
swap(arr[l], arr[j]);
return j;
}
// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){
if (l >= r)
return;
int p = __partition(arr, l, r);
__quickSort(arr, l, p - 1);
__quickSort(arr, p + 1, r);
}
template <typename T>
void quickSort(T arr[], int n){
__quickSort(arr, 0, n - 1);
}
第二种：
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/// ①
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*///因为上面①，把a[first]的原值给覆盖了，但是a[first]有副本key，所以需要重新赋值一下
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}
**
//合并排序/归并排序
**
#include<iostream>
using namespace std;
//合并排序/归并排序
template<typename T>
void __mergeSort(T arr[], int l, int mid, int r)
{
// 经测试,传递aux数组的性能效果并不好
//T aux[r - l + 1];
T *aux = new T[r - l + 1];
for (int i = l; i <= r; i++)
aux[i - l] = arr[i];//赋值
int i = l, j = mid + 1;
for (int k = l; k <= r; k++){
if (i > mid)
{
arr[k] = aux[j - l]; j++;
}
else if (j > r)
{
arr[k] = aux[i - l]; i++;
}
else if (aux[i - l] < aux[j - l])
{
arr[k] = aux[i - l]; i++;
}
else
{
arr[k] = aux[j - l]; j++;
}
}
delete[]aux;
}
template<typename T>
void MergeSort(T arr[], int l, int r)
{
if (l >= r)
{
return;
}
//优化1：
/*if (r - l <= 15)//由于小数量的排序，插入排序比归并更划算，所以这选择这样，这个数是测试得到的，不一定是15 { insertionSort1(arr, l, r); }*/
int mid = (r + l) / 2;
MergeSort(arr, l, mid);//先将这个运行到底 ①
MergeSort(arr, mid + 1, r);//这个，mid不是那个例如数组大小为6，mid=3那个mid，而是上步①结束时的mid
__mergeSort(arr, l, mid, r);
//优化2：
/* if(arr[mid] > arr[mid + 1])//例如这里第一次是1个和1个比，比完后，两个元素（数组A）和两个元素（数组B）比，这两个数组里的元素是已经排好序的，所以只需要比较arr[mid] 和 arr[mid + 1]就知道还需不需要去比较； { __mergeSort(arr, l, mid, r);//这个排序，排的是第一对（1边1个），在排第二对。。。然后下一轮第一对（1边2个）相排.。。 } */
}
int main()
{
int n;
cin >> n;
int *arr = new int[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
MergeSort(arr, 0, n-1);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
delete[]arr;
return 0;
}