Swift 排序算法

本文采用数组实现。

直接插入排序

思想：每次将无序区的第一个记录按关键字插入到有序区的合适位置，并将有序区的长度加1。

func insertSort(array: inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }

    for i in 1..<(array.count-1) {// 从1开始，因为默认为有序区
        if array[i + 1] < array[i] {// 需要插入有序序列
            let temp = array[i + 1] //保存将要被有序区向后移顶替的值
            var j = i + 1// 有序区的序号,+1 为了不取到array[-1]
            repeat {// 数据移动，比temp大的都往后移
                j -= 1
                array[j + 1] = array[j]
            } while array[j - 1] > temp// 还需要移动
            
            // 插入
            array[j] = temp
        }
    }
}
复制代码

希尔排序

又称作缩小增量排序,是对直接插入 排序 的改进。

思路：shell排序是相当于把一个数组中的所有元素分成几部分来排序；先把几个小部分的元素排序好，让元素大概有个顺序，最后再全面使用插入排序。一般最后一次排序都是和上面的直接插入排序一样的。

/// 一趟希尔排序，增量为dk
func shellInsert(array: inout [Int], dk: Int) -> Void {
    for i in 0..<(array.count-dk) {
        if array[i + dk] < array[i] {// 需要插入有序序列
            let temp = array[i + dk]// 保存将要被有序区向后移顶替的值
            var j = i + dk// 有序区的序号+dk 为了不取到array[-1]
            repeat {// 数据移动，比temp大的都往后移
                j -= dk
                array[j + dk] = array[j]
            }while (j - dk > 0) && (array[j - dk] > temp)// 还需要移动
            
            // 插入
            array[j] = temp
        }
    }
}

/// 希尔排序
func shellSort(array: inout [Int], dk: [Int]) -> Void {
    guard array.count > 1 else {
        return
    }

    // 按增量序列d[]对数组array作希尔排序
    for dkItem in dk {
        shellInsert(array: &array, dk: dkItem)
    }
}
复制代码

冒泡排序

思路：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

func bubbleSort(array:inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }

    for i in 0..<(array.count - 1) { // 外层循环为 数组长度 - 1
        for j in 0..<(array.count - 1 - i) { // 内层循环为 外层循环 - i
            if array[j] > array[j + 1] { // 冒泡操作
                array.swapAt(j, j + 1)
            }
        }
    }
}
复制代码

选择排序

思路：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

func selectSort(array:inout [Int]) -> Void {
    guard array.count > 1 else {
        return
    }
    
    for i in 0..<(array.count - 1) {
        var min = i // 有序区的最后一个位置
        
        for j in (i + 1)...(array.count - 1) { // 注意边界, 是遍历到最后一个
            if array[min] > array[j] {
                min = j; // 找到无序区中最小值的下标
            }
        }
        
        if i != min { // 防止相同位置交换操作
            array.swapAt(min, i)
        }
    }
}
复制代码

归并排序

归并 是指将两个或两个以上的有序序列组合成一个新的有序序列。 归并排序 是指把无序的待排序序列递归分解成若干个长度大致相等的有序自序列，并把有序子序列合并为整体有序序列的过程。

思路：

/// 合并
func merge(array:inout [Int], low:Int, mid:Int, high:Int){
    
    var tempArray = Array<Int>()
    var indexA = low
    var indexB = mid
    
    while (indexA < mid) && (indexB < high) {
        if array[indexA] < array[indexB]{
            tempArray.append(array[indexA])
            indexA += 1
        }else{
            tempArray.append(array[indexB])
            indexB += 1
        }
    }
    
    while indexA < mid {
        tempArray.append(array[indexA])
        indexA += 1
    }
    
    while indexB < high{
        tempArray.append(array[indexB])
        indexB += 1
    }
    
    var index = 0
    for item in tempArray{
        array[low + index] = item
        index += 1
    }
}
/// 拆分最后合并
func mergeSort(array:inout [Int], low: Int, high: Int) -> Void {
    guard array.count > 1 else {
        return
    }

    if low + 1 < high {
        
        let mid = (low + high) / 2
        mergeSort(array: &array, low: low, high: mid)
        mergeSort(array: &array, low: mid, high: high)
        merge(array: &array, low: low, mid: mid, high: high)
    }
}
// 测试用例
// var sortArray = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04]
// mergeSort(array: &sortArray, low: 0, high: sortArray.count)
复制代码

快速排序

对冒泡排序的改进，常简称为快排。

思想：首先从待排序列中选定一个记录，称之为枢轴，通过关键字与枢轴的比较将待排序的序列划分成位于枢轴前后的两个自序列，其中枢轴之前的子序列的所有关键字都不大于枢轴，枢轴之后的子序列的所有关键字都不小于枢轴；此时枢轴已到位，再按同样方法对这两个子序列分别递归进行快速排序，最终使得整个序列有序。

// 进行一次划分，并返回枢轴的最终位置
func partiton(array:inout [Int], low: Int, high: Int) -> Int {
    
    var left = low, right = high  // 设置左右起点
    let x = array[low] // 设置枢轴
    
    repeat{// left 和 right 从待排序列的两端交替地向中间移动
        
        while (array[right] > x) && (left < right) { // 从右往左找, 找出比枢轴小的数
            right -= 1
        }
        
        while (array[left] <= x) && (left < right) { // 从左往左找, 找出比枢轴大的数
            left += 1
        }
        
        if left < right {
            array.swapAt(left, right) // 交换操作
        }
        
    } while left < right
    
    // 枢轴移到正确位置
    if low != right { // 防止交换位置相同
        array.swapAt(low, right) // 将中值和左边有序区的的最后一个数交换
    }
    
    return left // 返回枢轴的最终位置
}
func quickSort (array:inout [Int], low: Int, high: Int) -> Void {
    guard array.count > 1 else {
        return
    }
    
    if low < high {// 长度大于1
        let pivot = partiton(array: &array, low: low, high: high)
        quickSort(array: &array, low: low, high: pivot - 1)// 对枢轴之前的子序列递归快排
        quickSort(array: &array, low: pivot + 1, high: high)// 对枢轴之后的子序列递归快排
    }
}
// 测试用例
// var sortArray = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04]
// quickSort(array: &sortArray, low: 0, high: sortArray.count-1)
复制代码

堆排序

思路：首先将待排序列建成一个大顶堆，使得堆顶结点最大；将堆顶结点与堆尾结点交换位置，堆长度减1（即最大记录排序到位）；然后调整剩余结点为堆，得到次大值结点；重复这一过程，即可得到一个升序序列。

/// 堆排序
// 筛选堆
func shiftDown(array:inout Array<Int>,i:Int,length:Int) -> Void {
    var i = i;
    let temp = array[i];// 保存当前元素
    var k = 2*i + 1 // 因为数组根结点为0，所以左子结点编号要 +1
    
    while k < length {// 从左子结点开始
        if((k+1 < length) && (array[k] < array[k+1])){//如果左子结点小于右子结点，k指向右子结点
            k += 1;
        }
        if(array[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            array[i] = array[k];
            i = k;
        } else {
            break;
        }
        k = k*2 + 1
    }
    
    array[i] = temp;// 将temp值放到最终的位置
}
func makeHeap(array:inout Array<Int>) -> Void {
    for i in (0...(array.count/2-1)).reversed() {
        //从第一个非叶子结点从下至上，从右至左调整结构
        shiftDown(array: &array, i: i, length: array.count)
    }
}
func heapSort(array:inout Array<Int>) -> Void {
    guard array.count > 1 else {
        return
    }
    
    // 构建大顶堆
    makeHeap(array: &array)
    
    // 调整堆筛选 + 交换堆顶元素与末尾元素
    for j in (1...(array.count-1)).reversed() {
        array.swapAt(0, j)//将堆顶元素与末尾元素进行交换
        shiftDown(array: &array, i: 0, length: j)//重新对堆筛选
    }
}
复制代码