超大:排序算法之冒泡、插入和选择排序
前言:排序作为算法中最基础的一环，相信大部分程序员不会陌生。但是排序算法分类众多，从复杂度来看，O(n^2)的有冒泡、插入、选择排序等；O(nlogn)的有快速、合并排序等；O(n)的有桶、基数排序等。下面几章会分别介绍这些排序算法，希望大家在看的同时，也可以动手实操一下，加深理解。
今天来讲讲最经典的冒泡和插入排序，我们都知道他们的时间复杂度都为O(n^2)，那么在实际应用时会考虑使用哪个呢？你的考虑方向是什么呢？
带着这个问题，我们先来介绍如何分析“排序算法”。
执行效率
1.1 最好、最坏、平均时间复杂度
1.2 时间复杂度的系数
1.3 比较的次数和交换次数内存消耗
即指之前提到的空间复杂度，引入一个原地排序(特指空间复杂度为O(1)的排序)稳定性
待排序的序列中存在值相等的元素时，经过排序后相等的元素之间原有的先后顺序是否改变
为什么要考虑稳定性呢？
可解决下面这种场景。对交易系统中的“订单”进行排序。订单中有两个属性，下单时间和下单金额。希望根据下单金额大小对订单数据排序。金额相同的订单按照下单时间从早到晚排序。
如果按照常规思路，先按照金额对订单数据进行排序，然后再遍历对金额相同的小区间进行下单时间排序，实现起来会很复杂。
通过稳定排序算法，可以先对下单时间进行排序，再对下单金额进行排序，可以很方便的实现。
冒泡 VS 插入
冒泡排序
n个待排序的序列，经过n-1个循环每次经过(n-已经排完数-1)的交换，把较大数依次放到相应的位置，完成排序。
private static void sort(int[] a){
int length = a.length;
//外循环需要n-1次
for (int i = 0; i < length - 1; i++) {
//每次都比要少一个i的交换
for (int j = 0; j < length- i - 1; j++) {
if(a[j] > a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
优化点:若内循环已经没有交换，说明整个待排序列已经排好序。直接退出。
private static void sort(int[] a){
int length = a.length;
//外循环需要n-1次
for (int i = 0; i < length - 1; i++) {
boolean flag = false;
//每次都比要少一个i的交换
for (int j = 0; j < length- i - 1; j++) {
if(a[j] > a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
flag = true;
}
}
//没有交换的话说明已经排好序
if(!flag) break;
}
}
冒泡分析:
因为只涉及一个常量级的临时空间开辟，所以为原地排序。
因为交换时只在>时进行交换，所以是具有稳定性的。
时间复杂度，最好情况下只需要一次冒泡，复杂度为O(n)；最坏情况逆序下需要n次冒泡，复杂度为O(n^2)。平均时间复杂度可以分析交换次数。交换次数又可以通过有序度来分析。有序度定义如下:
有序元素对：a[i] <= a[j], 如果 i < j。
最好的情况下有序度为n*(n-1)/2，即不需要交换。最坏的情况下有序度为0，即需要n*(n-1)/2次交换。平均就是n*(n-1)/4，即为O(n^2)。
插入排序
通过遍历数组，找到数据应该插入的位置进行插入。
核心思想为:取未排序区间中的元素，在已排序区间中找到合适的位置进行插入，并保证已排序区间数据一直有序。
public static void sort(int[] a){
int length = a.length;
//轮到数组中下标为i的数进行插入
for (int i = 1; i < length; i++) {
int j = i-1;
int value = a[i];
//j下标前为已排序的序列 寻找插入位置
for (; j>=0; j--) {
if(a[j] > value){
a[j+1] = a[j];
}else {
break;
}
}
a[j+1] = value;
}
}
插入分析:
因为不涉及开辟临时空间，所以肯定为原地排序。
移动数组的条件为>，因此可以把后进行排序的数安排到已排序序列中相同数后边。
时间复杂度，最好的情况为只需要进行判断而不用进行交换操作，即O(n)。最坏为O(n^2)。
选择排序
跟插入排序类似，分为已排序区域和未排序区域。每次都从未排序区域中选择最小值和未排序区中最小index的值进行交换。直接贴代码：
public static void sort(int[] a){
int length = a.length;
//未排序的区域
for (int i = 0; i < length; i++) {
//设置未排序区域的最小值
int min = a[i];
//未排序区域的最小index
int index = i;
for (int j = i+1; j < length; j++) {
if(a[j] < min){
min = a[j];
index = j;
}
}
//交换
int temp = a[i];
a[i] = min;
a[index] = temp;
}
}
选择分析:
空间复杂度为O(1)，为原地排序
最好、最坏、平均空间复杂度都为O(n^2)
因为会有和已排序最小index进行交换，所以会破坏原有相等值的前后顺序，为不稳定排序