Question

C++排序有哪几种最常用，最好用？

Answer 1

在C++排序中，最常用、最好用的有

1. 冒泡排序（bubble sort），时间复杂度为O(n^2)；

2. 鸡尾酒排序（Cocktail sort，双向的冒泡排序），时间复杂度为O(n^2)；

3. 快速排序（Quick sort，是对冒泡排序的一种改进），时间复杂度下界为O(nlogn)，最坏情况为O(n^2)；
   

4. 插入排序（insertion sort），时间复杂度为O(n^2)；

5. 希尔排序（Shell Sort，插入排序的一种，也称缩小增量排序），时间复杂度为O(nlog n) ；

6. 选择排序（selection sort），时间复杂度为O(n^2)；

7. 堆排序（Heap sort，选择排序的一种。），时间复杂度为O(nlog n)；

8. 归并排序（Merge sort），时间复杂度为O(nlog n)；

9. 基数排序（radix sort），时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数

在C++中有排序函数sort()，包含在<algorithm> 中，参数格式为

sort(a+begin,a+end)；

其中begin表示所需要排序的数组a的开头，end则表示所需要排序的数组a的最后一个元素的位置。

Answer 2

排序大类分为内排序和外排序，通常排序指的是内排序
内排序主要分为：
插入排序（直接插入排序，折半插入排序，Shell排序）
交换排序（冒泡排序，快速排序）
选择排序（简单选择排序，堆排序）
归并排序
基数排序
每种排序根据问题的规模以及初始排序表排列情况性能而不同，一般来讲，快速排序的平均性能最好。在C++中，可以使用标准库算法中的sort进行排序，它会根据情况动态地选择一种高效排序算法。

Answer 3

通常有插入，冒泡，桶，交换排序，堆排序，根据数据量大小各有优缺点。STL提供的快速排序能够动态的根据数量多少选择经验上最恰当的排序算法，所以std::sort是集成了所有排序有点的最好排序算法

Answer 4

冒泡排序O(n2)，快速排序（常有），归并排序（较好），选择排序，插入排序。具体排序实现百度之