排序算法
1.什么叫排序？
排序前：3，1，6，9，8，9
排序后：1，3，5，6，8，9
排序无处不在
十大排序算法：
2 算法介绍
什么是排序算法的稳定性？
回答：如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法
举例：
排序前：5，1，3（a）, 4，7，3(b)
稳定的排序： 1，3(a)，3(b)，4，5，7
不稳定的排序: 1，3(b)，3(a)，4，5，7
在对自定义对象进行排序时，稳定性会影响最终的排序效果
什么是原地算法（In-place Algorithm）?
回答：不依赖额外的资源或者依赖少数的额外资源，仅依靠输出覆盖输入，空间复杂度为0（1）的可以认为是原地算法
ps.(代码实现用到的方法定义，本文统一以升序为例子）
cmp(index0,index1)
cmp方法传入二个数组索引比较两个索引所指元素的大小
如果index0索引的元素大于index1索引的元素则返回 一个大于0 的整数
反之则返回小于0的整数 ,相等返回0。
swp(index0,index1)
swp方法传入二个数组索引交换索引所指元素的位置
2.1冒泡排序
冒泡排序也叫起泡排序
-
执行流程
① 从头开始比较相邻每一对元素，如果第1个比第2个大，就交换它们的位置，执行完一轮后，最末尾那个元素就是最大的元素
② 忽略①中曾经找到的最大元素，重复执行步骤1，知道全部元素有序
代码实现：
for (int end = array.length - 1; end > 0 ; end --){
for (int begin = 1; begin <= end ; begin ++){
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1)
}
}
}
冒泡排序优化①
在冒泡排序的过程中会出现这么一种情况在某一轮的排序过程中根本就没有调用swap方法说明此时的数组已经是完全有序了但是按照之前的做法我们的程序还是要执行下去直到所有轮次结束，这样后面的代码都是在做无用功大大的浪费了性能，所以我们可以在检测到数组已经提前有序的情况下及时的结束方法提高效率。
代码实现：
for (int end = array.length - 1; end > 0 ; end --){
bool sorted = true;
for (int begin = 1; begin <= end ; begin ++){
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1)
sorted = false;
}
}
if (sorted) break
}
从代码中可以看出 如果swap 在一轮排序中始终没有调用，那么sorted变量则为true
发现sorted为true时，我们直接结束循环。在实际应用中很少会出现①中提前有序的情况，所以第一种优化的能用到的情况不会太大。
冒泡排序优化②
如果序列尾部已经局部有序，我们可以记录最后一次交换的位置，减少比较次数
什么意思？
举个例子：有无序列表 a = [2,1,8,9,7,10,11,12,13,14]
通过观察可以发现a的尾部从10元素开始后面都是有序的，如果通过我们之前的代码排序在交换了9 和 7 的位置之后 我们还是会去判断10之后的元素的大小关系但是它们已经是有序的了。所以后面我们几轮的排序都会做一些无用的判断。这个时候我们可以记录下我们最后一次交换元素的位置 7 的位置 此时 a = [1,2,8,7,9,10,11,12,13,14]
当我们下一轮排序时到7 的位置我们就直接结束排序因为后面的元素已经是有序的了。这样可以优化我们判断次数。
代码实现：
for (int end = array.length - 1; end > 0 ; end --){
int sortedIndex = 1;
for (int begin = 1; begin <= end ; begin ++){
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1)
sortedIndex = begin;
}
}
end = sortedIndex
}
- 设置 sortedIndex 的初始值为1可以完美的兼容整个序列提前有序的情况
- sortedIndex 的值会不断被begin的值覆盖 单一轮排序完成时 sortedIndex的值必然是最后一次交换元素的位置
2.2 选择排序
-
执行流程
① 遍历一边序列找出最大的那个元素,然后与末尾的元素交换位置
② 忽略①中找到的最大元素，重复执行步骤 ①
代码实现：
for (int end = array.length - 1; end > 0 ; end --){ int maxIndex = 0; for (int begin = 1; begin <= end ; begin ++){ if (cmp(max, begin ) <= 0) { max = begin; } } swap(max,end); } 选择排序的交换次数远远少于冒泡排序，平均性能优于冒泡排序
最好，最坏，平均时间复杂度:O(n2)
2.3 插入排序
- 执行流程
① 在执行过程中,插入排序会将序列分为2部分,头部是已经排好序的,尾部是待排序的
② 从头开始扫描每一个元素,每当扫描到一个元素，就将它插入到头部合适的位置,使得头部的数据依次保持有序
代码实现：
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
while (cur > 0 && amp(cur, cur -1) < 0) {
swap(cur, cur - 1);
cur--
}
}
插入排序的时间复杂度与逆序对的数量成正比关系
逆序对的数量越多，插入排序的时间复杂度越高
(ps.什么是逆序对? 举个例子：数组<2,3,8,6,1>的逆序对为: <2,1><3,1><8,1><8,6><6,1>,一共5个逆序对）最坏,平均时间复杂度:：O(n2)
最好时间复杂度: O(n)
空间复杂度:O(1)
属于稳定排序
插入排序优化1
- 思路将【交换】转为【挪移】
① 先将待插入的元素备份
②头部有序数据中比待插入元素大的，都朝尾部方向挪动一个位置
③将待插入元素放入最终合适的位置
代码实现：
for (int begin = 1 ; begin < array.length; begin++){
int cur = begin;
T value = array[cur];//备份元素
while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
array[cur] = array[cur - 1];
cur --;
}
array[cur] = v;
}
插入排序优化2
- 思路在优化1的基础上 优化确定位置的过程优化1是一个一个比较来确定，所以可以通过二分法直接求出要插入的位置。从而减少比较次数
代码实现：
for (int i = 1; i < array.length; i ++ ){
//找出插入位置
int index = -1;
int begin = 0;
int end = I;
while (begin < end) {
int mid = (begin + end) >> 1;
if (cmp(i ,mid) < 0 ){
end = mid;
}else {
begin = mid + 1;
}
}
index = begin;
//备份元素
T value = array[I];
for (int j = i; j > index; j --) {
array[j] = array[j - 1];
}
array[index] = value;
}
2.4 归并排序
-
执行流程
① 不断地将当前序列平均分割成2个子序列，直到不能分割（序列中只剩一个元素）
② 不断地将2个子序列合并成一个有序序列直到最终只剩下1个有序序列
代码实现
// 准备一段临时的数组空间,在合并操作中使用
leftArray = (T[ ]) new Object[array.lengtn >> 1];
sort(0,array.length);
private void sort(int begin, int end) {
// 至少需要有2个元素
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sort(begin,mid);
sort(mid,end);
merge(begin,mid,end);
}
private void merge(int begin, int mid ,int end) {
int li = 0;
int le = mid - begin; // 左边数组（基于leftArray）
int ri = mid;
int re = end;//右边数组(基于array)
int ai = begin;//array 的索引
for (int I = li; i < le; i ++){//拷贝左边数组到leftArray
leftArray[I] = array[begin + I];
}
while (li < le) {
if (ri < re && amp(array[ri]),leftArray[li] < 0) {
array[ai ++] = array[ri ++];// 拷贝右边数组到array
} else {
array[ai ++] = leftArray[li ++];//拷贝左边数组到array
}
}//cmp位置改为 <= 会失去稳定性
}
归并排序 - 复杂度分析
- 归并排序花费的时间
T(n) = 2 * T(n/2) + 0(n)
T(1) = O(1)
T(n)/n = T(n/2)/(n/2) + O(1)
令S(n) = T(n)/n
S(1) = O(1)
S(n) = S(n/2) + O(1) = S(n/4) + 0(2) = S(n/8) + 0(3) = S(n/2k) + O(k) = S(1) + O(logn) = O(logn)
T(n) = n* S(n) = 0(nlogn)
- 由于归并排序总是平均分割子序列,所以最好,最坏，平均时间复杂度都是O(nlogn)
常见的递推式与复杂度
2.5 快速排序
- 执行流程
① 从序列中选择一个轴点元素,一般每次选择0位置的元素为轴点元素
② 利用轴点将序列分割成2个子序列,将小于轴点元素的元素放在轴点前面(左侧)
将大于轴点元素的元素放在轴点的后面(右侧)
③ 对子序列进行①②操作知道不能再分割(子序列中只剩下1个元素)
代码实现
private void sort(int begin, int end) {
//至少要用2个元素
if (end - begin < 2) return;
int middle = privotIndex(begin,end);
sort(begin,middle);
sort(middle + 1, end);
}
private int privotIndex(int begin, int end) {
T privot = array[begin];
end --;//end指向最后一个元素
while (begin < end) {
while (begin < end) {
if (cmp(privot, array[end]) < 0) {
end --;
} else {
array[begin ++] = array[end];
break;
}
}
while (begin < end) {
if (cmp(privot, array[begin]) > 0) {
begin ++;
} else {
array[end --] = array[begin];
break;
}
}
}
array[begin] = pivot;
return begin;
}
