美文网首页Aha! Algorithms
Aha! Algorithms - Quicksort

Aha! Algorithms - Quicksort

作者: su3 | 来源:发表于2017-03-16 22:03 被阅读0次

《啊哈!算法》第 1 章第 3 节,快速排序的 Swift 实现

问题

为给定数字序列排序

解决

以左侧第一个位置为基准数,假设最左侧索引值为 i,最右侧索引值为 j,先从右往左找小于基准数的值,然后左侧往右找大于基准数的值,找到后交换位置,直到 i 与 j 相遇,此时将最左侧基准数与索引 i 位置的值交换位置,接着递归循环为左右两侧分别排序。

var array = [3, 1, 2, 5, 4, 6, 9, 7, 10, 8]

func quicksort( left: Int, right: Int){
    var i: Int, j: Int, temp: Int
    
    if left > right {
        return
    }
    
    temp = array[left] //temp 存基准数
    i = left
    j = right
    
    //两边向中间查找,与基准数相比较,直到i和j相遇
    while i != j {
        //先从右往左找小于基准数的数
        while array[j] >= temp && i < j {
            j -= 1
        }
        
        //再从左往右找大于基准数的数
        while array[i] <= temp && i < j {
            i += 1
        }
        
        //找到后如果没有相遇,那么交换位置
        if i < j {
            swap(&array[i], &array[j])
        }
    }
    
    //当 i 和 j 相遇时,将基准数与当前位置的值交换位置,基准数归位
    array[left] = array[i]
    array[i] = temp
    
    //接着用同样的方法给基准数左边与右边两个序列分别排序
    quicksort(left: left, right: i-1) //继续处理左边,递归过程
    quicksort(left: i+1, right: right) //继续处理右边,递归过程
    
}

quicksort(left: 0, right: array.count-1)

for item in array {
    print("\(item)")
}

快速排序的最差时间复杂度和冒泡排序一样为O(N2),平均时间复杂度为O(NLogN)。

代码在 GitHub

相关文章

  • Aha! Algorithms - Quicksort

    《啊哈!算法》第 1 章第 3 节,快速排序的 Swift 实现 问题 为给定数字序列排序 解决 以左侧第一个位置...

  • Aha! Algorithms

    1. 涉及的数据结构 栈、队列、链表、树、并查集、堆、图 2. 涉及的算法 排序、枚举、深度和广度优先搜索、图的遍...

  • Aha! Algorithms - Queue

    《啊哈!算法》第 2 章第 1 节,队列的 Swift 实现 问题 给一个数字序列,解密方法是:删除第 1 个,将...

  • Aha! Algorithms - Dijkstra

    《啊哈!算法》第 6 章第 2 节,Dijkstra 算法求最短路径的 Swift 实现。 问题 已经若干顶点和路...

  • Aha! Algorithms - Floodfill

    《啊哈!算法》第 4 章第 5 节,漫水填充法的 Swift 实现。 问题 给一个群岛地图中不同的岛屿填充不同的颜...

  • Aha! Algorithms - Bomberman

    《啊哈!算法》第 3 章第 2 节,bomb 人的 Swift 实现。 问题 在哪里放置 bomb 才可以消灭最多...

  • Aha! Algorithms - Stack

    《啊哈!算法》第 2 章第 2 节,栈的 Swift 实现。 问题 判断字符串是否回文 解决 将字符串前半部分入栈...

  • Aha! Algorithms - Heap

    《啊哈!算法》第 7 章第 3 节,创建最小堆的 Swift 实现。 问题 把一个数组转换为最小堆,并从小到大输出...

  • Aha! Algorithms - Bucket Sort

    《啊哈!算法》第 1 章第 1 节,桶排序的 Swift 实现 问题 班上 5 个同学的考试成绩分别为:5 分,3...

  • Aha! Algorithms - Bubble Sort

    《啊哈!算法》第 1 章第 2 节,冒泡排序的 Swift 实现 问题 给学生成绩排序,打印排序后的名字(和成绩)...

网友评论

    本文标题:Aha! Algorithms - Quicksort

    本文链接:https://www.haomeiwen.com/subject/islsnttx.html