美文网首页iOS Developer
Swift 3.0实现面试常考的排序算法

Swift 3.0实现面试常考的排序算法

作者: 是小胖阿 | 来源:发表于2017-02-20 16:23 被阅读0次

1.插入排序

⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5

  public func insertionSort(arr: inout Array<Int>) {//时间复杂度O(n^2)
    for i in 0..<arr.count - 1 {
        if arr[i + 1] < arr[i] {
            let temp = arr[i + 1]
            for j in (1...(i + 1)).reversed() {
                if arr[j - 1] > temp {
                    (arr[j - 1],arr[j]) = (arr[j],arr[j - 1])
                }
            }
        }
    }
}

2.冒泡排序

⒈比较相邻的元素。如果第一个比第二个大,就交换他们两个。
⒉ 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
⒊ 针对所有的元素重复以上的步骤,除了最后一个。
⒋ 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  public func bubbleSort(arr: inout Array<Int>) {//时间复杂度O(n^2)
    for i in 0..<(arr.count - 1) {
        for j in 0..<(arr.count - i - 1) {
            if arr[j] > arr[j + 1] {
                (arr[j],arr[j + 1]) = (arr[j + 1],arr[j])
            }
        }
    }
}

3.快速排序(冒泡排序的改进版)

⒈设置两个变量i、j,排序开始的时候:i=0,j=n-1。
⒉ 以第一个数组元素作为关键数据,赋值给key,即key=A[0]。
⒊ 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换。
⒋ 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换。
⒌重复第3、4步,直到i=j

 public func quickSort(arr: inout Array<Int>, leftIndex:  Int, rightIndex:  Int) {
    if leftIndex < rightIndex {
        var left = leftIndex
        var right = rightIndex
        let midIndex = getMidIndex(arr: &mArray, leftIndex: &left, rightIndex: &right)
        quickSort(arr: &mArray, leftIndex: leftIndex, rightIndex: midIndex - 1)
        quickSort(arr: &mArray, leftIndex: midIndex + 1, rightIndex: rightIndex)
    }
}

private func getMidIndex(arr: inout Array<Int>, leftIndex: inout Int, rightIndex: inout Int) -> (Int) {
    let temp = arr[leftIndex]
    while leftIndex < rightIndex {

        while leftIndex < rightIndex && temp <= arr[rightIndex] {
            rightIndex -= 1
        }
        if leftIndex < rightIndex {
            arr[leftIndex] = arr[rightIndex]
        }
        while leftIndex < rightIndex && arr[leftIndex] <= temp {
            leftIndex += 1
        }
        if leftIndex < rightIndex {
            arr[rightIndex] = arr[leftIndex]
        }
    }
    arr[leftIndex] = temp
    return leftIndex
}

4.归并排序(速度仅次于快速排序)

⒈将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素。
⒉ 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素。
⒊ 重复步骤2,直到所有元素排序完毕。

 public func mergeSort(arr: inout Array<Int>) {
    var tempArr: Array<Array<Int>> = []
    for item in arr {
       var subArr: Array<Int> = []
       subArr.append(item)
       tempArr.append(subArr)
    }
    while tempArr.count != 1 {
        var i = 0
        while i < tempArr.count - 1 {
            tempArr[i] = mergeTowArr(arr1: tempArr[i], arr2: tempArr[i+1])
            tempArr.remove(at : i+1)
            i += 1
        }
    }
 }

private func mergeTowArr(arr1: Array<Int>, arr2: Array<Int>) -> Array<Int> {
    var mergeArr: Array<Int> = []
    var firstIndex = 0
    var secondIndex = 0
    while firstIndex < arr1.count && secondIndex < arr2.count {
        if arr1[firstIndex]  < arr2[secondIndex] {
            merge.append(arr1[firstIndex])
            firstIndex += 1
        }else{
            merge.append(arr2[secondIndex])
            secondIndex += 1
        }
    }
    while firstIndex < arr1.count {
         merge.append(arr1[firstIndex])
         firstIndex += 1
    }
    while secondIndex < arr2.count {
         merge.append(arr2[secondIndex])
         secondIndex += 1
    }
    
    return mergeArr
}

5.选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)

public func selectSort(arr: inout Array<Int>) {
    for i in 0..<arr.count {
        var index = i
        for j in (i + 1)..<arr.count {
            if arr[index] > arr[j] {
                index = j
            }
        }
        if index != i {
            (arr[i],arr[index]) = (arr[index],arr[i])
        }
    }
}

6.堆排序(选择排序的一种)

通过headMakeFrom将数组arr变为大顶堆,再把大顶堆的第一值和最后一个值交换,数组长度减1。通过heapAdjast将交换后的数组重新排序成大顶堆直到数组长度为0。

public func heapSort(arr: inout Array<Int>) {//时间复杂度O(n*logn)
    var endIndex = arr.count - 1
    headMakeFrom(arr: &arr)

    while endIndex > 0 {
        (arr[0],arr[endIndex]) = (arr[endIndex],arr[0])
        heapAdjast(arr: &arr,starIndex: 1, arrLength: endIndex)
        endIndex -= 1
    }
}


private func heapMakeFrom(arr: inout Array<Int>) {
    var lastHead = arr.count/2
    while lastHead > 0 {
        heapAdjast(arr:  &arr, starIndex: lastHead, arrLenght: arr.count)
        lastHead -= 1
    }
}

private func heapAdjast(arr: Array<Int>, starIndex: Int, arrLength: Int) {
    var temp = arr[starIndex - 1]
    var parentIndex = starIndex
    var childIndex = 2 * parentIndex
    while childIndex <= arrLength {
        if childIndex < arrLength && arr[childIndex] > arr[childIndex - 1] {
            childIndex += 1
        }
        if arr[childIndex-1] > temp {
            arr[parentIndex - 1] = arr[childIndex - 1]
        }else{
            break 
        }
        parentIndex = childIndex
        childIndex = 2 * parentIndex 
    }
    arr[parentIndex - 1] = temp
}

相关文章

  • Swift 3.0实现面试常考的排序算法

    1.插入排序 ⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描...

  • 常见排序算法 - Swift实现

    常见排序算法 排序算法是算法和数据结构中最为基础,同时很多面试也都是各种算法的变种,因此使用swift对目前较为常...

  • 京东高级java现场三面,包含:算法、数据库、设计模式、java

    京东技术面试(一): 算法面试: 二叉树怎么实现的 知道哪些排序算法 快排怎么实现 堆排序怎么实现 一道算法题:两...

  • 面试常问的小算法总结

    前言 本文快速回顾了面试常考的算法,用作面试复习,事半功倍。 需要说明的是,由于算法的代码实现主要注重思路的清晰,...

  • 各种排序算法的使用范围

    面试题目:各种排序算法的使用范围 解析: 排序可以算是最基本,最常用的算法,也是笔试面试中最常被考的算法,最基本的...

  • 常见算法题

    1. reserve 让数组反转倒置 2. 排序算法 面试最常考:快速排序和希尔算法 (tips) 原理:如果是想...

  • 排序算法

    前言: 排序算法是面试经常考的题,游戏开发对算法是非常看重的,不说你了解所有算法,但是基本的排序算法是必须掌握的基...

  • 图文详解面试常考算法「拓扑排序」

    前言 Topological sort 又称 Topological order,这个名字有点迷惑性,因为拓扑排序...

  • 常用排序算法(一)

    排序是笔试面试的常考知识点,检验应聘者对排序这类基本算法的接受程度和数据结构的理解。在2017春季暑期实习生招聘过...

  • 面试算法知识梳理(12) - 二叉树算法第二部分

    面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 ...

网友评论

    本文标题:Swift 3.0实现面试常考的排序算法

    本文链接:https://www.haomeiwen.com/subject/zhvjwttx.html