基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
- (NSInteger)BinarySearch:(NSArray *)array target:(id)key{//二分法查找
NSInteger left = 0;
NSInteger right = [array count] - 1;
NSInteger middle = [array count] / 2;
while (right >= left) {
middle = (right + left) / 2;
if (array[middle] == key) {
return middle;
}
if (array[middle] > key) {
right = middle - 1;
}
else if (array[middle] < key) {
left = middle + 1;
}
}
return -1;
}
5.6 快速排序
1. 从数列中挑出一个元素，称为 "基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
平均时间复杂度：O(n^2)
平均空间复杂度：O(nlogn) O(nlogn)~O(n^2)
- (NSMutableArray *)QuickSorkOC:(NSMutableArray *)array Count:(NSInteger)count{//快速排序
NSInteger i = 0;
NSInteger j = count - 1;
id pt = array[0];
if (count > 1) {
while (i < j) {
for (; j > i; --j) {
if (array[j] < pt) {
array[i++] = array[j];
break;
}
}
for (; i < j; ++i) {
if (array[i] > pt) {
array[j--] = array[i];
break;
}
}
array[i] = pt;
[self QuickSorkOC:array Count:i];
[self QuickSorkOC:array Count:count - i - 1];
}
}
return array;
}
5.7 归并排序
把序列分成元素尽可能相等的两半。
把两半元素分别进行排序。
把两个有序表合并成一个。
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber *num in ascendingArr) {
NSMutableArray *subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
while (tempArray.count != 1) {
NSInteger i = 0;
while (i < tempArray.count - 1) {
tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
i++;
}
}
NSLog(@"归并升序排序结果：%@", ascendingArr);
}
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
NSMutableArray *resultArray = [NSMutableArray array];
NSInteger firstIndex = 0, secondIndex = 0;
while (firstIndex < array1.count && secondIndex < array2.count) {
if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
}
while (firstIndex < array1.count) {
[resultArray addObject:array1[firstIndex]];
firstIndex++;
}
while (secondIndex < array2.count) {
[resultArray addObject:array2[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
5.8 基数排序
- (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr
{
NSMutableArray *buckt = [self createBucket];
NSNumber *maxnumber = [self listMaxItem:ascendingArr];
NSInteger maxLength = numberLength(maxnumber);
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in ascendingArr) {
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
[mutArray addObject:item];
}
NSInteger index = 0;
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
ascendingArr[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基数升序排序结果：%@", ascendingArr);