01-冒泡排序
认识排序
什么叫排序？例如有下面的一串无序数字
- 排序前：3,1,6,9,2,5,8,4,7
- 排序后：1,2,3,4,5,6,7,8,9（升序）或者9,8,7,6,5,4,3,2,1（降序）
其实，排序的应用无处不在，例如，汽车销售根据销量排序
再例如，游戏充值，根据金额进行排序
认识了排序以后，接下来交接一下经典的10大排序算法
以上表格中的结论是基于数组进行排序的一般性结论
其中：
冒泡，选择，插入，归并，快速，希尔，堆排序属于比较排序（Comparison Sorting）
冒泡排序
接下来，先介绍一个冒泡排序，在这里所有的排序，统一以升序为例子。其冒泡排序的流程为
- 从头开始比较每一对相邻元素，如果第一个比第二个大，就交换它们的位置。
- 执行完一轮后，最末尾的哪个元素就是最大元素
- 忽略1中曾经找到的最大元素，重复执行步骤1，直到全部元素有序
所以，通过上面的步骤，就可以得到以下的代码
int[] array = {10,9,19,28,37,56,34};
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
冒泡排序-优化1
通过上面这种代码，虽然实现了对元素的排序，但是还是有优化的地方，比如在某个时间节点，所有元素已经完全有序[下图]，则可以提前终止冒泡排序。通过上面这种实现方式，是不能达到这种要求的。
由于在排序过程中，是通过一个元素一个元素扫描，来判断是否交换的，所以在第一轮扫描时，就可以知道该组元素是否已经有序。所以只要 if (array[begin] < array[begin - 1])成立，这说明当前组元素不完全有序，需要交换，否则就是所有元素都不用交换，则表示已经完全有序。所以可以通过下面方式进行优化
int[] array = {10,9,19,28,37,56,34};
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true;
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sorted = false;
}
}
if (sorted == true) {
break;
}
}
通过这种优化，就可以提高效率。
但是这种优化，真的可以提高效率吗？为了测试真的可以提升效率，可以进行下面的测试。
- 通过工具类，生成两组相同的数据
- 计算两种不同方式，处理相同数据所消耗的时间
所以在这里随机生成了10000个随机数，然后通过两个不同的函数来计算最终所消耗的时间，函数如下
public static void bubbleSort1(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
}
public static void bubbleSort2(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true;
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sorted = false;
}
}
if (sorted == true) {
break;
}
}
得到的结果如下
通过测试时间，得到的结果，发现没有优化的代码，所消耗的时间更短。是不是觉得很奇怪，为什么优化后，反而更慢呢？那想一个问题，bubbleSort2之所以成为优化，在什么情况下，才能被优化。应该是经过冒泡排序后，数组中的数据提前排好序的情况下，可以被优化。假设冒泡排序的数据，数据量很大，而且有很随机的话，很难达到提前有序的情况。由于bubbleSort2相对于bubbleSort1多做了一些事情，所以所消耗的时间更长。
但是如果现在的数据是升序的，同样为10000个元素，最终得到的结果为
通过结果可以发现，bubbleSort1无论数据是否提前有序，都要消耗很长的时间。但是bubbleSort2却可以大大的提高效率。不过需要注意的是，这种优化在某种前提下有效。
冒泡排序-优化2
通过上面这种优化，提前有序的概念很低，那有没有更好的优化方案呢？是有的，可以这样做：
如果序列尾部已经局部有序，可以记录最后一次交换的位置，较少比较次数。例如现在得到的数据是这样的
如果按照普通的冒泡排序算法，则是依次扫描所有的元素并进行比较。并不会理会后面数据是否有规律。但是上面这组数据，是有优化空间的，通过观察发现，使用冒泡排序的话， 最后面的几个元素的顺序是不会发生改变的，因为这些元素都已经有序，并且比前面的元素都大。也就意味着，交换操作，只需要堆前面未排序的元素进行就行了，没必要对后面已经有序的元素再次比较。所以，如果可以提前发现局部排序的元素，是可以提高效率的。所以可以这样实现
public static void bubbleSort3(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
int sortedIndex = 1;//该值在数组完全女友许的时候有用
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sortedIndex = begin;
}
}
end = sortedIndex;
}
}
通过这种方式优化后，现在来比较三种排序算法最终的结果。同样假设数据样本为10000个升序数据，最终得到的比较结果为
可以看到，最后两种算法的效率是非常高的。
接下来，对数据进行优化，现在利用工具生成10000个数据，其中8000个数据已经排好序。最终运行程序，得到的结果为
可以看到，通过这种局部排序的数据，bubbleSort3是明显优于bubbleSort1和bubbleSort2的。
通过这种优化
- 最坏，平均时间复杂度为：O(n^2)
- 最好时间复杂度：O(n)
- 空间复杂度为O(1)
排序算法的稳定性（Stability）
如果相等的两个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法。例如，下列数据中，有两个值相等的元素
排序前:5,1,3(a),4,7,3(b)
稳定的排序:1,3(a),3(b),4,5,7
不稳定的排序：1,3(b),3(a),4,5,7
为什么要这样认为呢？因为在实际开发中，存在对自定义对象进行排序的情况，稳定性会影响最终的排序效果。
所以根据这个结论，可以知道冒泡排序是属于稳定的排序算法。但是，稍有不慎，稳定的排序算法也能被写成不稳定的排序算法，比如下面的冒泡排序代码就是不稳定的
public static void bubbleSort4(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end ; begin++) {
if (array[begin] <= array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
}
所以在写排序算法时，需要特别的注意。
原地算法（In-place Algorithm）
什么叫原地算法？
- 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入。
解读：
- 不依赖额外的资源或者依赖少数的额外资源就意味着空间复杂度低；
- 仅依靠输出来覆盖输入表示可以利用传进来的参数直接进行操作，不会利用其它资源
所以，空间复杂度为O(1)的算法，都可以认为是原地算法。
非原地算法，成为Not-in-place或者Out-of-place
前面的冒泡排序，属于In-place
完！
