排序复习

# 排序复习

创建时间：2020/2/5 0:29

C++STL Sort实现

1. 数据量大时采用QuickSort快排算法，分段归并排序。
2. 一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。
3. 如果递归层次过深，还会改用HeapSort堆排序。

https://blog.csdn.net/qq_35440678/article/details/80147601

stable_sort

会对一段元素进行排序并保证 维持相等元素的原始顺序 sort是快速排序实现，因此是不稳定的； stable_sort是归并排序实现，因此是稳定的。

string str1 = "test";
string str2 = "test";

• sort是快速排序实现，因此是不稳定的；stable_sort是归并排序实现，因此是稳定的。
• 如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable_sort则要求参数被限定为const，否则编译不能通过。

快速排序

给基准数据找其正确索引位置的过程

1. 先从数列中取出一个数作为基准数
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3. 再对左右区间重复第二步，直到各区间只有一个数

挖坑填数过程：

1. i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2. j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

string str1 = "test";
string str2 = "test";