排序
一、排序办法与复杂度归类
（1）几种最经典、最罕用的排序办法：冒泡排序、插入排序、抉择排序、疾速排序、归并排序、计数排序、基数排序、桶排序。
（2）复杂度归类
冒泡排序、插入排序、抉择排序 O(n^2)
疾速排序、归并排序 O(nlogn)
计数排序、基数排序、桶排序 O(n)
二、如何剖析一个“排序算法”？
<1> 算法的执行效率
- 最好、最坏、均匀状况工夫复杂度。
- 工夫复杂度的系数、常数和低阶。
- 比拟次数，替换（或挪动）次数。
<2> 排序算法的稳定性
- 稳定性概念：如果待排序的序列中存在值相等的元素，通过排序之后，相等元素之间原有的先后顺序不变。
- 稳定性重要性：可针对对象的多种属性进行有优先级的排序。
- 举例：给电商交易系统中的“订单”排序，依照金额大小对订单数据排序，对于雷同金额的订单以下单工夫早晚排序。用稳固排序算法可简洁地解决。先依照下单工夫给订单排序，排序实现后用稳固排序算法依照订单金额从新排序。
<3> 排序算法的内存损耗
原地排序算法：特指空间复杂度是 O(1)的排序算法。
三、冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比拟，看是否满足大小关系要求，如果不满足就让它俩调换。稳定性：冒泡排序是稳固的排序算法。
空间复杂度：冒泡排序是原地排序算法。
工夫复杂度：
- 最好状况（满有序度）：O(n)。
- 最坏状况（满逆序度）：O(n^2)。
- 均匀状况：
“有序度”和“逆序度”：对于一个不齐全有序的数组，如 4，5，6，3，2，1，有序元素对为 3 个（4，5），（4，6），（5，6），有序度为 3，逆序度为 12；对于一个齐全有序的数组，如 1，2，3，4，5，6，有序度就是 n *(n-1)/2，也就是 15，称作满有序度；逆序度 = 满有序度 - 有序度；冒泡排序、插入排序替换（或挪动）次数 = 逆序度。
最好状况下初始有序度为 n (n-1)/2，最坏状况下初始有序度为 0，则均匀初始有序度为 n (n-1)/4，即替换次数为 n *(n-1)/4，因替换次数 < 比拟次数 < 最坏状况工夫复杂度，所以均匀工夫复杂度为 O(n^2)。
四、插入排序
插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的适合地位，直到未排序区间为空。空间复杂度：插入排序是原地排序算法。
工夫复杂度：
- 最好状况：O(n)。
- 最坏状况：O(n^2)。
- 均匀状况：O(n^2)（往数组中插入一个数的均匀工夫复杂度是 O(n)，一共反复 n 次）。
稳定性：插入排序是稳固的排序算法。
五、抉择排序
抉择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的开端，直到未排序区间为空。空间复杂度：抉择排序是原地排序算法。
工夫复杂度：（都是 O(n^2)）
- 最好状况：O(n^2)。
- 最坏状况：O(n^2)。
- 均匀状况：O(n^2)。
稳定性：抉择排序不是稳固的排序算法。
思考
抉择排序和插入排序的工夫复杂度雷同，都是 O(n^2)，在理论的软件开发中，为什么咱们更偏向于应用插入排序而不是冒泡排序算法呢？答：从代码实现上来看，冒泡排序的数据交换要比插入排序的数据挪动要简单，冒泡排序须要 3 个赋值操作，而插入排序只须要 1 个，所以在对雷同数组进行排序时，冒泡排序的运行工夫实践上要长于插入排序。