Swift实现Selection Sort选择排序算法的实例讲解

选择排序Selection Sort是一种和插入排序Insertion Sort类似的排序方法，它同样只适用于对规模不大的集合进行排序。它的核心思想是，在序列内部，把序列逻辑上分成已排序和未排序两部分，不断找到未排序部分中最符合排序规则的元素，添加进已排序部分，直到序列中所有元素都已经添加到了已排序部分，此时，整个序列就排序完成了。
冒泡排序是两两比较不断交换来实现排序，所以比较繁琐。
而选择排序  则是先选择要交换的那个数，才去交换。这样就可以省去很多不必要的步骤。

Swift版实现示例：

func selectSort(var arr: [Int]) ->[Int] {
 var min = 0

 // 只需要n-1趟
 for var i = 0; i < arr.count - 1; ++i {
  min = i

  // 从第n+1趟起始找到末尾
  for var j = i + 1; j < arr.count; ++j {

   // 找到比min位置更小的，就更新这一趟所找到的最小值的位置
   if arr[j] < arr[min] {
    min = j
   }
  }

  // 如果min与i不相等，说明有比i位置更小的，所以需要交换
  if min != i {
   let temp = arr[i]
   arr[i] = arr[min]
   arr[min] = temp
  }
 }

 return arr
}
赞 (0)

相关推荐

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

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

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

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

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

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

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

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

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

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

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

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

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

    冒泡排序原理 1.对需要排序的数据,俩俩进行比较,小的放前面,大的放后面 2.依次对每一对相邻的数据作步骤1的工作,当排序到最后一个元素的时候,我们能保证这个数据是最大. 3.针对所有的元素重复以上的步骤,除了最后一个(这里为什么需要针对除了最后一个元素的全部元素做一次呢,因为最后一个元素已经是最大的不需要排序了,同时,由于元素的交换,交换上来的元素的大小不一定比前面的元素的大,所以需要再做一次). 4持续对越来越少的元素重复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实现快速排序算法的代码示例

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

随机推荐