时间复杂度为O(n2)的排序（JAVA）
时间复杂度为O(n2)的排序
选择排序
思路
选择排序作为不站在巨人肩膀上可以想到的一种排序算法，其思路相对简单而纯粹。
比如现在要对一个数组做升序排序，那么，找到里边的最小值，放到第一位；找到第二小值，放到第二位；…找到里边的最大值，放到最后一位
而具体到数组中：
从index=0开始向后遍历找最小值，找到最小值后，记录下它的索引值，比如是index=m，然后将index=0和index=m的元素做交换，最小值搞定，可以确定index=0就是最小值了
从index=1开始向后遍历找第二小值，找到第二小值后，记录下它的索引值，比如是index=n，然后将index=1和index=n的元素做交换，第二小值搞定，可以确定index=1就是第二小值了
…
依次向后操作，最终得到的数组就是一个升序排序的数组了
当然，也可以先找到最大值，将其放到index=length-1的位置，继续从后往前来
写循环代码的过程
假如以最开始找最小值为例，考虑某个中间状态循环体内要做的操作有哪些？
设定数组长度为length，已有i次处理，也就是说现在从index=0到index=i-1都是有序数列了，接下来的任务就是找出剩余length-i个元素中的最小值，记录下它的索引，并与index=i的元素做交换，下边是伪代码
int i = 当前要处理的索引值;
int length = array.length;
int minValue = Integer.MAX_VALUE;
int minIndex = -1;
for(int j = i; j < length; j++) {
if(minValue <= array[j]) {
// 不做任何操作
} else {
// 记录下最小值的索引和值本身
minValue = array[j];
minIndex = j;
}
}
// 将最小值和m交换
if(i == minIndex) {
// 如果比较一圈发现当前位置放置的就是最小值， 不处理
} else {
// 交换
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
// i位置已经确定好了， 接着处理i+1
i++;
接着考虑循环部分
循环从index=0开始，终止位置是index=length-1（其实到index=length-2就OK了）
下边是伪代码
for(i = 0; i < length; i++) {
// 把上边部分拿进来， 注意，这里定义了i， 也在for循环中做了i的自增， 所以上边定义i和i自增的代码需要去掉了
}
最终代码
public void selectionSortFromHead(int[] array, int length) {
for (int i = 0; i < length; i++) {
int minIndex = -1;
int min = Integer.MAX_VALUE;
for (int j = i; j < length; j++) {
if (min <= array[j]) {
continue;
}
min = array[j];
minIndex = j;
}
// 交换
if (minIndex == i) {
// 当前位置就是最小值
} else {
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
如果先找到最大值放最后呢，代码也放这儿了
public void selectionSortFromTail(int[] array, int length) {
for (int i = length - 1; i >= 0; i--) {
int maxIndex = -1;
int max = Integer.MIN_VALUE;
for (int j = 0; j <= i; j++) {
if (max >= array[j]) {
continue;
}
max = array[j];
maxIndex = j;
}
// 交换
if (maxIndex == i) {
// 当前位置就是最大值
} else {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
}
}
冒泡排序
思路
从冒泡排序开始，都是要站在巨人肩膀上，偷窥下巨人们留下来的思路了
冒泡排序的主题是交换元素，相邻元素比较换位置，每次达到的效果和选择排序类似。
选择排序的第一轮操作找到了最大值，并将其放置到尾端，冒泡排序第一轮也要想办法将最大值放置到尾端，不过方式不是先找后换。言语苍白，上图解释。假设有一个数组为[1, 5, 7, 2, 8, 4]，第一轮的操作是这样的
该轮结束后，最大值8被换到了index=length-1的位置
可以预见，经过第二轮7会被换到index=length-2的位置
第三轮是5被换到index=length-3
…
写循环代码的过程
像分析选择排序的循环代码一样，假设某个中间状态是经历了x次冒泡排序后的状态，数组中还有前i+1个元素处于无序状态，容易得知x=length-i-1
数组的后length-i-1个元素已经是升序状态，而且有前i+1个元素一定不大于后length-i-1个元素，当前要进行第length-i轮冒泡，目的是经过一系列比较交换后将index=i设置为前i+1个元素中的最大值。而循环体中便是一系列的比较交换操作，操作从index=0开始，一直到index=i-1结束（可参考上图中，6个元素在第一轮中比较操作是从index=0到index=5的）
下面是伪代码
int i = 本轮冒泡要确定的索引;
for(int j = 0; j < i; j++) {
if(array[j] <= array[j+1]) {
// 不做处理
} else {
// 交换两元素
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
// 因为是从后（大）往前（小）操作，需要i自减
i--;
接着考虑循环部分i是从数组的尾index=length-1开始，确定到index=1就可以了（后边length-1个都确定了，那么index=0自然也就确定了）
下边是伪代码
for(int i = length-1; i > 0; i--) {
// 把上边部分拿进来， 注意，这里定义了i，也在for循环中做了i的自减， 所以上边定义i和i自减的代码需要去掉了
}
最终代码
public void bubbleSortFromTail(int[] array, int length) {
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] <= array[j + 1]) {
// 保持
} else {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
如果冒泡从后往前来，最先确定的是最小值，代码如下：
public void bubbleSortedFromHead(int[] array, int length) {
for (int i = 0; i < length - 1; i++) {
for (int j = length - 1; j > i; j--) {
if (array[j - 1] <= array[j]) {
// 保持
} else {
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
不过看网上关于冒泡排序的写法更多的不是这种，我按这种思路写的时候也感觉有些差异。那么换种思路来写冒泡吧
另一种思路分析冒泡的循环体
假设现在是第i+1轮冒泡，这意味着已经确定了后i位，前边还有length-i个元素处于无序状态，接下来要从index=0开始，确定到index=length-i-2
for(int j = 0; j < length-i-1; j++) {
if(array[j] <= array[j+1]) {
// 保持
} else {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
外部循环关于i的理解是，一共需要冒泡length-1次，从第一轮到第length-1轮（不需要第length轮，因为那时候就剩下index=0元素无序，很显然，不用处理它了）。也就是1<=i+1<=length-1，即0<=i<length-1
for(int i = 0; i<length-1; i++){
// 上述代码
}
最终代码
public void bubbleSorted(int[] array, int length) {
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (array[j] <= array[j + 1]) {
// 保持
} else {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
插入排序
思路
玩儿扑克牌，一张一张的揭起来，捋到手里，想象一下这个过程。
揭到第一张红桃8，直接放在手里
揭到第二张黑桃9，瞄了一眼，和红桃8比，当前更大，插入到了红桃8后边
揭到第三张黑桃5，瞄了一眼，比黑桃9小，正准备要放到黑桃9的前边，又瞄了下红桃8，比红桃8小，前边没牌了，插入到了红桃8的前边
揭到第四张方块6，瞄了一眼，比黑桃9小，又瞄一眼，比红桃8小，又瞄一眼，比黑桃5大，于是插入到了黑桃5和红桃8之间
…
假如就这4张牌，相当于一个数组
Integer[] cards = {null, null, null, null};
// 揭到第一张8到手里，相当于8已经有序了
cards = {8, null, null, null};
// 揭到第二张9到手里，和8比了下，保持原位置不变
cards = {8, 9, null, null};
// 揭到第三张5到手里，和9比更小，于是9要挪位置给5
cards = {8, null, 9, null};
// 接着和8比也更小，于是8要挪地方给5
cards = {null, 8, 9, null};
// 没得比了，将5放入这个位置
cards = {5, 8, 9, null};
// 揭到第四张6到手里，和9比更小，于是9要挪位置给6
cards = {5, 8, null, 9};
// 接着和8比更小，于是8要挪位置给6
cards = {5, null, 8, 9};
// 接着和5比更大，将6放在这个位置
cards = {5, 6, 8, 9};
// 后边没牌了，插入排序结束
写循环代码的过程
经过一轮插入排序后，从index=0到index=1有序
经过二轮插入排序后，从index=0到index=2有序
经过i-1轮插入排序后，从index=0到index=i-1有序
现在执行第i轮插入排序，将index=i的元素从index=i-1开始逐个向前比较并最终确定位置，执行过程是：
取出index=i的值，
和index=i-1比较，如果更小，将index=i-1放入index=i
接着和index=i-2比较，如果更小，将index=i-2放入index=i-1
接着和index=i-3比较，如果更大或者相等，将取出的值放入index=i-2，退出该轮
否则一直执行到和index=0比较结束，把取出的值放入index=0
下边是伪代码
int temp = array[i];
for(int j = i-1; j >= 0; j--) {
if(temp < array[j]) {
array[j+1] = array[j];
} else {
// 将值存入
array[j+1] = temp;
break;
}
if(j == 0) {
array[0] = temp;
}
}
经过i-1轮插入排序，从index=0到index=i-1有序，
那么经过length-1轮插入排序，从index=0到index=length-1有序（即全数组）
外部循环就有了，下边是伪代码
for(int i = 1; i < length; i++) {
// 上边代码
}
最终代码
public void insertionSortFromHead(int[] array, int length) {
for (int i = 1; i < length; i++) {
int temp = array[i];
for (int j = i - 1; j >= 0; j--) {
if (temp < array[j]) {
array[j + 1] = array[j];
} else {
// 将值存入
array[j + 1] = temp;
break;
}
if (j == 0) {
array[0] = temp;
}
}
}
}
学习了下网上的一个写法，看着更舒服些
public void insertionSortFromHead(int[] array, int length) {
for (int i = 1; i < length; i++) {
int temp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if (temp < array[j]) {
array[j + 1] = array[j];
} else {
break;
}
}
// 将值存入
array[j + 1] = temp;
}
}
上边代码当执行到内层for循环的else分支时，j的值被保留了下来，执行array[j + 1] = temp即可；当执行的都在内层for循环的if分支时，最终跳出内层for循环的原因是j = -1，则执行array[j + 1] = temp相当于执行array[0] = temp；有没有觉得很巧。想不出来，要么就背下来这种写法；要么就上边那种会稍微丑一点。
假设一位惯用左手的揭牌，而且习惯把大的往后放（看着仍然是升序）
写循环代码的过程
经过一次插入排序，index=length-2到index=length-1有序
经过二次插入排序，index=length-3到index=length-1有序
经过i-1次插入排序，index=length-i到index=length-1有序
经过i次插入排序，index=length-i-1到index=length-1有序
经过length-1次插入排序，index=0到index=length-1有序（全数组有序）
最后一次为什么是length-1，已知length-i-1=0求i就得到了
第i次插入排序要做的操作是：
将index=length-i-1的值暂存，然后从index=length-i到index=length-1逐个比较确定
伪代码如下
int temp = array[length-i-1];
for(int j = length-i; j < length; j++) {
if(temp > array[j]) {
array[j-1] = array[j];
} else {
array[j-1] = temp;
break;
}
if(j == length-1) {
array[length-1] = temp;
}
}
i这个时候表示的依然是次数，从第1次到第length-1次
for(int i = 1; i < length; i++) {
// 上边代码
}
最终代码
public void insertionSortFromTail(int[] array, int length) {
for (int i = 1; i < length; i++) {
int temp = array[length - i - 1];
for (int j = length - i; j < length; j++) {
if (temp > array[j]) {
array[j - 1] = array[j];
} else {
// 将值存入
array[j - 1] = temp;
break;
}
if (j == length - 1) {
array[length - 1] = temp;
}
}
}
}
这里也可以用简洁些的写法
public void insertionSortFromTail(int[] array, int length) {
for (int i = 1; i < length; i++) {
int temp = array[length - i - 1];
int j = length - i;
for (; j < length; j++) {
if (temp > array[j]) {
array[j - 1] = array[j];
} else {
break;
}
}
// 将值存入
array[j - 1] = temp;
}
}