当前位置：首页 > 资讯 > 技术文档

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

时间：2022-12-10 16:00 编辑：来源：阅读：
扫一扫，手机访问

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

[b]算法思想 [/b]插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌。开始时，我们左手中没有牌，桌上有洗好的扑克牌，我们抓取一张扑克牌并放入左手的正确位置。为了找到一张扑克牌的正确位置，我们从右到左将它与手中的每张牌进行比较，左手上的牌总是排序好的，而这些牌原来都是桌上牌堆中顶部的牌，当我们抓完牌时，左手中的牌自然是有顺序的。之所以叫插入排序，不是为别的，正是因为该算法的核心就是将无序的元素插入排好序的部分。插入排序的核心思想即在于划分已排序和未排序，将每个待排序的元素逐个与已排序的元素比较，找出恰当的插入位置，插入元素，循环操作至结束这里是一张插入排序的使用流程，在写代码前先感受一下。 [img]http://files.jb51.net/file_images/article/201607/201676110656609.jpg?2016661177[/img] 我们以一维数组作为待排序的数据源，整个数组的以第一个待排序的元素为分水岭，前半部分为已排好序的，后半部分是等待排序的；开始排序时，从第二个元素开始循环开始，由于需要记录当前待排序的元素，我们引入一个变量记录分水岭的下标，也就是下面源码内的变量i；比较的过程比较直接，从分水岭往前，逐一比较值的大小，没找到需要插入的位置时向后移动元素，知道找到位置插入元素； [img]http://files.jb51.net/file_images/article/201607/201676110724690.png?20166611733[/img] [b]实现代码 1.由小到大排序：[/b]

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
}

[b]2.由大到小排序：[/b]

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 3.0基础学习之下标

资讯排行榜
更多>>