快速排序
快速排序是一种分而治之的算法。它选择一个数做为“基准”(pivot),将数组分为两部分,比“基准”数小的放在左边,比“基准”数大的放在的右边,然后分别对左边一部分和右边一部分重复上述操作,直到排序完成。
关键步骤:
1、选取“基准”,可以是第一个数,最后一个数,或者任意一个数。
2、确定“基准”的位置,选取一个变量 j ,遍历数组。选取变量 i ,做为最后一个比“基准”小的坐标位置,那么比“基准”小的个数为(i + 1),“基准”的位置就是(i + 2)。
3、递归的确定左、右两部分的“基准”,直到无法区分左右部分。
代码实现(Objective-c):
//快速排序
- (void)quickSortWithLeft:(int)left right:(int)right array:(NSMutableArray *)mularray{
NSLog(@"--%@",mularray);
if (left < right) {
int pi = [self partition:mularray left:left right:right];
[self quickSortWithLeft:left right:pi - 1 array:mularray];
[self quickSortWithLeft:pi + 1 right:right array:mularray];
}
}
- (int)partition:(NSMutableArray *)mularray left:(int)left right:(int)right {
//取最后一个做为 pivot
int pivot = [mularray[right] intValue];
int i = left - 1;//i 表示“基准”左边的位置
for (int j = left; j < right; j++) {
int value = [mularray[j] intValue];
//如果当前值比“基准”小,i++
if (value <= pivot) {
i ++;
//把当前值放在 i 的右边
[mularray exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
//把“基准”放在 i 的右边
[mularray exchangeObjectAtIndex:i + 1 withObjectAtIndex:right];
//此时“基准”的下标为 i + 1
return i + 1;
}
图片解析:
QuickSort.png步骤解析:
1、i = -1,j = 0;10 < 70,i ++,位置 0 和 0 上的数交换。
此时数组为:10,80,30,90,40,50,70
2、i = 0,j = 1;80 > 70,不做任何操作。
3、i = 0,j = 2;30 < 70,i ++,位置 1 和 2 上的数交换。
此时数组为:10,30,80,90,40,50,70
4、i = 1,j = 3;90 > 70,不做任何操作。
5、i = 1,j = 4;40 < 70,i ++,位置 2 和 4 上的数交换。
此时数组为:10,30,40,90,80,50,70
6、i = 2,j = 5;50 < 70,i ++,位置 3 和 5 上的数交换。
此时数组为:10,30,40,50,80,90,70
7、i = 3,j = 6;此时j 等于数组的最大坐标,for循环终止。将“基准”放在 i + 1 的位置上,返回 i + 1 将数组分为两部分并重复以上步骤。
此时数组为:10,30,40,50,70,90,80
参考资料:
1、GeeksforGeeks
2、维基百科
网友评论