常用算法总结，锻炼一下思维😀
冒泡排序：
- 1：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 2：对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 3：针对所有的元素重复以上的步骤，除了最后一个。
- 4：持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
func bubbleSort<T: Comparable>(array: [T]) -> [T] {
//如果数组只有一个元素，直接返回
guard array.count > 1 else{
return array
}
var tempArr = array
let count = array.count
for i in 0...(count-1) {
for j in 0..<(count - i - 1){
//比较两个元素，如果前面的比后面的大，就交换位置，其他情况不动，继续下一轮比较
if tempArr[j] > tempArr[j+1]{
let temp = tempArr[j+1]
tempArr[j+1] = tempArr[j]
tempArr[j] = temp
}
}
}
return tempArr
}
外层循环所有元素，内层循环除了最后一位的元素，每次都把最大的元素放在最后，直到循环完毕。
快排：
- 1：从数列中挑出一个元素，称为 “基准”（pivot）。
- 2： 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面，相同的放在中间。
- 3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
func quickSort<T: Comparable>(array:[T]) -> [T] {
//如果数组只有一个元素，直接返回
guard array.count > 1 else {
return array
}
let pivot = array[array.count/2]//取出中间位置的值作为基准
let less = array.filter { $0 < pivot }//过滤小于基准的值，返回一个数组
let equal = array.filter { $0 == pivot }//过滤等于基准的值，返回一个数组
let greater = array.filter { $0 > pivot }//过滤大于基准的值，返回一个数组
return quickSort(array: less) + equal + quickSort(array: greater)//利用递归，返回最后的有序数组
}
归并排序：
- 1：把长度为n的输入序列分成两个长度为n/2的子序列。
- 2：对这两个子序列分别采用归并排序。
- 3：将两个排序好的子序列合并成一个最终的排序序列。
func mergeSort<T: Comparable>(array: [T]) -> [T] {
//如果数组只有一个元素，直接返回
guard array.count > 1 else{
return array
}
let count = array.count
let middle = count/2//取中间位置
let left = Array(array.prefix(upTo: middle))//取左边数组
let right = Array(array.suffix(from: middle))//取右边数组
//利用递归，合并左边和右边的数组
return merge(left: mergeSort(array: left), right: mergeSort(array: right))
}
func merge<T: Comparable>(left: [T], right: [T]) -> [T] {
var tempLeft = left
var tempRight = right
var result = Array<T>()
//当两个数组都有值的时候
while tempLeft.count > 0 && tempRight.count > 0 {
if tempLeft[0] <= tempRight[0]{
//如果左边的第一个元素大于右边的第一个元素，就取出左边的第一元素放到result数组里
result.append(tempLeft.removeFirst())
}else{
//如果左边的第一个元素小于右边的第一个元素，就取出右边的第一元素放到result数组里
result.append(tempRight.removeFirst())
}
}
//当只剩下左边数组的时候,合并到result数组
if tempLeft.count > 0{
result += tempLeft
}
//当只剩下由边数组的时候,合并到result数组
if tempRight.count > 0{
result += tempRight
}
return result
}
插入排序：
- 1：从第一个元素开始，该元素可以认为已经被排序。
- 2：取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 3：如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 4：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 5：将新元素插入到该位置后。
- 6：重复步骤2~5。
func insertionSort<T: Comparable>(array: [T]) -> [T] {
//如果数组只有一个元素，直接返回
guard array.count > 1 else{
return array
}
let count = array.count
var preIndex: Int
var current: T
var tempArr = array
for i in 1..<count {
preIndex = i - 1
current = tempArr[i]
while preIndex >= 0 && tempArr[preIndex] > current{
tempArr[preIndex+1] = tempArr[preIndex]
preIndex -= 1
}
tempArr[preIndex+1] = current
}
return tempArr
}
还有其他的一些排序方法，以后再写吧，当然，Swift数组已经有排序方法：
public func sorted() -> [Element]//返回排序后的数组，默认升序
public func sorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element]//利用闭包返回想要的排序数组
网友评论