算法之旅：理解透彻冒泡算法及它的几个优化版本
什么是冒泡排序？
冒泡排序的英文Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。
而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2） 。
增强版1
对于后面已经有序的部分，不需要在进行比较了。增加isSorted标记，默认true，如果本轮存在交换，就变为false，说明下一轮可能还有排序。否则break跳出循环
这一版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
增强版2
提前预知已排好序的边界，减少排序比较次数。最后交换元素的下标记住。
这一版代码中，sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的。
鸡尾酒排序
告别冒泡排序的单项比较移动，鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环，一个向左，一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含两个小循环，第一个循环从左向右比较并交换元素，第二个循环从右向左比较并交换元素。
鸡尾酒排序增强版
代码中使用了左右两个边界值，rightSortBorder 代表右边界，leftSortBorder代表左边界。
在比较和交换元素时，奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置，偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
地精排序
它也像冒泡排序一样，相邻元素之间两两进行比较，如果这两个元素逆序，则交换。与冒泡排序不同的是，它如果遇到交换操作时，变为向前冒泡，直至不发生交换操作位置。相当于做了一个插入操作，将比较小的数插入到前面的有序序列中合适的位置。所以，地精排序可以说是冒泡排序和直接插入排序的综合。
参考文档：
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
冒泡排序的英文Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。
而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2） 。
增强版1
对于后面已经有序的部分，不需要在进行比较了。增加isSorted标记，默认true，如果本轮存在交换，就变为false，说明下一轮可能还有排序。否则break跳出循环
这一版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
增强版2
提前预知已排好序的边界，减少排序比较次数。最后交换元素的下标记住。
这一版代码中，sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的。
鸡尾酒排序
告别冒泡排序的单项比较移动，鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环，一个向左，一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合，大循环内包含两个小循环，第一个循环从左向右比较并交换元素，第二个循环从右向左比较并交换元素。
鸡尾酒排序增强版
代码中使用了左右两个边界值，rightSortBorder 代表右边界，leftSortBorder代表左边界。
在比较和交换元素时，奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置，偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
地精排序
它也像冒泡排序一样，相邻元素之间两两进行比较，如果这两个元素逆序，则交换。与冒泡排序不同的是，它如果遇到交换操作时，变为向前冒泡，直至不发生交换操作位置。相当于做了一个插入操作，将比较小的数插入到前面的有序序列中合适的位置。所以，地精排序可以说是冒泡排序和直接插入排序的综合。
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;
if(array == NULL) {
return FALSE;
}
while(i < size) {
//如果i=0或者i-1与i正序时，i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时，i--
Swap(array + i-1, array + i);
i--;
}
}
return TRUE;
}
参考文档：
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
