简谈快速排序

上篇文章说到了冒泡排序,这篇文章讲解一下快速排序算法。具体内容还是从算法实现思想、时间复杂度、算法稳定性以及算法实现四个方面介绍。

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)
    }

写在最后

大家可能会好奇,文章更新一段时间又被搁置了。唉,最近实在是太忙了,各种加班(你们懂得),没有连续整段的时间整理文章,有望各位读者多多包涵!!

今天发的文章有点晚咯~~~

最后,感谢大家阅读,如有问题,欢迎大家留言!!!

本文分享自微信公众号 - 攻城狮的动态(iOSDevSkills),作者:Jack_lin

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 简谈选择排序

    Jacklin
  • 简谈冒泡排序

    Jacklin
  • 简谈归并排序

    Jacklin
  • 八种方式实现多条件匹配

    之前在Excel内部的分享交流群和别的讲师探讨了多条件匹配有哪些实现方式。 围观的市民刘先生表示:我活了二十多年,看见斗图的比较多,这么无聊斗Excel使用技巧...

    用户1332619
  • 2020年1月编程语言排行榜:【2019年度最佳编程语言】公布!

    在每个人都认为Python将连续第二年成为TIOBE的年度编程语言的时候,老编程语言C语言凭借2.4%的年增长率,获得了奖项。

    老九君
  • Mybatis foreach标签含义

    这种方式非常方便,我们只要把查询条件写出来,剩下的操作都由mysql来处理。而在实际场景中,为了减少底层耦合,我们一般不通过mysql中的子查询方式联表查询,而...

    xiaoxi666
  • 二分查找变种

    该算法有很多版本,这里给出java中实现比较好的一种方式。其中,>>>为无符号右移。

    xiaoxi666
  • Java基础系列(四十五):集合之Map

    Map是一个接口,代表的是将键映射到值的对象。一个映射不能包含重复的键,每个键最多只能映射到一个值。

    山禾说
  • TIOBE 6月编程语言排行榜:C语言仍为榜首,Rust首冲前20

    截止目前,Rust已经连续5年被Stackoverflow的用户评为“最受喜爱的编程语言”。

    老九君
  • Vue.js实战第五章练习题

    购物车需要展示一个已加入购物车的商品列表,包含商品名称、商品单价、购买数量、操作等信息,还需要实时显示购买的总价。其中购买的数量可以增加或减少,每类商品可以从购...

    听城

扫码关注云+社区

领取腾讯云代金券