Objective-C
一淌实、冒泡排序
核心思想:
通過與相鄰元素的比較和交換，把最大的數(shù)交換到最后面映皆。
/**
5, 3, 8, 6, 4 (開始)
第一趟___(冒泡出最大值8)
3, 5, 8, 6, 4 （5和3交換）
3, 5, 8, 6, 4 （5和8不用交換）
3, 5, 6, 8, 4 （8和6交換）
3, 5, 6, 4, 8 （8和4交換）
第二趟___(冒泡出最大值6)
3, 5, 6, 4, 8 （3和5不用交換）
3, 5, 6, 4, 8 （5和6不用交換）
3, 5, 4, 6, 8 （6和4交換）
第三趟___(冒泡出最大值5)
3, 5, 4, 6, 8 （3和5不用交換）
3, 4, 5, 6, 8 （5和4交換）
第四趟___(冒泡出最大值4)
3, 4, 5, 6, 8 (3和4不用交換)
*/
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
for (int i = 0; i < array.count - 1; ++i) {
for (int j = 0; j < array.count - i - 1; ++j) {
if (array[j] > array[j + 1]) {
NSNumber *temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
NSLog(@"冒泡排序后：%@",array);
//輸出: 冒泡排序后：(3, 4, 5, 6, 8)
二访敌、 選擇排序
核心思想:
選出最小的數(shù)與第1個(gè)位置的數(shù)交換凉敲，然后從剩下的數(shù)中再找出最小的數(shù)與第2個(gè)位置的數(shù)交換衣盾，依次類推寺旺。
/**
5, 3, 8, 6, 4 (開始)
第一趟___(最小值3交換到第1個(gè)位置)
3, 5, 8, 6, 4 （5和3交換）
3, 5, 8, 6, 4 （3和8不用交換）
3, 5, 8, 6, 4 （3和6不用交換）
3, 5, 8, 6, 4 （3和4不用交換）
第二趟___(最小值4交換到第2個(gè)位置)
3, 5, 8, 6, 4 (5和8不用交換)
3, 5, 8, 6, 4 (5和6不用交換)
3, 4, 8, 6, 5 (5和4交換)
第三趟___(最小值5交換到第3個(gè)位置)
3, 4, 6, 8, 5 (8和6交換)
3, 4, 5, 8, 6 (6和5交換)
第四趟___(最小值6交換到第4個(gè)位置)
3, 4, 5, 6, 8 (8和6交換)
*/
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
for (int i = 0; i < array.count; ++i) {
for (int j = i + 1; j < array.count; ++j) {
if (array[i] > array[j]) {
NSNumber *temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
NSLog(@"選擇排序后：%@",array);
//輸出: 選擇排序后：(3, 4, 5, 6, 8)
三、 插入排序
核心思想:
找到合適位置插入元素势决，插入位置后移阻塑。
/**
5, 3, 8, 6, 4 (開始)
第一趟
3, 5, 8, 6, 4 （3插入 下標(biāo)0位置）
第二趟
3, 5, 8, 6, 4 （3插入 下標(biāo)2位置）
第三趟
3, 5, 6, 8, 4 （6插入 下標(biāo)2位置）
第四趟
3, 4, 5, 6, 8 （4插入 下標(biāo)1位置）
*/
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
for (int i = 1; i < array.count; i++) {
int j = i;
NSNumber *insertValue = array[i];
while (j > 0 && insertValue < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = insertValue;
}
NSLog(@"插入排序后：%@", array);
//輸出: 選擇排序后：(3, 4, 5, 6, 8)
四、快速排序
核心思想:
冒泡+二分法+分治果复。
/**
5, 3, 8, 6, 4 (開始)
第一趟(基準(zhǔn): 5)
4, 3, 8, 6, 4 (小)
4, 3, 8, 6, 8 (大)
4, 3, 8, 6, 8 (小)
4, 3, 8, 6, 8 (大)
4, 3, 5, 6, 8 (中間)
第二趟(基準(zhǔn): 4)
3, 3, 5, 6, 8 (小)
3, 3, 5, 6, 8 (大)
3, 4, 5, 6, 8 (中間)
第三趟(基準(zhǔn): 6)
3, 4, 5, 6, 8 (小)
3, 4, 5, 6, 8 (大)
3, 4, 5, 6, 8 (中間)
*/
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
int end = [[NSNumber numberWithInteger:array.count - 1] intValue];
[self quickSort:array start:0 end:end];
NSLog(@"選擇排序后：%@", array);
//輸出: 選擇排序后：(3, 4, 5, 6, 8)
- (void)quickSort:(NSMutableArray *)array start:(int)start end:(int)end{
//遞歸結(jié)束
if (start >= end){
return;
}
int index = [self indexQuickSort:array left:start right:end];
[self quickSort:array start:start end:index - 1];
[self quickSort:array start:index + 1 end:end];
}
- (int)indexQuickSort:(NSMutableArray *)array left:(int)left right:(int)right{
NSNumber *keyValue = array[left]; //基準(zhǔn)值
while (left < right) {
while (left < right && array[right] >= keyValue) {
right--;
}
array[left] = array[right]; //小的換到左邊
while (left < right && array[left] <= keyValue) {
left++;
}
array[right] = array[left]; //大的換到右邊
}
array[left] = keyValue; //基準(zhǔn)換到中間
return left;
}
