准备工作
/*
交换方法
*/
- (void)swap:(int *)p1 andB:(int *)p2 {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
一、快速排序
20140317163240031.gif
/*
快速排序
*/
- (void)quickSort:(int[])a start:(int)start end:(int)end {
if (start >= end) {
return; // 出口
}
int low = start;
int high = end;
int keyIndex = start;
// 一趟 快排跳出while
while (low < high) {
// 从后往前找
while (a[high] >= a[keyIndex] && high > keyIndex) {
high --;
}
//找到交换
if (a[high] < a[keyIndex]) {
[self swap:&a[high] andB:&a[keyIndex]];
keyIndex = high;
}
// 从前往后找
while (a[low] <= a[keyIndex] && low < keyIndex) {
low ++;
}
// 找到交换 并重新keyIndex赋值
if (a[low] > a[keyIndex]) {
[self swap:&a[low] andB:&a[keyIndex]];
keyIndex = low;
}
}
// 确定 keyIndex 位置并递归 两边
if (low == high) {
[self quickSort:a start:start end:keyIndex - 1];
[self quickSort:a start:keyIndex + 1 end:end];
}
}
二、归并排序
/*
归并排序
*/
- (void)mergeSort:(int[])a to:(int[])b start:(int)start end:(int)end{
if (start >= end) {
return;
}
//分成两部分
int middle = start + (end - start) / 2;
// 递归前半部分拆分
[self mergeSort:a to:b start:start end:middle];
// 递归后半部分查分
[self mergeSort:a to:b start:middle + 1 end:end];
// 开始出栈 已经分到最小数组 开始排序合并 现在栈中存储的是一系列 start end middle 值 从栈顶出
int bIndex = start;
int preIndex = start;
int sufIndex = middle + 1;
while (preIndex != middle && sufIndex != end +1) {
if (a[preIndex] > a[sufIndex]) {
b[bIndex++] = a[sufIndex++];
} else {
b[bIndex++] = a[preIndex++];
}
}
if (preIndex != middle) {
b[bIndex++] = a[preIndex++];
}
if (sufIndex != middle) {
b[bIndex++] = a[sufIndex++];
}
// 此时b 中为有序数组 a 中是带排序数组
int j = start;
while (j< end + 1) {
a[j] = b[j];
j++;
}
}
三、堆排序
20140317163501125.gif
/*
堆排序
*/
- (void)heapSort:(int[])a length:(int)length {
[self creatHeap:a length:length];
for (int i = length - 1; i >= 0; i--) {
[self swap:&a[0] andB:&a[I]];
[self ajustHeap:a head:0 length:i];
}
}
// 建堆
- (void)creatHeap:(int[])a length:(int)length {
// 从最后一个父节点 开始向下调整建堆
int n = length / 2 - 1;
for (int i = n; i >= 0; i--) {
[self ajustHeap:a head:i length:length];
}
}
// 向下调整
- (void)ajustHeap:(int[])a head:(int)head length:(int)length {
// 初始化 左节点
int leftChild = 2 *head + 1;
// 记录最大的节点
int bigger = leftChild;
if (bigger >= length) { //只有一个点
return;
}
// 比较左右节点 把较大index赋值给bigger
int rightChild = 2 *head +2;
if (rightChild < length) {
if (a[rightChild] > a[bigger]) {
bigger = rightChild;
}
}
// 和根节点比较 如果大于根节点则 交换两个节点 并递归继续向下调整
if (a[bigger] > a[head]) {
[self swap:&a[bigger] andB:&a[head]];
[self ajustHeap:a head:bigger length:length];
}
}
四、 二分查找
/*
二分查找
*/
- (int)binarySearch:(int[])a length:(int)length key:(int)key {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >>1);
if (a[mid] > key) {
low = mid + 1;
} else if (a[mid < key]) {
high = mid -1;
} else {
return mid;
}
}
return -1;
}
五、 冒泡排序
/*
OC 冒泡排序及优化
*/
- (NSArray *)bubbleSort:(NSArray *)sortArray {
NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
BOOL isOrdered = NO; // 跳出循环标识
NSInteger length = sortArray.count;
NSInteger count1 = 0;// 外层循环次数
NSInteger count2 = 0;//内层循环次数
for (int i = 0; i < length; i ++) {
isOrdered = NO;
count1 ++;
for (int j = 0; j < length - i - 1; j ++) { // 一趟排序过后,最大值确定在最后边 所以排序范围递减
count2 ++;
if ([sort[j] integerValue] > [sort[j +1] integerValue]) {
[sort exchangeObjectAtIndex:j withObjectAtIndex:j+1];
isOrdered = YES;
}
}
if (!isOrdered) {
break;// 一趟排序如果已经有序 则跳出循环
}
}
NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
return [sort copy];
}
NSArray *arr = @[@34,@54,@12,@78,@3,@45,@9];
NSArray *arr1 = [self bubbleSort:arr];
count1 : 6
count2 :21
sort: (
3,
9,
12,
34,
45,
54,
78
)
/*
排序过程
*/
20160609181236390.gif
I = 0;
34 54 12 78 3 45 9
34 12 54 78 3 45 9
34 12 54 3 78 45 9
34 12 54 3 45 78 9
34 12 54 3 45 9 78
I = 1;
12 34 54 3 45 9 78
12 34 3 54 45 9 78
12 34 3 45 54 9 78
12 34 3 45 9 54 78
I = 2;
12 3 34 45 9 54 78
12 3 34 9 45 54 78
I = 3;
3 12 34 9 45 54 78
3 12 9 34 45 54 78
I = 4;
3 9 12 34 45 54 78
六、 选择排序
/*
选择排序
*/
- (NSArray *)selectedSort:(NSArray *)sortArray {
NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
NSInteger length = sortArray.count;
NSInteger count1 = 0;// 外层循环次数
NSInteger count2 = 0;//内层循环次数
NSInteger curentIndex = 0;
NSInteger minIndex = 0;
for (int i = 0; i < length - 1; i ++) {
count1 ++;
curentIndex = i;
minIndex = i;
for (int j = i + 1; j < length; j ++) {
count2 ++;
if ([sort[minIndex] integerValue] > [sort[j] integerValue]) {
minIndex = j;
}
}
if (curentIndex != minIndex) {
[sort exchangeObjectAtIndex:curentIndex withObjectAtIndex:minIndex];
}
}
NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
return [sort copy];
}
NSArray *arr = @[@34,@54,@12,@78,@3,@45,@9];
NSArray *arr1 = [self selectedSort:arr];
count1 : 6
count2 :21
sort: (
3,
9,
12,
34,
45,
54,
78
)
/*
排序过程
*/
选择排序
原始数据
34 54 12 78 3 45 9
I = 0;
minIndex = 0;
minIndex = 2;
minIndex = 4;
3 54 12 78 34 45 9
I = 1;
minIndex = 1;
minIndex = 2;
minIndex = 6;
3 9 12 78 34 45 54
I = 2;
minIndex = 2;
I = 3;
minIndex = 3;
minIndex = 4;
3 9 12 34 78 45 54
I = 4;
minIndex = 4;
minIndex = 5;
3 9 12 34 45 78 54
I = 5;
minIndex = 5;
minIndex = 6;
3 9 12 34 45 54 78
网友评论