点开这个连接 ☟☟☟

十大经典排序算法

以下为部分个人笔记 ✍ 可忽略

冒泡排序（Bubble Sort）

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

image.gif

代码实现

func bubbleSort (arr: inout [Int]) {
    for i in 0..<arr.count - 1 {
        for j in 0..<arr.count - 1 - i {
            if arr[j] > arr[j+1] {
                arr.swapAt(j, j+1)
            }
        }
    }
}

代码优化

增加一个标记变量flag来实现这一算法的改进，避免已经有序的情况下的无意义循环判断

func bubbleSort(sortArray: inout [Int]) {
    var flag = true
    
    for i in 0..<sortArray.count - 1 {
        guard flag else { return }
        flag = false
        
        for j in (i..<sortArray.count - 1).reversed() {
            if sortArray[j] > sortArray[j + 1] {
                let temp = sortArray[j]
                sortArray[j] = sortArray[j + 1]
                sortArray[j + 1] = temp
                flag = true
            }
        }
    }
}

简单选择排序（Simple Selection Sort）

简单选择排序法就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换。

它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。

尽管与冒泡排序同为O(n²)，但简单选择排序的性能上还是要略优于冒泡排序。

image.gif

代码实现

func selectionSort(_ list: inout [Int]) -> Void {
    for j in 0..<list.count - 1 {
        var minIndex = j
        for i in j..<list.count {
            if list[minIndex] > list[i] {
                minIndex = i
            }
        }
        list.swapAt(j, minIndex)
    }
}

func selectSort(sortArray: inout [Int]) {
    var min = 0
    
    for i in 0..<sortArray.count - 1 {
        min = i
        for j in (i + 1)..<sortArray.count {
            if sortArray[min] > sortArray[j] {
                min = j
            }
        }
        if i != min {
            let temp = sortArray[i]
            sortArray[i] = sortArray[min]
            sortArray[min] = temp
        }
    }
}

直接插入排序（Straight Insertion Sort）

直接插入排序的基本操作是将一个记录插入到已经排好的序的有序表中，从而得到一个新的、记录数增1的有序表。

同样的O(n²)时间复杂度，直接插入排序法比冒泡排序和简单选择排序的性能要好一些。

image.gif

代码实现

for i in 1..<arr.endIndex {
    let temp = arr[i]
    for j in (0..<i).reversed() {
        if arr[j] > temp {
            arr.swapAt(j, j+1)
        }
    }
}

func insertSort(sortArray: inout [Int]) {
    
    for i in 1..<sortArray.count {
        if sortArray[i] < sortArray[i - 1] {
            let temp = sortArray[i]
            var j = i - 1
            
            while j >= 0, sortArray[j] > temp {
                sortArray[j + 1] = sortArray[j]
                j -= 1
            }
            
            sortArray[j + 1] = temp
        }
    }
}

希尔排序（Shell Sort）

希尔排序是D.L.Shell于1959年提出的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n²)，希尔排序算法是突破这个时间复杂度的第一批算法之一。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

增量序列的最后一个增量值必须等于1才行。由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。

image.gif

代码实现

func shellSort(sortArray: inout [Int]) {
    var i = sortArray.count
    while i > 0 {
        for j in i..<sortArray.count {
            var m = j - i
            while m >= 0 {
                if sortArray[m] > sortArray[m + i] {
                    let temp = sortArray[m]
                    sortArray[m] = sortArray[m + i]
                    sortArray[m + i] = temp
                }
                m -= i
            }
        }
        i /= 2
    }
}

堆排序（Heap Sort）

堆是具有下列性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序就是利用堆进行排序的方法。

算法描述

将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

image.gif

代码实现

func heapSort(sortArray: inout [Int]) {
    
    //构建大顶堆
    for i in stride(from: (sortArray.count / 2 - 1), through: 0, by: -1) {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(sortArray: &sortArray, i: i, length: sortArray.count)
    }
    
    //调整堆结构+交换堆顶元素与末尾元素
    for i in stride(from: (sortArray.count - 1), to: 0, by: -1) {
        swap(sortArray: &sortArray, a: 0, b: i)//将堆顶元素与末尾元素进行交换
        adjustHeap(sortArray: &sortArray, i: 0, length: i)//重新对堆进行调整
    }
}

func adjustHeap(sortArray: inout [Int], i: Int, length: Int) {
    let temp = sortArray[i]//先取出当前元素i
    var j = i * 2 + 1//从i结点的左子结点开始，也就是2i+1处开始
    var i = i
    
    while j < length {
        if j + 1 < length && sortArray[j] < sortArray[j + 1] {//如果左子结点小于右子结点，k指向右子结点
            j += 1
        }
        if sortArray[j] > temp {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            sortArray[i] = sortArray[j]
            i = j
        } else {
            break
        }
        j = j * 2 + 1
    }
    sortArray[i] = temp//将temp值放到最终的位置
}

func swap(sortArray: inout [Int], a: Int, b: Int) {
    let temp = sortArray[a]
    sortArray[a] = sortArray[b]
    sortArray[b] = temp
}

归并排序（Merging Sort）

归并排序就是利用归并的思想实现的排序方法。

它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（x表示不小于x的最小整数）个长度为2或者1的有序子序列；再两两归并，......，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

image.gif

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

image.gif