简谈快速排序
上篇文章说到了冒泡排序，这篇文章讲解一下快速排序算法。具体内容还是从算法实现思想、时间复杂度、算法稳定性以及算法实现四个方面介绍。
1
算法实现思想
1、设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2、以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3、从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4、从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5、重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
2
时间复杂度：max = O(n^2) 、 average = O(n*log2n)
3
算法稳定性：不稳定
4
算法实现
C语言实现
void algorithm(int *array, int left, int right){
if (left >= right) {
/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
return ;
}
int i = left;
int j = right;
int key = array[left];
while (i < j) {
/*控制在当组内寻找一遍*/
while (i < j && array[j] >= key) {
j --;
}
array[i] = array[j];/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left]，那么就是给key）*/
while (i < j && array[i] <= key) {
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
i ++;
}
array[j] = array[i];
}
array[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
//递归
algorithm(array, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
algorithm(array, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}Objective-C语言实现
- (void )fast:(NSArray *)array left:(int)left right:(int)right{
if (left >= right) {
return ;
}
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
int i = left;
int j = right;
int key = [tempArray[left] intValue];
while (i < j) {
while (i < j && [tempArray[j] intValue] >= key) {
j --;
}
tempArray[i] = tempArray[j];
while (i < j && [tempArray[i] intValue] <= key) {
i ++;
}
tempArray[j] = tempArray[i];
}
tempArray[i] = [NSNumber numberWithInt:key];
[self fast:tempArray left:left right:i - 1];
[self fast:tempArray left:i + 1 right:right];
}Swift语言实现
func fastAlgorithm(array:[Int], left:Int, right:Int) ->Void{
if left >= right{
return
}
var tempArray = array
var i = left
var j = right
let key = tempArray[left]
while(i < j){
while(i < j && tempArray[j] >= key){
j--
}
tempArray[i] = tempArray[j]
while(i < j && tempArray[i] <= key){
i++
}
tempArray[j] = tempArray[i]
}
tempArray[i] = key
fastAlgorithm(tempArray, left: left, right: i - 1)
fastAlgorithm(tempArray, left: i + 1, right: right)
}写在最后
大家可能会好奇，文章更新一段时间又被搁置了。唉，最近实在是太忙了，各种加班（你们懂得），没有连续整段的时间整理文章，有望各位读者多多包涵！！
今天发的文章有点晚咯~~~
最后，感谢大家阅读，如有问题，欢迎大家留言！！!
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2017-03-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读