文章涉及的全都是由小到大排序
简单选择排序：O(n^2)
外层进行n-1次循环，每次指定当前的第i个元素为最小值，保存下标，内层n-i+1次循环依次与当前保存的最小值下标的数进行比较，如果比所存下标内的数更小，则保存这个下表，内层循环结束，若i 与最小值下标不相等，则交换
//选择排序
- (NSMutableArray *)selectSort:(NSMutableArray *)array{
NSInteger n = array.count;
NSInteger min;
for (NSInteger i = 0; i < n-1 ; i++) {
min = i;
for (NSInteger j = i+1; j<n; j++) {
if ([array[min] intValue] > [array[j] intValue]) {
min = j;
}
}
if (min != i) {
id tmp =array[i];
array[i] = array[min];
array[min] = tmp;
}
}
return array;
}
冒泡排序：O(n^2)
从第一个位置开始，相邻两个位置的元素进行比较，如果反序，则进行交换，一次循环确定一个数的具体位置，进行n-1次循环
- (NSMutableArray *)sort:(NSMutableArray *)array{
NSInteger n = array.count;
//n-1次循环就可以了
for (NSUInteger i = 0; i < n -1; i ++) {
for (NSUInteger j = 1; j < n- i; j++) {
if ([array[j-1] intValue] > [array[j] intValue]) {
id tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
}
}
}
return array;
}
冒泡排序优化：再一次冒泡循环过程中更没有进行交换，说明待排序的序列已经有序了，使用一个标识位如果此次循环没有交换数据退出循环
- (NSMutableArray *)selectSort:(NSMutableArray *)array{
NSInteger n = array.count;
NSInteger min;
for (NSInteger i = 0; i < n-1 ; i++) {
min = i;
BOOL notFinished = YES;
for (NSInteger j = i+1; j<n; j++) {
if ([array[min] intValue] > [array[j] intValue]) {
min = j;
notFinished = NO;
}
}
if (min != i) {
id tmp =array[i];
array[i] = array[min];
array[min] = tmp;
}
if (notFinished) {
break;
}
}
return array;
}
插入排序：O(n^2)
将一个记录插入到已经排好序的序表中，从第二个数开始，进行n-1次循环，如果当前这个数小于前面的数，则一次与前面列表内的数进行比较，大于这个记录的都向后移动，然后将这个数插入正确的位置。
//插入排序
- (NSMutableArray *)insertSort:(NSMutableArray *)array{
NSInteger n = array.count;
for (NSInteger i = 1; i < n ; i++) {
id currentNum = array[i];
NSInteger currentIndex = i;
for (NSInteger j = i - 1; j >= 0; j--) {
if ([array[j] intValue] > [currentNum intValue]) {
array[j+1] = array[j];
array[j] = currentNum;
currentIndex = j;
}
}
}
return array;
}
归并排序：O(n log n)
将一个待排序序列看成是n个有序的序列，相邻的两个有序序列组合成一个有序序列，这样就有n/2个有序序列，再将相邻的两个有序序列组合成一个有序序列，这样就有n/4个有序序列,如此反复下去，最终得到一个长度为n的有序序列。
