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

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

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)，下同。
第二次 gap = 5 / 2 = 2
排序后

第三次 gap = 2 / 2 = 1

第四次 gap = 1 / 2 = 0 排序完成得到数组：

实现代码：

 import UIKit

   func shellsort(inout a : [Int]){

     let n = a.count-1

     for(var gap = n / 2; gap > 0; gap /= 2){
       for j in gap...n {
         if a[j] < a[j-gap]{
           let tmep = a[j]
           var k = j - gap
           while k >= 0 && a[k] > tmep {//扫一遍 好填最小值
             a[k + gap] = a[k]
             k -= gap
           }
           a[k + gap] = tmep
         }
       }
     }

   }

   var a = [2,5,6,7,8,9,0,1,3,4]

   shellsort(&a)
赞 (0)

相关推荐

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

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

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

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

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

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

  • 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实现快速排序算法的代码示例

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

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

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

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

  • 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版的代码示例

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

  • 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 所以 快排的 优化, 定基准 非常重要,

随机推荐