（以下都是升序排列写法）
var testArr: [Int] = [2, 12, 44, 5, 9, 111, 322, 20]
func swap(a: Int, b: Int, arr: inout [Int]) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
- 直接插入排序
从前往后 把元素插入已经前面已经排序好的数组中
func chaRuSort(arr: inout [Int]) {
for i in stride(from: 1, through: arr.count - 1, by: 1) {
for j in stride(from: i - 1, through: 0, by: -1) {
if arr[j+1] < arr[j] {
swap(a: j+1, b: j, arr: &arr)
} else {
break
}
}
}
}
- 冒泡排序
相邻元素比较，每次发生交换就记录位置；
下一次遍历就只遍历到上次交换的位置，以为后面的元素都是有序的
func maopaoSort(arr: inout [Int]) {
var bounds = arr.count - 1
var pos = bounds
while pos != 0 {
bounds = pos
pos = 0
for i in stride(from: 0, through: bounds - 1 , by: 1) {
if arr[i] > arr[i+1] {
swap(a: i, b: i+1, arr: &arr)
pos = i
}
}
}
}
- 快速排序
一次排序： 先找一个基准数，并记录下来(挖坑)，先从右向左，找到元素比基准小下标为j，就把左边坑填为array[j]，再从左往右，直到找到元素比基准数大下标为i，就把该元素填到j的位置，直到i == j
/// 使用递归的思维 分区 挖坑
func devide(low: Int, high: Int, a: inout [Int]) -> Int {
let x = a[low]
var i = low, j = high
while i < j {
while a[j] >= x && i < j {
j -= 1
}
if i < j {
a[i] = a[j]
i += 1
}
while a[i] <= x && i < j {
i += 1
}
if i < j {
a[j] = a[i]
j -= 1
}
}
a[i] = x
return i
}
func quickSort(low: Int, high: Int, arr: inout [Int]) {
if low < high {
let devideIndex = devide(low: low, high: high, a: &arr)
quickSort(low: low, high: devideIndex - 1, arr: &arr)
quickSort(low: devideIndex + 1, high: high, arr: &arr)
}
}
- 希尔排序
希尔排序是对直接插入排序的优化 复杂度为O(n^(1.3-2))
将数组中的元素按照不同的步长分别插入排序
func shellSort(arr: inout [Int]) {
var grap = arr.count/2
while grap >= 1 {
for i in stride(from: grap, through: arr.count - 1, by: 1) {
for j in stride(from: i, through: 0, by: -grap) where j >= grap {
if arr[j] < arr[j-grap] {
swap(a: j, b: j-grap, arr: &arr)
} else {
break
}
}
}
grap = grap/2
}
}
- 选择排序
遍历数组 将最小的元素和当前遍历的的下标元素交换 即依次找到从小到大的元素
func selectSort(arr: inout [Int]) {
for i in stride(from: 0, to: arr.count - 1, by: 1) {
var minIndex = i
for j in stride(from: i + 1, through: arr.count - 1, by: 1) {
if arr[j] < arr[minIndex] {
minIndex = j
}
}
if minIndex != i {
swap(a: i, b: minIndex, arr: &arr)
}
}
}
- 堆排序
排序规格和选择排序类似
1、构造大顶堆，堆顶部就是最大的元素
2、交换顶部和最后一个元素，最大的元素放到最后
后续将0 - (n-1)的元素重复上述步骤
func heapSort(arr: inout [Int]) {
func swap(a: Int, b: Int) {
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
/// 调整大顶堆
func adjustHeap(i: Int, l: Int) {
let temp = arr[i]
var i = i
/// i * 2 + 1 找这个节点的 左子节点
var j = i * 2 + 1
while j < l {
/// 有右节点 且右节点比左节点大 j指向右子节点
if j + 1 < l && arr[j] < arr[j + 1] {
j += 1
}
if arr[j] > temp {
arr[i] = arr[j]
i = j
} else {
break
}
arr[i] = temp
j = 2 * j + 1
}
}
// 升序 - 构建大顶堆
for i in stride(from: arr.count/2 - 1, through: 0, by: -1) {
/// arr.count/2 - 1 最后一个非叶子结点
/// 从下到上 从右到左
adjustHeap(i: i, l: arr.count)
}
/// 调整堆结构+交换堆顶元素与末尾元素
for j in stride(from: arr.count - 1, to: 0, by: -1) {
/// 将堆顶元素与末尾元素进行交换
swap(a: 0, b: j)
/// 重新对堆进行调整
adjustHeap(i: 0, l: j)
}
//
}
/// 归并排序
分治法将数组元素分割成最小的单元
func mergrSort() {
func merge(arr: inout [Int], left: Int, right: Int, mid: Int) {
var i = left //左边序列指针
var j = mid + 1 //右边序列指针
var newArr: [Int] = []
while i <= mid && j <= right {
if arr[i] <= arr[j] {
newArr.append(arr[i])
i += 1
} else {
newArr.append(arr[j])
j += 1
}
}
while i <= mid { /// 添加左边剩余元素
newArr.append(arr[i])
i += 1
}
while j <= right { // 添加右边剩余元素
newArr.append(arr[j])
j += 1
}
i = left
var temp = 0
/// 将新数据中的元素拷贝到元素组
while i <= right {
arr[i] = newArr[temp]
temp += 1
i += 1
}
}
func sort(arr: inout [Int], left: Int, right: Int) {
if left < right {
let mid = (right - left)/2 + left
sort(arr: &arr, left: left, right: mid)
sort(arr: &arr, left: mid+1, right: right)
merge(arr: &arr, left: left, right: right, mid: mid)
}
}
//
sort(arr: &testArr, left: 0, right: testArr.count - 1)
}
