简谈快速排序

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

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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2795
来自专栏机器之心

码如其人,同学你能写一手漂亮的Python函数吗

与多数现代编程语言一样,在 Python 中,函数是抽象和封装的基本方法之一。你在开发阶段或许已经写过数百个函数,但并非每个函数都生而平等。写出「糟糕的」函数会...

1352
来自专栏java一日一条

Java面试参考指南(一)

Java是一种基于面向对象概念的编程语言,使用高度抽象化来解决现实世界的问题。 面向对象的方法将现实世界中的对象进行概念化,以便于在应用之间进行重用。例如...

1733
来自专栏机器学习从入门到成神

设计模式之静态工厂、工厂方法和抽象工厂的联系与区别

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

852
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer 第二章 【变量和基本类型】

正文之前 C++的数据类型包括 算术类型(int double等)和空类型(void),今天发生了一些很可怕的事情,详情请看正文之后!!我好害怕!! 正文 1、...

38911
来自专栏Jimoer

Java设计模式学习记录-迭代器模式

这次要介绍的是迭代器模式,也是一种行为模式。我现在觉得写博客有点应付了,前阵子一天一篇,感觉这样其实有点没理解透彻就写下来了,而且写完后自己也没有多看几遍,上次...

913
来自专栏程序员宝库

给初学者:JavaScript 的常见注意点

作者: CarterLi 原文:https://segmentfault.com/a/1190000012730162 上篇说了一些 JS 中数组操作的常见误区...

2955
来自专栏web编程技术分享

JavaScript: 零基础轻松学闭包(1)

1995
来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

3238
来自专栏java架构师

读【重构】读书笔记之一 代码的坏味道

一、重复的代码: 包含完全重复、部分重复、以及程序不同结果相同 1)一个类的两个函数有相同的表达式  ---提取方法 2)两个互为兄弟的子类含有相同表达式---...

2667

扫码关注云+社区

领取腾讯云代金券