Jonathan's Studio

算法基础（三）排序和搜索

实习准备
字数统计: 4.8k阅读时长: 20 min
2020/08/29

算法基础（三）排序和搜索

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
class Solution<T: Comparable> {
    
    /**
        直接插入排序（插入排序的一种）  时间复杂度O(n~n2) 空间复杂度O(1)  稳定
     */
    func insertSort(_ array: [T]) -> [T] {
        var array = array
        guard !array.isEmpty && array.count > 1 else {
            return array
        }
        for i in 1...array.count-1 {
            for j in (0..<i).reversed() {
                if array[j] > array[j+1] {
                    let temp = array[j+1]
                    array[j+1] = array[j]
                    array[j] = temp
                }
            }
        }
        return array
    }
    
    /**
        希尔排序（插入排序的一种）  时间复杂度(n^(1.3~2)) 空间复杂度O(1)  不稳定
     */
    func shellSort(_ array: [T]) -> [T] {
        var array = array
        //获取增量
        var gap = array.count/2
        while gap > 0 {
            for i in 0..<array.count {
                var j = i + gap
                while j >= gap && j < array.count {
                    if array[j-gap] > array[j] {
                        array.swapAt(j-gap, j)
                        j = j - gap
                    } else {
                        break
                    }
                }
            }
            //增量减半
            gap /= 2
        }
        return array
    }
    
    /**
        简单选择排序  时间复杂度O(n2) 空间复杂度O(1)  不稳定
     */
    func selectSort(_ array: [T]) -> [T] {
        guard array.count > 1 else {
            return array
        }
        var array = array
        for index in 0..<array.count-1 {
            var lowest = index
            for i in index+1..<array.count {
                if array[i] < array[lowest] {
                    lowest = i
                }
            }
            if index != lowest {
                array.swapAt(index, lowest)
            }
        }
        return array
    }
    
    /**
        堆排序（选择排序的一种） 时间复杂度为O(nlog2n) 空间复杂度O(1) 不稳定
     */
    func heapSort(_ array: [T]) -> [T] {
        guard array.count > 1 else {
            return array
        }
        var array = array
        //1.构建大顶堆
        for i in (0...(array.count/2-1)).reversed(){
            //从第一个非叶子结点从下至上，从右至左调整结构
            self.adjustHeap(array: &array, i: i, length: array.count)
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for j in  (1...(array.count-1)).reversed(){
            array.swapAt(0, j)//将堆顶元素与末尾元素进行交换
            self.adjustHeap(array: &array, i: 0, length: j)//重新对堆进行调整
        }
        return array
    }
    
    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     */
    private func adjustHeap(array: inout [T], i: Int, length: Int) {
        var i = i
        let temp = array[i]//先取出当前元素i
        var k = 2*i+1//左孩子下标
        while k<length {//从i结点的左子结点开始，也就是2i+1处开始
            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值放到最终的位置
    }

    /**
        冒泡排序（交换排序的一种）时间复杂度O(n~n2) 空间复杂度O(1) 稳定
     */
    func bubbleSort(_ array: [T]) -> [T] {
        var array = array
        for i in (1...array.count-1).reversed() {
            for j in 1...i {
                if array[j-1] > array[j] {
                    array.swapAt(j-1, j)
                }
            }
        }
        return array
    }
    
    /**
        快速排序（选择排序的一种）时间复杂度O(nlog2n~n2)  时间复杂度O(nlog2n)  不稳定
     */
    func quickSort(_ array: [T]) -> [T] {
        var array = array
        helper_quickSort(&array, low: 1, high: array.count)
        return array
    }
    
    /**
        递归法将数组分区
     */
    private func helper_quickSort(_ array: inout [T], low: Int, high: Int) {
        if low<high {
            let pivotloc = partition(&array, low: low, high: high)
            helper_quickSort(&array, low: low, high: pivotloc-1)//左
            helper_quickSort(&array, low: pivotloc+1, high: high)//右
        }
    }
    
    /**
        对子数组进行排序
     */
    private func partition(_ array: inout [T], low: Int, high: Int) -> Int {
        var hight = high
        var low = low
        let pivotkey = array[low-1]//子数组第一个为枢轴
        while low<hight {
            while (low<hight && array[hight-1]>=pivotkey) {hight = hight-1}//高位向前扫描
            if low<hight {array[low-1] = array[hight-1]}//小的挪到地位
            while (low<hight && array[low-1]<=pivotkey) {low = low+1}//地位向前扫描
            if low<hight {array[hight-1] = array[low-1]}//大的挪到高位
        }
        array[low-1] = pivotkey//还原枢轴
        return low
    }
    
    /**
        归并排序  时间复杂度O(nlog2n) 空间复杂度O(1) 稳定
     */
    func mergeSort(_ array: [T]) -> [T] {
        guard !array.isEmpty else {
            return array
        }
        var helperArray: [T] = Array.init(repeating: array.first!, count: array.count)
        var array = array
        helper_mergeSort(&array, helperArray: &helperArray, low: 0, high: array.count - 1)
        return array
    }

    /**
        递归拆分然后合并
     */
    private func helper_mergeSort(_ array: inout [T], helperArray: inout [T], low: Int, high: Int) {
        guard low<high else {
            return
        }
        let middle = (high-low)/2+low
        helper_mergeSort(&array, helperArray: &helperArray, low: low, high: middle)
        helper_mergeSort(&array, helperArray: &helperArray, low: middle+1, high: high)
        merge(&array, helperArray: &helperArray, low: low, middle: middle, high: high)
    }

    /**
        合并过程
     */
    private func merge(_ array: inout [T], helperArray: inout [T], low: Int, middle: Int, high: Int) {
        for i in low...high {
            helperArray[i] = array[i]
        }//复制操作
        var helperLeft = low,
        helperRight = middle+1,
        current = low
        while helperLeft <= middle && helperRight <= high {
            if helperArray[helperLeft] <= helperArray[helperRight] {
                array[current] = helperArray[helperLeft]
                helperLeft += 1
            } else {
                array[current] = helperArray[helperRight]
                helperRight += 1
            }//两组从头开始比较大小并赋值到原数组
            current += 1
        }
        guard middle-helperLeft >= 0 else {
            return
        }//将剩下的数归并到后面
        for i in 0...middle-helperLeft {
            array[current+i] = helperArray[helperLeft+i]
        }
    }
    
    /**
        基数排序   时间复杂度O(d(n+rd)~d(r+n))   空间复杂度O(rd+n)  d为长度，r为关键字的基数   稳定
     */
    static func radixSort(_ array: [Int]) -> [Int] {
        guard !array.isEmpty else {
            return array
        }
        var array = array
        var exp = 1
        var temp = [Int].init(repeating: 0, count: array.count)//临时数组
        var max = array.first!
        for value in array {
            if max < value {
                max = value
            }
        }//找出最大数确定最大位数
        while max/exp > 0 {
            var bucket = [Int].init(repeating: 0, count: 10)//建立桶
            for i in 0...array.count-1 {
                bucket[(array[i]/exp)%10] += 1//exp位的各个数的统计
            }
            for i in 1...9 {
                bucket[i] += bucket[i-1]
            }
            for i in (0...array.count-1).reversed() {
                bucket[(array[i]/exp)%10] -= 1
                temp[bucket[(array[i]/exp)%10]] = array[i]
            }//获得exp位的排序
            for i in 0...array.count-1 {
                array[i] = temp[i]
            }//temp赋值到原数组
            exp = exp*10
        }
        return array
    }
    
}


Solution<Int>().insertSort([7,798,44,154,22,77,112,47,1])
Solution<Int>().insertSort([89,4])
Solution<Int>().shellSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>().selectSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>().heapSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>().bubbleSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>().quickSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>().mergeSort([7,798,44,154,22,77,112,47,1,12])
Solution<Int>.radixSort([7,798,44,154,22,77,112,47,1,12])


搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
    顺序查找：顺序查找适合于存储结构为顺序存储或链接存储的线性表，时间复杂度为O(n)
 */

/**
    二分查找：元素必须是有序的，如果是无序的则要先进行排序操作。时间复杂度O(log2n)
    也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
    注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
 */
func binarySearch<T: Comparable>(_ value: T, from array: [T]) -> Int? {
    var low = 0
    var high = array.count-1
    var mid = 0
    while low <= high {
        mid = (low+high)/2
        if array[mid] == value { return mid }
        if array[mid] > value {
            high = mid-1
        } else {
            low = mid+1
        }
    }
    return nil
}

/**
    插值查找：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。查找成功或者失败的时间复杂度均为O(log2(log2n))。
    注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
 */
func insertionSearch(_ value: Int, from array: [Int]) -> Int? {
    return _insertionSearch(value, from: array, low: 0, high: array.count-1)
}

private func _insertionSearch(_ value: Int, from array: [Int], low: Int, high: Int) -> Int? {
    guard low < high else {
        if low == high && array[low] == value {
            return low
        }
        return nil
    }
    let mid = low+(value-array[low])/(array[high]-array[low])*(high-low)
    guard mid < array.count && array[mid] != value else {
        if mid >= array.count {
            return nil
        }
        return mid
    }
    if array[mid] > value {
        return _insertionSearch(value, from: array, low: low, high: mid-1)
    } else {
        return _insertionSearch(value, from: array, low: mid+1, high: high)
    }
}

/**
   斐波那契查找：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
*/
func fibonacciSearch(_ value: Int, from array: [Int]) -> Int? {
    guard !array.isEmpty else {
        return nil
    }
    var low = 0
    var high = array.count-1
    var fibonacciArray = [Int].init(repeating: 0, count: 20)
    fibonacciArray[1] = 1
    for i in 2...19 {
        fibonacciArray[i] = fibonacciArray[i-1]+fibonacciArray[i-2]
    }//构造一个斐波那契数组
    var k = 0
    while array.count > fibonacciArray[k]-1 {
        k += 1
    }//计算n位于斐波那契数列的位置
    var temp = [Int].init(repeating: 0, count: fibonacciArray[k]-1)
    for i in 0...array.count-1 {
        temp[i] = array[i]
    }
    for i in array.count..<fibonacciArray[k]-1 {
        temp[i] = array.last!
    }//将数组a复制到F[k]-1的长度的temp数组，剩余数用末尾填充
    while low <= high {
        let mid = low+fibonacciArray[k-1]-1
        if value < temp[mid] {
            high = mid-1
            k -= 1
        } else if value > temp[mid] {
            low = mid+1
            k -= 2
        } else {
            if mid < array.count-1 {
                return mid
            } else {
                return array.count-1
            }
        }
    }
    return nil
}


/**
    树表查找
    最简单的树表查找算法——二叉树查找算法。它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡
        基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
 
        二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
        　　1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
        　　2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
        　　  3）任意节点的左、右子树也分别为二叉查找树。
       二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
 　  基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

 */

/**
    树表查找
    平衡查找树之2-3查找树（2-3 Tree）
    2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：
    　　  1）要么为空，要么：
    　　2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。
    　　3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
    2-3查找树的性质：
    　　  1）如果中序遍历2-3查找树，就可以得到排好序的序列；
    　　2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）
 　　　　
    在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
    在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
 */

/**
    树表查找
    平衡查找树之红黑树（Red-Black Tree）
    　2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。
    　　基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
    红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：
        红色节点向左倾斜
        一个节点不可能有两个红色链接
        整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。
    红黑树的性质：整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。
    最坏的情况就是，红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。
 */

/**
    树表查找
    B树和B+树（B Tree/B+ Tree）
    树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
        根节点至少有两个子节点
        每个节点有M-1个key，并且以升序排列
        位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
        其它节点至少有M/2个子节点
 
    B+树是对B树的一种变形树，它与B树的差异在于：
        有k个子结点的结点必然有k个关键码；
        非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
        树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
 
    B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
    但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
 */


/**
    分块查找：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素.
    算法流程：
    　　step1 先选取各块中的最大关键字构成一个索引表；
    　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
 */

/**
    哈希查找：
    哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
 
    算法流程：
        1）用给定的哈希函数构造哈希表；
        2）根据选择的冲突处理方法解决地址冲突；
            常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。
        3）在哈希表的基础上执行哈希查找。
    哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
 　　　　
 　　　　单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。
 */

let array:[Int] = [4,5,15]
binarySearch(4, from: array)
insertionSearch(15, from: array)
fibonacciSearch(5, from: array)

原文作者：Jonathan Lu

原文链接：https://jonathanlu98.github.io/2020/08/29/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%EF%BC%88%E4%B8%89%EF%BC%89%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/

发表日期：August 29th 2020, 9:54:01 pm

更新日期：October 5th 2021, 11:34:35 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 算法基础（三）排序和搜索
    1. 1.1. 排序
    2. 1.2. 搜索
Total : 15
2022
2020
2019
iOS小记 分享 项目分享 实习准备 软件使用