双向冒泡排序

https://www.2cto.com/kf/201601/488267.html

在每一次排序动作，先从左往右进行一次冒泡排序，再从右往左进行一次冒泡排序，用left和right分别记录左右两边已排序的元素位置，left大于right时，排序结束。例如：

8 2 6 9 7 3 4 5 1 0

第一次 [0] 8 2 6 7 3 4 5 1 [9]

第二次 [0 1] 2 6 7 3 4 5 [8 9]

第三次 [0 1 2] 6 3 4 5 [7 8 9]

第四次 [0 1 2 3] 4 5 [6 7 8 9]

第五次 [0 1 2 3 4] [5 6 7 8 9]

第六次 此时left = 5，right = 4，left > right，排序结束。

（因为每一次向双向的冒泡排序都能确定左右各一个元素的位置，也就是对称的，而且第一次开始是从左往右排序，所以最后一次肯定是在左边的已排序下标比右边的已排序元素下标大的时候）

+(void)bubbleSortArr:(NSMutableArray *)arr

{

 NSInteger len = arr.count;

 //每次向左向右冒泡排序都是排lo（包含）到hi（包含）的所有元素

 NSInteger lo = 0;//lo右边包含lo开始是未排序的

 NSInteger hi = len - 1;//hi左边包含hi开始是未排序的

 NSInteger l,r;

 while (lo<hi) {

 //每次左右两边各排好一个数，这样在没有交换的情况下，也能保证一次while循环后缩小向左向右的冒泡排序的范围

 l = lo+1;//下一次向左冒泡排序的开始下标

 r = hi-1;//下一次向右冒泡排序的开始下标

//这里的i取值范围是  右边未排好序的第一个数的下标一直到左边未排序好的最后一个数的下标减1

 for (NSInteger i = lo; i < hi; i++) {

 if ([arr[i]integerValue]>[arr[i+1]integerValue]) {

 NSNumber *num = arr[i];

 arr[i] = arr[i+1];

 arr[i+1] = num;

//向左冒泡排序最后一次做交换的两个元素下标，从大的那个开始是有序的，小的那个右边包含小的下标都是无序的，所以下一次排序需要包含到这个小的下标以及它前面的元素下标

 r = i;//r右边(不包括r)都是已经排序好的数,这里肯定不能用hi = i保存，因为hi是i的循环判断部分的变量，所以另外定义了r

 }

 }

 hi = r;//同理hi右边(不包括hi)都是已经排序好的数

//解析等同上循环i

 for (NSInteger i = hi; i > lo; i--) {

 if ([arr[i-1]integerValue]>[arr[i]integerValue]) {

 NSNumber *num = arr[i];

 arr[i] = arr[i-1];

 arr[i-1] = num;

//向右冒泡排序最后一次做交换的两个元素下标，从大的那个开始是有序的，小的那个右边包含小的下标都是无序的，所以下一次  排序需要包含到这个小的下标以及它前面的元素下标

 l = i;//l左边(不包括l)都是已经排序好的数,这里肯定不能用lo = i保存，因为lo是i的循环判断部分的变量，所以另外定义了l

 }

 }

 lo = l;//同理lo左边(不包括lo)都是已经排序好的数

 }

}