Swift 排序算法代码实现

冒泡排序

逐个比较并移动，每次循环确定一个最大元素

复杂度：最好O(n)，最坏，平均复杂度O(n^2), 空间复杂度O(1)。

稳定性：冒泡排序稳定与否，取决于判断相邻两个元素大小的的方式是> 或者是 >=

static func bublleSort(arr: [Int]) -> [Int] {
    var list = arr;
    for end in (1..<list.count - 1).reversed() {
        for j in 0...end {
            if list[j] > list[j+1] {
                (list[j], list[j+1]) = (list[j+1], list[j])
            }
        }
    }
    return list
}

优化1：序列如果完全有序，可以提前终止冒泡

优化2：尾部有序，可以通过记录最后一次交换的位置，减少比较次数

原地算法：不依赖额外的资源或者依赖少数的额外资源，仅依输出来覆盖输入

选择排序

从待排序数组中找到最大元素的位置，并与最后面的元素交换位置。

复杂度：最好，最坏，平均复杂度O(n^2), 空间复杂度O(1)。

稳定性：不稳定

static func sort(arr: [Int]) -> [Int] {
    if arr.count <= 1 {return arr}
    var list = arr;
    for end in (0..<list.count-1).reversed(){
        var maxIndex = 0;
        for start in 0..<end {
            if list[start] > list[maxIndex] {
                maxIndex = start;
            }
        }
        (list[maxIndex], list[end]) = (list[end], list[maxIndex])
    }
    return list
}

选择排序交换次数远小于冒泡排序，平均性能优于冒泡

不稳定排序，如数组[2 3 2 1 4]，2和1交换后，两个2的顺序便不稳定

优化：使用堆来选择最大值

堆排序

将无序的序列构建成大顶堆。

复杂度：最好，最坏，平均复杂度O(nlogn), 空间复杂度O(1)。

稳定性：不稳定

完全二叉树：假设根节点的编号是 i ，那么该根节点的左孩子的编号是 2i，右孩子的编号是 2i+1。

大顶堆：完全二叉树的根节点比其左右节点都要大

具体步骤：

1. 对序列进行原地建堆
2. 重复
   1. 交换堆顶元素与堆尾元素
   2. 堆元素数量减1
   3. 对0位置进行一次siftDown操作

class HeapSort: ArraySort {
    
    var list : [Int]?
    static var heapSize = 0
    
    static func sort(arr: [Int]) -> [Int] {
        if arr.count <= 1 {return arr}
        var list = arr;
        heapSize = arr.count
          //1、构建大顶堆
        for i in (0..<heapSize>>1).reversed() {
            siftDown(arr: &list, index: i);
        }
        //2、首尾元素交换，并重新处理首元素的位置。此时二叉堆元素数量-1
        while(heapSize > 1) {
            heapSize -= 1;
            list.swapAt(0, heapSize) // 交换二叉堆首尾元素，目的是不需要额外空间
            siftDown(arr: &list, index: 0);
        }
        return list
    }
    
    //调整大顶堆（仅是调整过程，建立在大顶堆以构建的基础上）
    static func siftDown(arr : inout [Int], index : Int){
        var tempIndex = index;
        
        let temp = arr[tempIndex];
        let half = heapSize >> 1
      
        while tempIndex < half {
            var childIndex = (tempIndex << 1)+1
            var child = arr[childIndex]
            
            let rightIndex = childIndex + 1
            
            if rightIndex < heapSize && arr[rightIndex] > child {
                
                child = arr[rightIndex];
                childIndex = rightIndex;
            }
            
            if temp > child { break }
            
            arr[tempIndex] = child;
            tempIndex = childIndex
        }
        arr[tempIndex] = temp
    }
}

插入排序

将数据分为两部分，即已排序部分，和未排序部分。逐个将未排序的的元素，插入到已排序的元素中。

逆序对：数组中从前往后的，大小与目的顺序相反的一对元素组成一个逆序对

复杂度：最好O(n)，最坏，平均复杂度O(n^2), 空间复杂度O(1)。逆序对越多，时间复杂度越高

稳定性：稳定

static func sort(arr: [Int]) -> [Int] {
  if arr.count < 2 {return arr}
  var list = arr
  for i in 1..<list.count {
    var index = i
    while index > 0 && list[index] < list[index - 1]{
      list.swapAt(index, index - 1)
      index -= 1
    }
  }
  return list
}

优化1：将交换转为挪动

1. 备份待插入元素temp
2. 头部有序数据中比temp大的，往右边挪动一个位置
3. 将temp插入到最终合适的位置

static func sort(arr: [Int]) -> [Int] {
  if arr.count < 2 {return arr}
  var list = arr
  for i in 1..<list.count {
    var index = i
    let temp = list[index];
    while index > 0 && temp < list[index - 1]{
      list[index] = list[index - 1]
      index -= 1
    }
    list[index] = temp
  }
  return list
}

优化2：二分查找

class InsertionSort2: ArraySort {
    
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 {return arr}
        var list = arr
        for i in 1..<list.count {
            let dest = InsertionSort2.search(arr: list, index: i)
            InsertionSort2.insert(arr: &list, source: i, dest: dest)
        }
        return list
    }
    
    static func insert(arr: inout [Int], source: Int, dest: Int) {
        
        if dest == source { return }
        let temp = arr[source];
        for i in ((dest+1)...source).reversed() {
            arr[i] = arr[i - 1];
        }
        arr[dest] = temp
    }
 
    static func search(arr: [Int], index: Int) -> Int {
        var begin = 0
        var end = index
        
        while(begin < end) {
            let mid = (begin + end) >> 1
            if (arr[mid] > arr[index]) {
                end = mid
            } else {
                begin = mid + 1
            }
        }
        return begin
    }
}

归并排序

递归将当前序列分割成两个子序列，直到不能被分割位置。然后将子序列合并成一个有序的序列

复杂度：最好，最坏，平均复杂度O(nlogn), 空间复杂度O(n/2 + logn)=O(n)。n/2是临时存放左侧数组，logn是因为递归调用

稳定性：稳定

class MergeSort: ArraySort {
    
    static var tempList: [Int] = []
    
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 {return arr}
        var list = arr
        
        MergeSort.divide(arr: &list, begin: 0, end: list.count)
        
        return list
    }
    
    static func divide(arr: inout [Int], begin: Int, end: Int) {
        
        if end - begin < 2 { return }
        let mid = (begin + end) >> 1
        divide(arr: &arr, begin: begin, end: mid)
        divide(arr: &arr, begin: mid, end: end)
        
        MergeSort.merge(arr: &arr, begin: begin, mid: mid, end: end)
    }
    
    static func merge(arr: inout [Int], begin: Int, mid: Int, end: Int) {
        var li = 0
        let le = mid - begin
        var ri = mid
        let re = end
        var ai = begin
        
        MergeSort.tempList = []
        for i in li..<le {
            MergeSort.tempList.append(arr[begin + i]) 
        }
        
        while(li < le) {
            if ri < re && arr[ri] < arr[li] {
                arr[ai] = arr[ri]
                ai += 1
                ri += 1
            }else {
                arr[ai] = MergeSort.tempList[li]
                ai += 1
                li += 1
            }
        }
    }
}

快速排序

选择轴点元素pivot，利用pivot将序列分两个子序列，对子序列递归以上操作

复杂度：最好，平均复杂度O(nlogn), 最坏O(n^2)，空间复杂度O(logn)。logn是因为递归调用

稳定性：不稳定

判断轴点元素与序列中元素大小时，用 < 或 > ，不包含=的意义：避免大小相等的元素过多，导致子序列分配不均匀，出现最坏时间复杂度

与归并排序对比，表面看时间复杂度比归并排序更高，但实际上是比归并排序快的。归并排序是每个元素都要一直参与合并(2-4-6-8)。快排每次递归都能够确定一个元素的位置，相当于数据规模一直在减少

可以通过随机数的方式减少最坏情况出现的几率。可以每次在区间中随机选择一个元素左边元素交换位置

class QuickSort: ArraySort {
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        quckSort(arr: &list, left: 0, right: arr.count)
        return list
    }
    
    static func quckSort(arr: inout [Int], left: Int, right: Int) {
        
        if right - left < 2 { return } // right - left = 要排序区间的长度
        
        let pivot = pivotIndex(arr: &arr, left: left, right: right)
        
        quckSort(arr: &arr, left: left, right: pivot)
        quckSort(arr: &arr, left: pivot + 1, right: right)
        
    }
    
    static func pivotIndex(arr: inout [Int], left: Int, right: Int) -> Int {
        
          let random = Int.random(in: 0..<(right-left))
        (arr[left], arr[left + random]) = (arr[left + random], arr[left]) // 随机选择一个元素作为轴点元素。避免最坏时间复杂度情况出现
      
        var begin = left
        var end = right
        
        let temp = arr[begin];
        end -= 1 // 最后一个元素index需要-1
        
        while begin < end {
            
            while begin < end {
                if temp < arr[end] {
                    end -= 1
                }else {
                    arr[begin] = arr[end];
                    begin += 1
                    break
                }
            }
            
            while begin < end {
                if temp > arr[begin] {
                    begin += 1
                }else {
                    arr[end] = arr[begin];
                    end -= 1
                    break
                }
            }
        }
        arr[begin] = temp
        return begin
    }
}

希尔排序

希尔排序将序列看做矩阵，分成n列，将每列进行排序。n逐渐减少，当n为1时，整个序列有序

步长序列：由大到小的n的值的组合。希尔给出的步长序列为 n/2^k。不同的步长序列，执行效率不同

在步长逐渐减少的过程中，逆序对数量也在逐渐减少，可以理解为插入排序的改进版

class ShellSort: ArraySort {
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        // 步长随便写的
        let stepList = sedgewichStepSequence(arr: &list);
        
        ArrayPrint.printArr(arr: stepList)
        
        for i in stepList {
            shellSort(arr: &list, step: i);
        }
        return list;
    }
    
    static func shellSort(arr: inout [Int], step: Int) {
        // col 列，对每列进行排序
        for col in 0..<step {
            // 每个元素坐标为，col(列index) + step(步长) * 行数 index
            // col + step 即为该列下一行对应的元素
            for begin in stride(from: col + step, to: arr.count, by: step) {
                var cur = begin;
                // 当前cur位置元素,与上一行的元素大小对比
                // 小于前面的就移动，大于前面的结束
                // 逐个往前插入，类似于插入排序
                while cur > col && arr[cur] < arr[cur - step] {
                    (arr[cur], arr[cur - step]) = (arr[cur - step], arr[cur])
                    cur -= step;
                }
                
            }
        }
    }

    // 目前最好的的步长序列，有robert sedgewick提出
    // 最坏时间复杂度O(n^(4/3))
    static func sedgewichStepSequence(arr: inout [Int]) -> [Int] {
        var stepList: [Int] = []
        var k = 0, step = 0
        while(true) {
            if(k % 2 == 0) {
                let pow = Int(truncating: pow(2, k>>1) as NSNumber)
                step = 1+9*(pow*pow - pow)
            }else {
                let pow1 = Int(truncating: pow(2,(k-1)>>1) as NSNumber)
                let pow2 = Int(truncating: pow(2,(k+1)>>1) as NSNumber)
                step = 1+8*pow1*pow2 - 6*pow2
            }
            if step >= arr.count {break}
            stepList.insert(step, at: 0)
            k+=1;
        }
        return stepList
    }
}

希尔给出的步长序列计算

static func shellStepSequence(arr: [Int]) -> [Int]{
        var stepList: [Int] = []
        var step = arr.count
        var temp = step >> 1
        while temp > 0 {
            step = temp;
            temp = step >> 1
            stepList.append(step);
        }
        return stepList
    }

计数排序

复杂度：最好， 最坏, 平均复杂度O(n+k)，空间复杂度O(n+k)。k为整数取值范围

稳定性：取决于代码中counts[i] += counts[i-1]优化部分。看具体需求，稳定的话需要额外O(n+k)时间复杂度，额外的O(n)空间

如果对对象进行排序，对象需要有可以用于排序的整数类型。如班级学生根据年龄排序

class CountSort: ArraySort {
    
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        
        countSort(arr: &list)
        
        return list;
    }
    
    static func countSort(arr: inout [Int]) {
        
        // 找出最大值，最小值。
        /**
         用来存储的数组区间可以选择 min -> max区间
         作用：
         - 可以对负数进行排序
         - 可以尽可能地降低空间复杂度
         */
        var max = arr[0];
        var min = arr[0];
        for value in arr {
            if value > max {
                max = value
            }
            if value < min {
                min = value
            }
        }
        
        // 将所有元素加入counts计数表中
        var counts:[Int] = [Int].init(repeating: 0, count: max - min + 1)
        for i in 0..<arr.count {
            counts[arr[i] - min] += 1;
        }
        
        // 每个元素位置存储数据 = 该元素出现次数+比该元素小的所有元素出现次数
        /**
         目的：将不稳定的排序变为稳定排序
         原理：统计完数据后，倒序遍历原数组，可以确定每个元素的具体位置。
         **/
        for i in 1..<counts.count {
            counts[i] += counts[i-1]
        }
        
        // 临时数组，保存结果
        // 每个位置，每取出一个元素，该位置计数-1。
        // 有了前部分优化后，位置计数-1即为当前元素所在位置
        var output:[Int] = [Int].init(repeating: 0, count: arr.count)
        for i in (0..<arr.count).reversed() {
            counts[arr[i] - min] -= 1;
            output[counts[arr[i] - min]] = arr[i]
        }
        
        // 结果数据依次存回原数组
        for i in 0..<arr.count {
            arr[i] = output[i]
        }
    }
}

基数排序

依次对个位数，十位数...进行排序。一定要从低位到高位才能保证最后是有序的

复杂度：最好， 最坏, 平均复杂度O(n+k)，空间复杂度O(n+k)。k为整数取值范围

稳定性：稳定

class RadixSort: ArraySort {
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        
        radixSort(arr: &list)
        
        return list;
    }
    
    static func radixSort(arr: inout [Int]) {
        var max = arr[0];
        for i in 0..<arr.count {
            if arr[i] > max {
                max = arr[i]
            }
        }
        
        var outPuts = [Int].init(repeating: 0, count: arr.count)
        var counts = [Int].init(repeating: 0, count: 10);
        
        var divider = 1
        while divider <= max {
            
            countingSort(arr: &arr, divider: divider, output: &outPuts, count: &counts)
            divider *= 10
        }
    }
    
    static func countingSort(arr: inout [Int], divider: Int, output: inout [Int], count: inout [Int]) {
        for i in 0..<count.count {
            count[i] = 0
        }
        for i in 0..<arr.count {
            count[arr[i]/divider%10] += 1
        }
        for i in 1..<count.count {
            count[i] += count[i-1]
        }
        for i in (0..<arr.count).reversed() {
            count[arr[i]/divider%10] -= 1
            output[count[arr[i]/divider%10]] = arr[i]
        }
        for i in 0..<arr.count {
            arr[i] = output[i]
        }
    }
}

基数排序方法2

依次根据个位数大小分别加入十个桶，然后再从0-10桶中依次取出各元素。再根据十位数大小重复前面操作

复杂度：最好， 最坏, 平均复杂度O(dn)，空间复杂度O(kn+k)。d是最大值位数，k是进制

稳定性：稳定

class RadixSort1: ArraySort {
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        
        radixSort(arr: &list)
        
        return list;
    }
    
    static func radixSort(arr: inout [Int]) {
        var max = arr[0];
        for i in 0..<arr.count {
            if arr[i] > max {
                max = arr[i]
            }
        }
        
        // 创建十个桶, 每个桶内可以存储最多arr.count个数据
        var buckets = [[Int]].init(repeating: [Int].init(repeating: 0, count: arr.count), count: 10)
        // 每个桶的元素数量
        var bucketSizes = [Int].init(repeating: 0, count: buckets.count)
        
        var divider = 1
        while divider <= max {
            
            for i in 0..<arr.count {
                let no = arr[i] / divider % 10
                buckets[no][bucketSizes[no]] = arr[i]
                bucketSizes[no] += 1
            }
            
            var index = 0
            for i in 0..<buckets.count {
                for j in 0..<bucketSizes[i] {
                    arr[index] = buckets[i][j]
                    index += 1
                }
                bucketSizes[i] = 0
            }
    
            divider *= 10
        }
    }

}

桶排序

执行步骤：

1. 创建一定数量的桶
2. 按照一定的规则，将序列中的元素均匀分配到对应的桶。
3. 对每个桶进行排序
4. 将所有的非空桶的元素合并成有序数组

分桶规则：需要根据数据特点来划分，下面代码划分方式为(arr[i] * arr.count)/100

复杂度：空间复杂度O(n+m),m为桶数量。时间复杂度O(n+k),k为nlogn-nlogm

稳定性：稳定

// 桶排序需要对数据根据特征划分桶 测试数据：[33, 51, 27, 81, 43, 39, 38, 72]
class BucketSort: ArraySort {
    static func sort(arr: [Int]) -> [Int] {
        if arr.count < 2 { return arr }
        var list = arr
        
        bucketSort(arr: &list)
        
        return list;
    }
    
    static func bucketSort(arr: inout [Int]) {
        
        var buckets = [[Int]].init(repeating: [], count: arr.count)
        
        for i in 0..<arr.count {
            
            let bucketIndex = (arr[i] * arr.count)/100
            var bucket = buckets[bucketIndex]
            bucket.append(arr[i])
            buckets[bucketIndex] = bucket
        }
        
        var index = 0
        for i in 0..<buckets.count {
            if buckets.count == 0 { continue }
            let blist = QuickSort.sort(arr: buckets[i])
            for n in blist {
                arr[index] = n
                index += 1
            }
        }
    }
}