排序就是把一组对象按照指定的条件(升序或倒序)重新排列的过程。
01 - 思考 开始前不妨思考以下几个问题:
想一想什么是排序呢?
想一想怎么描述排序的效率?时间复杂度,空间复杂度
02 - 常见排序 本文中的代码使用的 Swift,默认排序是升序排序,其他的大同小异,这里不一一赘述了。
选择排序 排序方法:
遍历过程为从一个元素到倒数第二个元素。
在遍历中,要执行的操作是每次从当前元素之后的序列中,寻找最小元素,然后与当前元素交换,然后再处理下一个元素。
1 2 3 4 5 6 7 8 9 10 11 func selection (_ numbers: inout [Int]) { guard numbers.count > 1 else { return } for indexI in 0 ..<numbers.count -1 { var minIndex = indexI for indexJ in minIndex+1 ..<numbers.count { minIndex = numbers[indexJ] < numbers[minIndex] ? indexJ : minIndex } numbers.swapAt(indexI, minIndex) } }
冒泡排序 排序方法:
遍历过程为多趟逐次递减遍历,即第一次遍历到最后一个元素,第二次为倒数第二个元素,直到第一个元素为止。
在每次遍历中,要执行的操作是,依次比较当前元素和下一个元素的值,不满足条件则交换。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 func bubble (_ numbers: inout [Int]) { guard numbers.count > 1 else { return } var total = numbers.count while total > 0 { var changed = false var index = 0 while index < numbers.count -1 { if numbers[index] > numbers[index+1 ] { numbers.swapAt(index, index+1 ) changed = true } index += 1 } if !changed { break } total -= 1 } }
插入排序 排序方法:
遍历过程为从第二个元素遍历到最后一个元素。
遍历中执行的操作是从当前元素之前的队列中,找到要插入的位置后,将当前元素插入到序列中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func insert (_ numbers: inout [Int], gap: Int = 1 ) { guard numbers.count > 1 else { return } for g in 0 ..<gap { var i = g while i < numbers.count { var current = i while current-gap >= 0 && numbers[current-gap] > numbers[current] { numbers.swapAt(current, current-gap) current -= gap } i += gap } } }
希尔排序 希尔排序是对插入排序的改进,是一种增量递减排序。
排序方法:
首先生成一个增量递减序列,一般是 n / 2。
遍历增量递减序列种,对于每一个增量 gap,要执行的操作是,对数组中依次相距 gap 的序列进行插入排序。增量序列遍历完得到的数组就是排序后数组。
1 2 3 4 5 6 7 8 9 func shell (_ numbers: inout [Int]) { guard numbers.count > 1 else { return } var gap = numbers.count / 2 while gap != 0 { insert(&numbers, gap: gap) gap = gap / 2 } }
归并排序 排序方法:
对数组中的元素进行递归分割,直到每个序列只包含一个元素为止。
有序合并分割后的每个序列,合并后数组就是排序后的数组。
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 func merge (_ numbers: [Int]) -> [Int ] { return divide(nums) } func divide (_ numbers: [Int]) -> [Int ] { guard numbers.count > 1 else { return numbers } let mid = (0 +numbers.count -1 )/2 let leftNumbers = divide(Array (numbers[0 ...mid])) let rightNumbers = divide(Array (numbers[mid+1 ..<numbers.count ])) return join (leftNumbers, rightNumbers) } func join (_ leftNumbers: [Int], _ rightNumbers: [Int]) -> [Int ] { var result = [Int ]() var leftIndex = 0 var rightIndex = 0 while leftIndex < leftNumbers.count && rightIndex < rightNumbers.count { if leftNumbers[leftIndex] <= rightNumbers[rightIndex] { result.append(leftNumbers[leftIndex]) leftIndex += 1 } else { result.append(rightNumbers[rightIndex]) rightIndex += 1 } } if leftIndex < leftNumbers.count { result.append(contentsOf: Array (leftNumbers[leftIndex..<leftNumbers.count ])) } if rightIndex < rightNumbers.count { result.append(contentsOf: Array (rightNumbers[rightIndex..<rightNumbers.count ])) } return result }
快速排序 排序方法:
以序列中间元素为基准,将序列重组为小于中间元素,等于中间元素,大于中间元素的三个部分。
递归地对小于中间元素序列、大于中间元素序列执行操作1,直到子序列的个数等于1为止,此时得到的数组就是排序后的数组。
1 2 3 4 5 6 7 8 9 10 11 12 func quick (_ numbers: [Int]) -> [Int ] { guard numbers.count > 1 else { return numbers } let pivot = numbers[numbers.count /2 ] let less = numbers.filter { $0 < pivot } let equal = numbers.filter { $0 == pivot } let greater = numbers.filter { $0 > pivot } return quick(less) + equal + quick(greater) }
计数排序 排序方法:
生成一个下标最小为0,最大为数组中最大值,值为0的一个统计序列。
遍历数组中的元素,以元素的值为 index,增加统计序列的出现次数。
遍历统计序列,根据出现次数,生成排序后的数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 func count (_ numbers: [Int]) -> [Int ]{ guard numbers.count > 1 else { return numbers } let maxVal = numbers.max ()! var counts = Array (repeating: 0 , count : maxVal+1 ) for element in numbers { counts[element] += 1 } var result = numbers var resultIndex = 0 for (index, val) in counts.enumerated() { for _ in 0 ..<val { result[resultIndex] = index resultIndex += 1 } } return result }
基数排序 排序方法:
生成一个下标为0,最大值为9的暂存序列。
寻找数组中值最大的元素,统计其位数。
从最低位开始,循环的执行操作4,循环完成后得到的数组就是排序后的数组。
将数组中的元素,按照相应位上数值分到暂存系列中,分完再将暂存序列合并后的数组赋值给原数组。
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 func radix (_ numbers: [Int]) -> [Int ] { guard numbers.count > 1 else { return numbers } let totalDigit = getTotalDigit(numbers.max ()!) var tempts = Array (repeating: [Int ](), count : 10 ) var result = numbers for digit in 0 ..<totalDigit { tempts = Array (repeating: [Int ](), count : 10 ) for element in result { let index = getDigit(element, digit) tempts[index].append(element) } result = tempts.flatMap { $0 } } return result } func getTotalDigit (_ number: Int) -> Int { guard number > 0 else { return 1 } var length = 0 var target = 1 while number >= target { length += 1 target *= 10 } return length } func getDigit (_ number: Int, _ Index: Int) -> Int { let num1 = pow(10 , Index +1 ) let num2 = pow(10 , Index ) return number % num1 / num2 } func pow (_ x: Int, _ y: Int) -> Int { var result = 1 for _ in 0 ..<y { result *= x } return result }
桶排序 排序方法:
生成一个元素类型是数组,总个数为 n 的的空序列,序列中的每个数组可以理解为一个桶。
找出数组最大值,最小值,将它们的差除以桶的总个数得到值就是每个桶的容量。
确定每个桶允许放入元素的数值范围后,遍历数组中的元素,将元素放入到每个桶中,使桶中的元素也是有序排列。
将包含桶的序列合并成一个新的数组就是排序后的数组。
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 func bucket (_ numbers: [Int]) -> [Int ] { guard numbers.count > 0 else { return numbers} let totalBucket = 10 var buckets = Array (repeating: [Int ](), count : totalBucket) let minVal = numbers.min ()! let maxVal = numbers.max ()! for element in numbers { let bucketIndex = getBucketIndex(element, minVal, maxVal, totalBucket) addElementToBucket(&buckets[bucketIndex], element) } return buckets.flatMap { $0 } } func getBucketIndex (_ element: Int, _ minVal: Int, _ maxVal: Int, _ totalBucket: Int) -> Int { var index = 0 let capacity = Double (maxVal-minVal) / Double (totalBucket) var target = capacity while Double (element-minVal) > target { target += capacity index += 1 } return index } func addElementToBucket (_ bucket: inout [Int], _ element: Int) { bucket.append(element) var index = bucket.count - 1 while index - 1 >= 0 && bucket[index-1 ] > bucket[index] { bucket.swapAt(index-1 , index) index -= 1 } }
堆排序 排序方法:
将数组中的元素构建成最大堆结构后,第一个元素与最后一个元素交换。
对去掉最后一个元素的数组继续执行操作1,直到数组中元素的个数为0.
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 func heap (_ numbers: inout [Int]) { var lastIndex = numbers.count - 1 while lastIndex >= 0 { buildHeap(&numbers, lastIndex) numbers.swapAt(0 , lastIndex) lastIndex -= 1 } } func buildHeap (_ numbers: inout [Int], _ lastIndex: Int) { var parent = (lastIndex - 1 ) / 2 while parent >= 0 { heapify(&numbers, parent, lastIndex) parent -= 1 } } func heapify (_ numbers: inout [Int], _ index: Int, _ lastIndex: Int) { guard index < lastIndex else { return } let left = index * 2 + 1 let right = index * 2 + 2 var max = index if left <= lastIndex && numbers[left ] > numbers[max ] { max = left } if right <= lastIndex && numbers[right ] > numbers[max ] { max = right } if max != index { numbers.swapAt(index, max ) heapify(&numbers, max , lastIndex) } }