技巧：先处理 内层 一次排序，在处理外面

直接插入排序

升序
最坏(遇到降序)：O(N^2) 等差数列 1+2+3+…+(n-1) = (n^2-n)/2
最好(有序) O(N)

希尔排序

gap 任何数字/2都是=1
gap/3 +1 保证gap最后是1

gap是多少 就分了多少组,每组数据可能少一点，但是肯定能分成gap组，前提是gap<n,也就是希尔的gap/2,gap/3+1，如果gap>n是不够分成gap组，比如gap=4,n=3分不成

时间复杂度分析

外层while(gap>1)----LogN
里面gap 很大 可以算出精确的2n 认为是N
gap=1 n 认为是N
gap变小过程中 ，N的变化

这里面就无法算出精确的了
结论：N^1.3

//N^1.3
void ShellSort(int* a, int n)
{//gap>1 预排序//gap == 1 直接插入排序int gap = n;while (gap > 1){//gap /= 2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;//tmp>a[end] 结束}}a[end + gap] = tmp;}//PrintArray(a, n);}}

选择排序

最烂的排序

最坏：N^2 N N-2 N-4 … 等差数列
最好：N^2
N-2还是优化后的，遍历一遍可以选出最大最小
不优化每次选出最小，选出一个

//最坏：N^2  N N-2 N-4 ...等差数列
//最好：N^2
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int min = left, max = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[left], &a[min]);if (left == max){max = min;}Swap(&a[right], &a[max]);left++;right--;}}

堆排序

O(NlogN)

交换排序

交换排序（冒泡，快排） 是把数据进行交换，也就是Swap() 就像不能直接站到同学的脑袋上去

冒泡排序

如果不加flag优化 时间复杂度 O(N^2) 等差数列 N-1 N-2…1
优化 最好O(N) 最坏O(N^2)

void BubbleSort(int* a, int n)
{for (int j = 1; j <= n - 1; j++){bool ExChange = false;for (int i = 0; i < n - j; i++){if (a[i + 1] < a[i]){Swap(&a[i + 1], &a[i]);ExChange = true;}}if (ExChange == 0){break;}}}

快速排序