Swift实现快速排序算法的代码示例

思想

快速排序作为分治代表，通常实现由三步

1.数据中选择一个元素作为”基准”（pivot），通常选取最后一个元素；
2.分区(partition) 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3.对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

实现：

func quickSort(inout a: [Int], l: Int, r: Int) {

 if l < r {
 var i = l,
  j = r,
  x = a[i]
 while i < j && a[j] >= x {
  j -= 1
 }
 if i < j {
  a[i] = a[j]
  i += 1
 }
 while i < j && a[i] < x {
  i += 1
 }
 if i < j {
  a[j] = a[i]
  j -= 1
 }

 a[i] = x

 quickSort( & a, l: l, r: i - 1)
 quickSort( & a, l: i + 1, r: r)
 }

}

var b = [8, 7, 6, 5, 4, 3, 2, 1]

quickSort( & b, l: 0, r: 7)

print(b)
赞 (0)

相关推荐

  • 理解二叉堆数据结构及Swift的堆排序算法实现示例

    理解二叉堆数据结构及Swift的堆排序算法实现示例

    二叉堆的性质 1.二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的 2.最小堆父结点小于等于其每一个子结点的键值,最大堆则相反 3.每个结点的左子树或者右子树都是一个二叉堆 下面是一个最小堆: 堆的存储 通常堆是通过一维数组来实现的.在起始数组为 0 的情形中: 1.父节点i的左子节点在位置 (2*i+1); 2.父节点i的右子节点在位置 (2*i+2); 3.子节点i的父节点在位置 floor((i-1)/2); 维持堆的性质 我们以最大堆来介绍(后续会分别给出最大堆和

  • 简单理解插入排序算法及Swift版的代码示例

    简单理解插入排序算法及Swift版的代码示例

    算法思想 插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌.开始时,我们左手中没有牌,桌上有洗好的扑克牌,我们抓取一张扑克牌并放入左手的正确位置.为了找到一张扑克牌的正确位置,我们从右到左将它与手中的每张牌进行比较,左手上的牌总是排序好的,而这些牌原来都是桌上牌堆中顶部的牌,当我们抓完牌时,左手中的牌自然是有顺序的. 之所以叫插入排序,不是为别的,正是因为该算法的核心就是将无序的元素插入排好序的部分. 插入排序的核心思想即在于划分已排序和未排序,将每个待排序的元素逐个与已排序的元素比较,

  • Swift实现堆排序算法的代码示例

    算法思想 堆排序利用了最大堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单. 1.用最大堆排序的基本思想 (1)先将初始文件R[1..n]建成一个最大堆,此堆为初始的无序区 (2)再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key (3)由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-

  • Swift代码实现冒泡排序算法的简单实例

    Swift代码实现冒泡排序算法的简单实例

    冒泡排序原理 1.对需要排序的数据,俩俩进行比较,小的放前面,大的放后面 2.依次对每一对相邻的数据作步骤1的工作,当排序到最后一个元素的时候,我们能保证这个数据是最大. 3.针对所有的元素重复以上的步骤,除了最后一个(这里为什么需要针对除了最后一个元素的全部元素做一次呢,因为最后一个元素已经是最大的不需要排序了,同时,由于元素的交换,交换上来的元素的大小不一定比前面的元素的大,所以需要再做一次). 4持续对越来越少的元素重复3的步骤,直到没有任何一对元素需要比较. 时间复杂度 我们一般谈最坏时

  • Swift编程中实现希尔排序算法的代码实例

    Swift编程中实现希尔排序算法的代码实例

    思想 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL．Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,

  • Swift算法实现字符串转数字的方法示例

    前言 最近学完Swift之后一直没有机会实战,发现由于Swift发展历史原因,目前网上大部分的算法都是使用C.Java或其他语言实现的,几乎没有使用Swift实现的,所以自己打算使用Swift去实现一些主流的算法,既是对自己Swift的回顾,也是对自己算法方面的提高. 首先是用Swift实现字符串转数字,当然,肯定是不能使用Swift自带的字符串转数字的api. 题目: 使用Swift实现一个方法,输入字符串,输出该字符串转换成的数字. 例如,输入字符串"125",输出数字125 实现

  • Swift算法之栈和队列的实现方法示例

    Swift算法之栈和队列的实现方法示例

    一.概述 栈和队列在数据结构中是比较重要的一个数据结构. 其实对于栈和队列并不需要太深入的介绍,栈和队列的核心内容是栈是先进后出.队列是先进先出.在实际开发中有些场景也可能会用到,比如 APP 中用户可以撤销操作,比如下棋 APP 中的悔棋操作,返回上一步就是先进后出(后进先出),也就是栈的特性. 比如在售票 APP 中,为先下订单的用户先出票,就需要用到队列.当然这两个只是在简单场景下的情况,实际开发中情况可能更复杂,比如售票 APP 为会员用户优先出票等. 接下来就通过 Swift 去实现栈

  • Swift算法之二叉树实现的方法示例

    Swift算法之二叉树实现的方法示例

    一.概述 二叉树的结构一般是以二叉链表的形式来存储的.二叉链表的结构类似于双向链表,二叉链表的节点也是有两个结点指针的,一个指向左子树,一个指向右子树.二叉树主要有四种遍历方式:先序遍历.中序遍历.后序遍历.层次遍历.关于二叉树的内容网上有很多,这里不再做过多的陈述. 本文将用Swift去实现二叉树的创建.四种遍历方式等.下面的实现部分内容参考了青玉伏案和唐巧两位大神相关的文章. 二.实现思路及代码 以下面二叉树为例: 先序遍历:先遍历根节点然后再遍历左子树,最后遍历右子树. 故上面先序遍历的顺

  • 快速排序算法在Swift编程中的几种代码实现示例

    快速排序算法在Swift编程中的几种代码实现示例

    总所周知 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用. 基本原理是: 数组a = [1,3,5,7,6,4,2] 1 选定一个 基准 a[0] 2 把比 a[0]小的放左边,比a[0]大的放右边. 中断递归如果少于两个数字 则不执行. 3 然后再分别对两边 执行 1,2,3操作. 对快速排序 的 想法 1 在待排序元素 大部分是有序的情况下, 速度 非常很快. 2 在最差的情况下,速度就很慢了. 相当于冒泡了 3 所以 快排的 优化, 定基准 非常重要,

  • Swift算法实现逐字翻转字符串的方法示例

    前言 翻转字符串在字符串算法中算是比较常见的,而且被很多公司用作笔试题."逐字翻转字符串"是翻转字符串的翻版,也是之前Google的面试题,原题是这样的: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing

随机推荐