算法

排序算法

不稳定排序

插入排序

1. 给出未排序的数组。
2. 在数组中选一个数字，选哪个数字不重要，选第一个数字是最简单的。
3. 将这个数字插入到一个新的数组中。
4. 在未排序数组中选择下一个数字，将它插入到新数组中，将新数组中的两个数字进行排序。
5. 继续将剩下的数字放入已排序数组中，直到未排序数组中的数字被全被取出，这时新数组就是一个有序数组了。

算法复杂度：O(n^2)

方法一：交换相邻的两个数

[ 3, 5, 8, 4 | 6 ]
        <-->
        swap
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     swap

func insertionSort(_ arr: [Int]) -> [Int] {
    var newArr = arr
    for x in 1 ..< newArr.count {
        
        var y = x
        while y > 0 && newArr[y] < newArr[y - 1] {
            swap(&newArr[y], &newArr[y-1])
            y -= 1
        }
    }
    
    return newArr
}

将方法抽象成泛型类型的数组

方法二：使用temp暂时存储待比较的数

[ 3, 5, 8, 4 | 6 ]   remember 4
           *

[ 3, 5, 8, 8 | 6 ]   shift 8 to the right
        --->
        
[ 3, 5, 5, 8 | 6 ]   shift 5 to the right
     --->
     
[ 3, 4, 5, 8 | 6 ]   copy 4 into place
     *

func insertionSort<T>(_ arr: [T], _ compareBlock:(T, T) -> Bool) -> [T] {
    var newArr = arr
    for x in 1 ..< newArr.count {
        
        var y = x
        let temp = newArr[y]
        while y > 0 && compareBlock(temp, newArr[y - 1]) {
            
            newArr[y] = newArr[y - 1]
            y -= 1
        }
        newArr[y] = temp
    }
    
    return newArr
}

let a = [10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26]

print(insertionSort(a, <)) 

选择排序

从0开始，找到数组中最小的元素放到index为0的元素上。 从1开始，找到数组中最小的元素放到index为1的元素上。 ...

时间复杂度：O(n^2)

func selectionSort(_ arr: [Int]) -> [Int] {
    
    guard arr.count > 1 else {
        return arr
    }
    var a = arr
    
    for x in 0 ..< a.count - 1 {
        
        var lowest = x
        for y in x + 1 ..< a.count {
            
            if (a[lowest] > a[y])
            {
                lowest = y
            }
        }
        
        if x != lowest {
            swap(&a[x], &a[lowest])
        }
    }
    
    return a
}

shell 排序/ 希尔排序

核心思想是：待排序列有n个元素，先取一个小于n的整数h1作为第一个增量，把待排序列以间隔h1分成若干子序列，子序列内使用插入排序；然后取第二个增量h2(< h1)，重复上述的划分和排序，直至所取的增量hl = 1 (h1 > h2 > ... > hl)。

[64, 20, 50, 33, 72, 10, 23, -1, 4]

长度除2 做为第一个增量
n = floor(9/2) = 4
将数组分割成4个子数组，依次对每个数组进行插入排序
sublist 0:  [ 64, xx, xx, xx, 72, xx, xx, xx, 4  ]
sublist 1:  [ xx, 20, xx, xx, xx, 10, xx, xx, xx ]
sublist 2:  [ xx, xx, 50, xx, xx, xx, 23, xx, xx ]
sublist 3:  [ xx, xx, xx, 33, xx, xx, xx, -1, xx ]

排序后得到
sublist 0:  [ 4, xx, xx, xx, 64, xx, xx, xx, 72 ]
sublist 1:  [ xx, 10, xx, xx, xx, 20, xx, xx, xx ]
sublist 2:  [ xx, xx, 23, xx, xx, xx, 50, xx, xx ]
sublist 3:  [ xx, xx, xx, -1, xx, xx, xx, 33, xx ]

[ 4, 10, 23, -1, 64, 20, 50, 33, 72 ]
第二次以n = 4/2 = 2作为增量分割数组
得到2个数组
sublist 0:  [  4, xx, 23, xx, 64, xx, 50, xx, 72 ]
sublist 1:  [ xx, 10, xx, -1, xx, 20, xx, 33, xx ]
进行插入排序得到
[ 4, -1, 23, 10, 50, 20, 64, 33, 72 ]

第三次 n = 2/2 = 1
意味着需要将上面得到的数组进行插入排序

func shellSort(_ list: inout [Int]) {
    
    guard list.count > 1 else {
        return
    }
    var sublistCount = list.count / 2
    
    while sublistCount > 0 {
        
        for index in 0 ..< list.count {
            
            var temp = index
            
            while temp < list.count {
                
                if list[index] > list[temp] {
                    swap(&list[index], &list[temp])
                }
                
                temp += sublistCount
            }
            
        }
        
        sublistCount = sublistCount/2
    }
    
    return
}