通过算法了解Swift 3—插入排序
Insertion sort
插入排序是最基础的排序算法之一。它最核心的思想,由以下几条构成。当我们要对一个值为
简单来说,就是不断通过比对,移动待排序元素的位置。直到待排序元素和之前已排序“子序列”全部元素都比对完之后: [5,1] ^ 6 > 5 == true [5,1] <---> swap [6,1] 新形成的序列就已经是排序好的了。(当然,这里也有一个潜台词,就是如果和子序列中第一个元素比对之后不需要移动,则新添加进来的元素就应该直接添加到子序列末尾); 反复3的操作,当读完所有待排序的元素之后,整个序列就排序完成了。
实现如何使用?在实现之前,我们要先考虑下开发者会如何使用这个算法,例如这样: let a: Array<Int> = [1,6] insertionSortOf(a) 或者,我们允许用户指定一个排序方法 let a: Array<Int> = [1,6] insertionSortOf(a,byCriteria: >) // [6,1] 然后,我们还应该允许对包含任何“可比较”元素的Array进行排序。于是, 如何按Swift 3的方式声明typealias CRITERIA<T> = (T,T) -> Bool func insertionSortOf<T: Comparable>( _ coll: Array<T>,byCriteria: CRITERIA<T> = { $0 < $1 }) ->Array<T> 在这个声明里,有以下和Swift 3相关的说明: 首先,我们使用了SE-0048中的新特性,允许在 其次,在方法的命名上,我们参考了SE-0023 API设计指南中的要求:
因此,我们把“表示要排序的集合”使用的介词“of”,从第一个参数名,放到了函数名中。 第三,在Swift 3里,根据SE-0046中的提议,函数的第一个参数不再默认省略label,它将和其他参数一样拥有默认的label行为。因此,如果我们要省略label,必须在参数名前强制使用_ 第四,根据SE-0023 API设计指南中的要求:
实现insertionSort按照一开始我们在算法思路中的描述,在 首先,只有一个元素的数组是无需排序的,我们直接返回就好: func insertionSortOf<T: Comparable>( _ coll: Array<T>,byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> { // 1. An array with a single element is ordered guard coll.count > 1 else { return coll } } 其次,复制一份参数数组,用于在函数内部进行排序: func insertionSortOf<T: Comparable>( _ coll: Array<T>,byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> { //: #### 1. An array with a single element is ordered guard coll.count > 1 else { return coll } var result = coll } 第三,我们从数组中第二个元素开始,通过逐个比对,来不断形成已排序好的子数组: for x in 1 ..< coll.count { var = x let key = result[y] print("Get: (key)") // 2. If the key needs to swap in the previous ordered sub array while y > 0 && byCriteria(key,result[y - 1]) { print("-----------------------------") print("Remove: (result[y]) at pos: (y)") print("Insert: (key) at pos: (y - 1)") print("-----------------------------") // 3. Swap the value // The new Swift 3 API: // remove(at:) replaces removeAtIndex // You can also use swap(:) instead of remove and insert. result.remove(at: y) result.insert(key,at: y - 1) y -= 1 } } 最后,数组中所有的元素都遍历之后,整个数组就完成排序了,我们直接把排序后的数组返回: func insertionSortOf<T: Comparable>( _ coll: Array<T>,byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> { guard coll.count > 1 else { return coll } var result = coll for x in 1 ..< coll.count { var y = x let key = result[y] print("Get: (key)") // 2. If the key needs to swap in the previous ordered sub array while y > 0 && byCriteria(key,result[y - 1]) { print("-----------------------------") print("Remove: (result[y]) at pos: (y)") print("Insert: (key) at pos: (y - 1)") print("-----------------------------") // 3. Swap the value // Notice the new Swift 3 API: remove(at:) replaces removeAtIndex // You can also use swap(:) instead of remove and insert result.remove(at: y) result.insert(key,at: y - 1) y -= 1 } } // 4. Return the sorted array return result } 测试用一开始我们设计的使用方法来测试 let a: Array<Int> = [1,6] insertionSortOf(a) 由于默认就是从小到大排序,并且,原始数组本身就是已经排序的,因此,我们可以在控制台看到下面的结果:
如果我们传递一个自定义的比较规则,例如从大到小排序: let a: Array<Int> = [1,byCriteria: >) 就可以在控制台看到这样的结果:
数字5经历了一次交换,数字6经历了两次交换。 Have a try?不用交换元素的插入排序方法除了使用
不同的实现方法之间的性能差异有多大呢?
当移动大量元素时,这些算法之间的差异有多大呢?自己试验一下吧,欢迎大家把实验的结果贴到泊学视频下面的泊学Disqus论坛里。 :-) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |