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

算法思想
插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌。开始时，我们左手中没有牌，桌上有洗好的扑克牌，我们抓取一张扑克牌并放入左手的正确位置。为了找到一张扑克牌的正确位置，我们从右到左将它与手中的每张牌进行比较，左手上的牌总是排序好的，而这些牌原来都是桌上牌堆中顶部的牌，当我们抓完牌时，左手中的牌自然是有顺序的。
之所以叫插入排序，不是为别的，正是因为该算法的核心就是将无序的元素插入排好序的部分。
插入排序的核心思想即在于划分已排序和未排序，将每个待排序的元素逐个与已排序的元素比较，找出恰当的插入位置，插入元素，循环操作至结束
这里是一张插入排序的使用流程，在写代码前先感受一下。

我们以一维数组作为待排序的数据源，整个数组的以第一个待排序的元素为分水岭，前半部分为已排好序的，后半部分是等待排序的； 开始排序时，从第二个元素开始循环开始，由于需要记录当前待排序的元素，我们引入一个变量记录分水岭的下标，也就是下面源码内的变量i； 比较的过程比较直接，从分水岭往前，逐一比较值的大小，没找到需要插入的位置时向后移动元素，知道找到位置插入元素；

实现代码
1.由小到大排序：

func insertionSortBigger(var array: Array<Int>) -> Array<Int>{
  for(var j = 1 ; j<array.count ; j++){//从第二个开始向前对比插入
    let key = array[j] //记录要比较的值
    var i = j-1
    while(i>=0 && array[i]>key){//如果key较小，那么现有的位置向后移，为key空出位置
      array[i+1] = array[i] //移位
      i--
    }
    array[i+1] = key
  }
  return array
}

2.由大到小排序：

func insertionSortSmaller(var array: Array<Int>) -> Array<Int>{
  for(var j = 1 ; j<array.count ; j++){//从第二个开始向前对比插入
    let key = array[j] //记录要比较的值
    var i = j-1
    while(i>=0 && array[i]<key){//如果key较大，那么现有的位置向后移，为key空出位置
      array[i+1] = array[i] //移位
      i--
    }
    array[i+1] = key
  }
  return array
}
赞 (0)

相关推荐

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

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

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

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

    思想 快速排序作为分治代表,通常实现由三步 1.数据中选择一个元素作为"基准"(pivot),通常选取最后一个元素: 2.分区(partition) 所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边.分区操作结束后,基准元素所处的位置就是最终排序后它的位置. 3.对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为

  • 快速排序算法在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编程中实现希尔排序算法的代码实例

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

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

  • 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算法实现逐字翻转字符串的方法示例

    前言 翻转字符串在字符串算法中算是比较常见的,而且被很多公司用作笔试题."逐字翻转字符串"是翻转字符串的翻版,也是之前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

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

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

  • 理解二叉堆数据结构及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去实现二叉树的创建.四种遍历方式等.下面的实现部分内容参考了青玉伏案和唐巧两位大神相关的文章. 二.实现思路及代码 以下面二叉树为例: 先序遍历:先遍历根节点然后再遍历左子树,最后遍历右子树. 故上面先序遍历的顺

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

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

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

随机推荐