7种常见排序

1 直接插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。


void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; ++i){//划分区间【0，end】int end = i;//保存需要插入的值int temp = a[end + 1];while (end >= 0){if (a[end] > temp) //这是temp，不是a[end+1]{a[end + 1] = a[end];end--;}else{break;}}a[end+1] = temp;}
}

直接插入排序的特性总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定

2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

其实就是是直接插入排序的优化，用分组的思想将数据进行预排序，将无序序列变得基本有序，最后使用直接插入排序。

这里gap最好为N/3+1，这样对于普遍数据排序效率相对更高，更优。


void ShellSort(int* a, int n)
{//gap大于一为预排序，让数字接近有序int gap=n;while (gap > 1){gap = gap / 3 + 1; //保证最后一次一定是1//gap等于1相当于插入排序for (int i = 0; i < n - gap; i++){int end = i;int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}printArray(a, n);}
}

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(N^1.25)~O(1.6*N^1.25)来算。

4. 稳定性：不稳定

3 选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

但是这是可以优化的，我们可以每次找出最大和最小的，将最大的放最后，最小的放最前面，就能完成升序，效率会快一半。


void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = a[begin];int min = a[begin];for (int i = begin; i <= end; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(&a[min], &a[begin]);if (max == begin){max = min;}Swap(&a[max], &a[end]);end--;begin++;}
}

4 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。


//堆排序//向下调整
void AjustDown(int*a,int n,int root)
{int parent = root;int child = parent * 2 + 1;while (child<n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{int parent = (n - 1 - 1) / 2;
//建堆for (int i = parent; i >= 0; i--){AjustDown(a, n, i);}printArray(a, n);int end = n-1;
//将堆顶放最后while (end > 0){Swap(&a[0], &a[end]);AjustDown(a, end, 0);end--;}}

直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

5 冒泡排序

将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

void BubbleSort(int* a, int n)
{int end = n-1;while (end > 0){int overCase = 0;for (int i = 0; i < end; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);overCase = 1;}}if (overCase == 0){break;}end--;}}

冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

6 快排

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有

1.左右指针

确定一个基准值，一般选取数组最后一个元素小标为key，然后L先从前往后遍历找到大于key的数，再R从后往前遍历找到小于key的数，然后交换L与R的数组元素，直到L与R指向同一个空间，此时再把key 与L或者R指向的元素交换，这只是其中一趟排序。

此时整个数组就被L和R指针所指向的空间分成了左右两块，左边的都小于8，右边都大于8。

//左右指针法
int PartSort1(int* a, int begin,int end)
{/*int midIndex=GetMidIndex(a,begin,end);Swap(&a[midIndex], &a[end]);*/int key = end;while (begin < end){//找大while (begin < end&&a[begin] <= a[key]){begin++;}//找小while (begin < end&&a[end] >= a[key]){end--;}Swap(&a[end], &a[begin]);}Swap(&a[key], &a[begin]);return begin;
}

2.挖坑法

这样就以5为中间值，左边都小于5，右边都大于5。

//挖坑法 
int PartSort3(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[mid], &a[end]);int key = a[end];while (begin < end){while(begin < end && a[begin] <= key){begin++;}a[end] = a[begin];while (begin<end&&a[end] >= key){end--;}a[begin] = a[end];}a[begin] = key;return begin;
}

3.前后指针

这时就分出左边都小于5，右边都大于5。


//前后指针法
int PartSort2(int* a, int begin, int end)
{int prev = begin-1;int cur = begin;int keyIndex = end;while (cur < end){if (a[cur] <a[keyIndex]&&++prev!=cur)Swap(&a[prev], &a[cur]);cur++;}prev++;Swap(&a[prev], &a[keyIndex]);return prev;
}

4.快排代码

//找到中间大的数，优化处理
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[mid] < a[begin]){if (a[mid] > a[end]){return mid;}else if (a[a[begin] < a[end]]){return begin;}else{return end;}}else{if (a[mid] < a[end]){return mid;}else{return end;}}
}
//左右指针法
int PartSort1(int* a, int begin,int end)
{/*int midIndex=GetMidIndex(a,begin,end);Swap(&a[midIndex], &a[end]);*/int key = end;while (begin < end){//找大while (begin < end&&a[begin] <= a[key]){begin++;}//找小while (begin < end&&a[end] >= a[key]){end--;}Swap(&a[end], &a[begin]);}Swap(&a[key], &a[begin]);return begin;
}//前后指针法
int PartSort2(int* a, int begin, int end)
{int prev = begin-1;int cur = begin;int keyIndex = end;while (cur < end){if (a[cur] <a[keyIndex]&&++prev!=cur)Swap(&a[prev], &a[cur]);cur++;}prev++;Swap(&a[prev], &a[keyIndex]);return prev;
}//挖坑法 
int PartSort3(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[mid], &a[end]);int key = a[end];while (begin < end){while(begin < end && a[begin] <= key){begin++;}a[end] = a[begin];while (begin<end&&a[end] >= key){end--;}a[begin] = a[end];}a[begin] = key;return begin;
}void QuickSort(int* a, int left,int right)
{if (left >= right) return;int div = PartSort1(a, left, right);QuickSort(a,left, div - 1);QuickSort(a,div+1,right);
}

5.快排优化

5.1 三数取中法选key

int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[mid] < a[begin]){if (a[mid] > a[end]){return mid;}else if (a[a[begin] < a[end]]){return begin;}else{return end;}}else{if (a[mid] < a[end]){return mid;}else{return end;}}
}

5.2 递归到小的子区间时，可以考虑使用插入排序

void QuickSort(int* a, int left,int right)
{if (left >= right) return;if (right - left + 1 > 10){int div = PartSort3(a, left, right);QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);}else{InsertSort(a+left, right - left + 1);}}

5.3 快排的非递归形式

这样是为了保证出栈时候，第一个就是数组的最左，第二个就是数组的最右。

//快排非递归
void QuickSortNonR(int* a, int begin, int end)
{Stack s;StackInit(&s);//先把得到的数组的末尾和头入栈StackPushBack(&s, end);StackPushBack(&s, begin);while (!StackEmpty(&s)){//得到需要排序数组的左指针int left = StackTop(&s);StackPopBack(&s);//出栈//得到右指针int right = StackTop(&s);StackPopBack(&s);//得到基准值，左边都小于他，右边都大于他int div = PartSort3(a, left, right);if (left < div - 1) //[left,div-1]区间大于1个元素就进栈，小于等于1个就不用排了{StackPushBack(&s, div - 1);StackPushBack(&s, left);}if (div + 1 < right)//[div,right]区间大于1个元素就进栈，小于等于1个就不用排了{StackPushBack(&s, right);StackPushBack(&s, div + 1);}}StackDestory(&s);//销毁栈
}