排序，是每一本数据结构的书都绕不开的重要部分。
排序的算法也是琳琅满目、五花八门。
每一个算法的背后都是智慧的结晶，思想精华的沉淀。
个人觉得排序算法没有绝对的孰优孰劣，用对了场景，就是最有的排序算法。
当然，撇开这些业务场景，排序算法本身有一些自己的衡量指标，比如我们经常提到的复杂度分析。
我们如何分析一个算法？
排序算法的执行效率
1、最好、最坏和平均情况的时间复杂度
2、时间复杂度的系数、常数和低阶
一般来说，在数据规模n很大的时候，可以忽略这些，但是如果我们需要排序的数据规模在几百、几千，那么这些指标就变的更加重要。
3、比较的次数和移动的次数
排序的过程涉及数据的比较和交换（移动）
排序算法的内存消耗
除了时间复杂度，我们还有空间复杂度，用来衡量内存消耗。这里我们引入原地排序的概念。原地排序即特指空间复杂度为O(1)的排序算法。
排序算法的稳定性
什么是稳定性，这比较抽象。
举个例子，现在有一组集合1，3，5，3，7
按照从小打到的顺序进行排序，结果应该是1，3，3，5，7
稳定指的是原集合的第二个3仍然在第四个3前面。不稳定则情况相反。
冒泡排序
原理
相邻元素两两比较，如果满足大小关系就保持不动，如果不满足，则两两交换位置，以此类推，直到集合有序为止。
之所以叫冒泡排序，因为其过程就犹如水中的气泡，泡泡越大的就在上面，越小的就在下面。
举例
现在给定一个集合4，5，6，3，2，1
第一次冒泡过程如下所示
20190113-1-冒泡排序.png
可以看出在这趟冒泡中，最大的泡泡6已经到达最高的位置，要让集合中所有元素都有序，还要继续冒泡，如下图：
image.png
代码
package com.jackie.algo.geek.time.chapter11_sort;
/**
* @Author: Jackie
* @date 2019/1/12
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{100,82,74,62,54,147};
bubbleSort(arr);
bubbleSort2(arr);
}
/**
* 外层i的循环代表比较的趟数，内层j的循环代表的元素位置
* a[0],a[1],a[2],a[3],a[4],a[5]
* 第一趟走完，最大的元素冒泡到最后a[5]的位置，需要比较的位置即为：
* a[0],a[1],a[2],a[3],a[4]
* 所以可以看到j的终止条件是动态变化的，与i的位置相关，趟数每增加一次，终止的位置就往前挪一个，因为每次都能固定一个元素
*
* 注意这里的边界条件，是<还是<=
* 第一层是小于，因为是从0开始，对于上面的例子来说，是比较length-1=6-1=5趟，因为总共6个元素，只要5趟就能比较完成
* 好比有两个元素，只要一趟就能比较完成
* 第二层是同样的道理，假设在i=0时，length-i-1=6-0-1=5，
* 但是这里<，所以只会到j=4，乍一看你会觉得之比较到了a[j]=a[4]，最后a[5]是不是就丢了
* 其实不是，仔细看下面的比较条件就会发现有a[j+1]即a[5]
* 所以，综上内层和外层都是从0开始，且都是<而不是<=
*/
public static void bubbleSort(int[] arr) {
int length = arr.length;
if (length <= 0) {
return;
}
int temp;
for (int i = 0; i < length - 1; i++) {
boolean flag = false;
for (int j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag) {
System.out.println("total loop: " + (i+1) + " times, stop at index:" + i);
break;
}
}
for (int i = 0; i < length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
/**
* 和上面的不同之处在于，上面的是保证数组从后往前有序，这里的是保证从前往后的有序
* 上面的做法如下所示，每次要遍历的元素如下
* a[0],a[1],a[2],a[3],a[4],a[5]
* a[0],a[1],a[2],a[3],a[4] (这里不再遍历a[5]的位置，因为a[5]在第一轮遍历已是最大，不需要参与遍历，下面遍历同理)
* a[0],a[1],a[2],a[3]
* a[0],a[1],a[2]
* a[0],a[1]
* a[0]
*
* 下面的做法如下所示，每次要遍历的元素如下
* a[0],a[1],a[2],a[3],a[4],a[5]
* a[1],a[2],a[3],a[4],a[5] (这里不再遍历a[0]的位置，因为a[0]在第一轮遍历已是最小，不需要参与遍历，下面遍历同理)
* a[2],a[3],a[4],a[5]
* a[3],a[4],a[5]
* a[4],a[5]
* a[5]
*/
public static void bubbleSort2(int[] arr) {
int length = arr.length;
if (length <= 0) {
return;
}
int temp;
for (int i = 0; i < length - 1; i++) {
boolean flag = false;
for (int j = length - 1; j > i; j--) {
if (arr[j] < arr[j-1]) {
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
if (!flag) {
System.out.println("total loop: " + (length - i - 1) + " times, stop at index:" + i);
break;
}
}
for (int i = 0; i < length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
写这类算法对于边界判定、起始条件和结束条件要非常谨慎，比如是用<还是用<=；是从0开始还是从1开始；是到length结束还是到length-1结束。
看似惺忪平常，有时候弄错一个符号就无法得到正确的排序结果。
冒泡排序的这些注意事项已经写在代码的注释中，参见如上代码。
同时，代码已经上传至Github
各项指标
1、是否是原地排序
是，因为冒泡排序只涉及两两元素交换，空间复杂度为O(1)
2、是否是稳定排序
是，对于元素相等的情况，不会交换顺序
3、时间复杂度
平均时间复杂度是O(n2)， 这里是n的平方
插入排序
原理
对于给定集合，从左至右，依次保证当前元素的左边集合有序。然后依次顺延当前位置，直至遍历完所有集合元素，保证整个集合有序。
有点抽象，没有关系，看举例。
举例
借用文章https://www.cnblogs.com/bjh1117/p/8335628.html中的例子说明插入排序的过程。
待比较数据：7, 6, 9, 8, 5,1
第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,_,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成_,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1
第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1
第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,_,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,_,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1
第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。
第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。
代码
package com.jackie.algo.geek.time.chapter11_sort;
/**
* @Author: Jackie
* @date 2019/1/13
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[]{100,82,74,62,54,147};
insertSort(arr);
}
/**
* 借用https://www.cnblogs.com/bjh1117/p/8335628.html文中的举例，我们可以看到一个完整的插入排序的过程
* 通过这个过程，我们可以更好的理解插入排序的思想
* 待比较数据：7, 6, 9, 8, 5,1
*
* 第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,_,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成_,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1
*
* 第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1
*
* 第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,_,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,_,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1
*
* 第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。
*
* 第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。
*
* 所以插入排序是保证一个元素的左边所有元素都是有序的，然后逐渐右移，直到遍历完所有的元素来保证整个数据是有序的
* 下面i从1开始，是表示以a[1]作为哨兵，第一次比较是a[0]和其比较，这里的j的其实位置都是小于i一个位移，即j=i-1
* 然后依次从右向左挨个比较，如果发现哨兵值小于左侧有序集合，则一直位移，以此保证始终留有一个位置用于插入待排序的值
* 一旦发现哨兵值如果大于等于（保证稳定性，即不会跑到等于某个值的左侧）左侧集合中的某个值，
* 则跳出内层循环，仔细想想左侧集合是有序的就明白了
* 至于最后为什么是a[j+1]=value，直觉上更应该是a[j]=value，但是记得，在跳出内层循环的时候进行了一次j--操作，
* 所以需要把这个操作补偿进来，变成了j+1
*/
public static void insertSort(int arr[]) {
int length = arr.length;
if (length <= 0) {
return;
}
for (int i = 1; i < length; i++) {
int value = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > value) {
arr[j+1] = arr[j]; // 位移
} else {
break;
}
}
arr[j+1] = value;
}
for (int i = 0; i < length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
同冒泡排序，有关边界判定、起始条件和结束条件也都写在注释中，不再赘述。
各项指标
1、是否是原地排序
是，同冒泡排序，空间复杂度为O(1)
2、是否是稳定排序
是，对于元素相等的情况，不会交换顺序
3、时间复杂度
平均时间复杂度是O(n2)， 这里是n的平方
选择排序
原理
选择排序思想和插入排序思想比较接近。每次排序从未排序的集合中找到最小的元素放进有序集合，通过这样的遍历排序保证整个集合有序。
举例
image.png
代码
package com.jackie.algo.geek.time.chapter11_sort;
/**
* @Author: Jackie
* @date 2019/1/13
*/
public class SelectionSort {
public static void main(String[] args) {
int[] arr = new int[]{100,82,74,62,54,147};
selectionSort(arr);
}
public static void selectionSort(int[] arr) {
int length = arr.length;
if (length <= 1) return;
for (int i = 0; i < length - 1; ++i) {
// 查找最小值
int minIndex = i;
for (int j = i + 1; j < length; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
for (int i = 0; i < length; i++) {
System.out.print(arr[i] + " ");
}
}
}
各项指标
1、是否是原地排序
是，同冒泡排序，空间复杂度为O(1)
2、是否是稳定排序
否，通过元素的交换可能改变原来的稳定结构，比如5，8，5，2，9，第一次排序后，5和2交换，则第一个5就跑到第二个5后面了，破坏了稳定结构。
3、时间复杂度
平均时间复杂度是O(n2)， 这里是n的平方，且最好最坏都是O(n2)。
声明：
文中图片来自极客时间王争老师专题《数据结构与算法之美》
网友评论