常见排序算法(1)--冒泡排序
前言：相信很多小伙伴在学习排序算法的时候，都遇到过一个问题，就是好像理解了某算法的思想，但是手写的时候，总是不能写对，主要在边界问题上，不知道写j还是j-1，写<length还是<=length。
目标：希望经常此专题的共同学习，每个小伙伴都能轻松的理解排序算法并且完全写对。
先看最简单的入门排序算法：冒泡排序吧。
为了后面可以方便的测试，先把简单的辅助函数写好。
#import <Foundation/Foundation.h>
// 打印数组的函数
void printArr(int *arr, int length)
{
for (int i = 0; i < length; i++)
{
printf("%d,",arr[i]);
}
printf("\n");
}
// 交互数组的元素
void swap(int *arr,int i,int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
1. 很像冒泡排序但是不是真正的冒泡排序
void BubbleSort0(int *arr,int length)
{
for (int i = 0; i < length-1; i++)
{
for (int j = i+1; j < length; j++)
{
if (arr[i] > arr[j]) // 采用升序排序
{
swap(arr, i, j);
}
}
}
}
光看代码可能不好理解，所以先看个简单的数组。int arr[] = { 3, 4, 2, 1};c语言的数组第一个元素下标为0，最后一个元素下标为length-1。第一次循环的时候，i从0开始，j从i+1开始，j的左边界很好理解，右边界为啥是<length呢？我们把arr[0]取出来放在那里，然后分别与arr[1]、arr[2]...到最后的arr[length-1]比较，如果遇到比arr[0]小的元素，就把它跟arr[0]交换。这样当i=0走完后，arr[0]就会成为最小的元素。然后i依次递增下去，排序就完成了，现在看看i的右边界为啥写<length-1而不写<length，其实外循环写<length也不会有错误，只是没有必要，因为当arr[length-2]排序完成后，剩余的最后一个元素arr[length-1]肯定就是最大的了。相信看完这段略显啰嗦的解释，大家应该都能一字不差的写出此"非正宗冒泡排序"了。
2. 正宗的冒泡排序
void BubbleSort(int *arr,int length)
{
for (int i = 0; i < length-1; i++)
{
for (int j = length - 2; j >= i; j--)
{
if (arr[j] > arr[j+1])
{
swap(arr, j, j+1);
}
}
}
}
为啥说这个是正宗的而前面却是似是而非的冒泡排序呢？因为冒泡排序的定义是两两相邻比较。我们还是拿最简单的例子来看，int arr[] = { 3, 4, 2, 1}；当i=0时，j=2，其实就是拿数组的最后一个元素与倒数第二个元素比较，把小的交换到前面。然后j依次递减，到最后比较的就是arr[i]与arr[i+1]，所以j的左边界是i，右边界是length-2。i=0的内循环走完后，其实arr[0]就是最小的元素，i依次递增，arr[i]就是依次的最小值。i的右边界的问题上一段有解释，不重复了。很多网上的冒泡排序的内循环的j是从0开始的，这个其实也是对的，大家任选一种就好了(不过j从后往前，造成的效果是小的元素依次上浮，个人感觉比较符合冒泡排序的意思。)。
tip：2其实效率跟1一样。方法1外循环执行完一次，仅仅做到了把arr[i]变为最小值，但是方法2在外循环执行完一次的过程中，除了把最小值带到arr[i]之外，还做了把数组中较小的元素慢慢交换到数组前半部的事情，所以数组会慢慢变的有序。2和1的比较次数和交换次数是一样的，不同的是2的数组在慢慢变的有序，这就是可以继续优化为3的基础。
3. 冒泡排序优化版
void BubbleSort2(int *arr,int length)
{
int status = 1; // 初始值为1
for (int i = 0; i < length-1 && status; i++)
{
status = 0; // 假设数组已经有序
for (int j = length - 2; j >= i; j--)
{
if (arr[j] > arr[j+1])
{
swap(arr, j, j+1);
status = 1; // 有交换，重置为1，数组可能还不是完全有序，需要再做校验
}
}
}
}
这个相对上面的冒泡排序有了一些优化，引入了一个标志位。还是拿一个最简单的数组int arr[] = { 2, 1, 3, 4}；先把标志位设置为1，然后在内外循环之间将标志位设置为0，假设数组已经有序。内循环从后到前依次比较2个相邻元素，如果if一直为假，即可证明arr[0]<=arr[1]<=...<=arr[length-1]。标志位没有被重置为1。下一次循环，外循环条件也不满足，结束循环。如果发生了交互，就把标志位重置为1，数组可能还不是完全有序，需要下一次循环再做校验。
冒泡排序到这里就结束了，可能会略显啰嗦，啰嗦的原因是大家觉得冒泡排序太简单，后面到略微复杂一些的希尔快速等排序的时候，也会保持这个风格，确保所有看过文章的人都能看懂，并且把排序代码正确的写出来。
