1、比较类排序算法
1.1 冒泡排序：
- 核心思想：依次比较相邻元素，然后按条件进行元素交换。直到所有元素排好为止
- 代码实现：
// 升序排列
var nums = [8, 7, 6, 1, 2, 3, 4, 5]
let length = nums.count - 1
for i in 0..<length {
for j in 0..<length - i {
if nums[j] > nums[j+1] {
let tmp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
}
}
}
1.2 选择排序
- 核心思想：如果是升序排序，首先从未排序序列中找出最小值放在第一位，然后继续在剩下未排序的序列中找出最小值放在第二位，依次类推直到排序完成
- 代码实现
var min = Int.max
var minIndex = 0
var nums = [3,5,3,11]
for i in 0..<nums.count - 1 {
let k = i
for j in k..<nums.count {
if nums[j] < min {
min = nums[j]
minIndex = j
}
}
print("循环次数 === i = \(i)")
print("最小数值的索引值 minIndex= \(minIndex)")
//在这里进行替换
let tmp = nums[i]
nums[i] = min
nums[minIndex] = tmp
// 交换完成记得修改min
min = Int.max
}
1.3 插入排序
- 核心思想：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到响应的位置插入，直到排序完成
- 代码实现
var nums = [5,4,3,2]
let count = nums.count
//外层循环需要多少次才能排好
for i in 1..<count {
var preIndex = i - 1
let currentEle = nums[i]
while preIndex >= 0, nums[preIndex] > currentEle {
//向后移一位
nums[preIndex + 1] = nums[preIndex]
preIndex -= 1
}
// 将新元素插入
print(preIndex)
nums[preIndex + 1] = currentEle
}
print(nums)
1.4 希尔排序
- 核心思想：希尔排序是插入排序的改进版本，将整个待排序列分割成功若干个子序列，分别对子序列进行排序
- 代码实现
var nums = [5,7,8,3,1,2,4,6]
let length = nums.count
var grap = length/2
while grap > 0 {
//对各个分组进行进行插入排序
for i in grap ..< length {
print("i====\(i)")
var preIndex = i - grap
let currentElement = nums[i]
while preIndex >= 0, nums[preIndex] > currentElement {
nums[preIndex + grap] = nums[preIndex]
preIndex -= grap
}
nums[preIndex + grap] = currentElement
}
grap = grap / 2
}
print(nums)
1.5 归并排序
核心思想：分而治之，先序列拆分子序列，保证子序列有序，然后再将各个子序列进行合并。
代码实现
// 归并排序
func sort(arr: [Int]) -> [Int]{
if arr.count <= 1 { //1.如果传入数组为空或者只有一个元素，我们就不需要继续拆分，直接返回
return arr
}
let midIndex = arr.count / 2 //2.找到数组个数的中间值
// 左边拆分
let leftArray = sort(arr: Array(arr[0..<midIndex]))
// 右边拆分
let rightArray = sort(arr: Array(arr[midIndex..<arr.count]))
print("leftArray = \(leftArray)")
print("rightArray = \(rightArray)")
return merge(leftArr: leftArray, rightArr: rightArray)
}
func merge(leftArr: [Int], rightArr: [Int]) -> [Int] {
//1.定义左右两个索引
var leftIndex = 0
var rightIndex = 0
//2.定义一个临时数组
var tmpArr = [Int]()
//3.开始合并
while leftIndex < leftArr.count , rightIndex < rightArr.count {
if leftArr[leftIndex] < rightArr[rightIndex] {
//左边元素小于右边的
tmpArr.append(leftArr[leftIndex])
leftIndex += 1
}else if leftArr[leftIndex] > rightArr[rightIndex] {
//左边元素大于右边、
tmpArr.append(rightArr[rightIndex])
rightIndex += 1
}else {
tmpArr.append(leftArr[leftIndex])
leftIndex += 1
tmpArr.append(rightArr[rightIndex])
rightIndex += 1
}
}
//4.添加未添加完的
while leftIndex < leftArr.count {
tmpArr.append(leftArr[leftIndex])
leftIndex += 1
}
while rightIndex < rightArr.count {
tmpArr.append(rightArr[rightIndex])
rightIndex += 1
}
return tmpArr
}
1.6 快速排序
- 核心思想：选择一个基数（一般序列中间元素），将大于基数的数放在右边，小于该基数的数放在左边，然后对象左右两个数组重复前面的步骤直到排序好为止
- 代码实现
func quickSort(nums: [Int]) -> [Int] {
guard nums.count > 1 else { return nums }
let pivot = nums[nums.count/2]
var less = [Int]()
var equal = [Int]()
var greater = [Int]()
for num in nums {
if num > pivot {
greater.append(num)
}else if num < pivot {
less.append(num)
}else {
equal.append(num)
}
}
return quickSort(nums: less) + equal + quickSort(nums: greater)
}
2、非比较类排序
2.1 计数排序
- 核心思想：找到序列A中的max和min，创建一个max-min+1大小的数组B，数组B中记录A中某元素出现的次数，然后按B中次数依次输出元素，得到有序数组。
- 代码实现
func countSort(nums: [Int]) -> [Int] {
var max = Int.min
var min = Int.max
// 1.找到最大值
for num in nums {
if num > max {
max = num
}else if num < min{
min = num
}
}
// 2.创建一个长度为max-min + 1 的数组
let length = max - min + 1
var tmpArr = Array.init(repeating: 0, count: length)
for num in nums {
let tmpIndex = num - min
// 统计元素出现的次数
tmpArr[tmpIndex] = tmpArr[tmpIndex] + 1
}
var resultArr = [Int]()
for (index,var num) in tmpArr.enumerated() {
let value = index + min
while num > 0 {
resultArr.append(value)
num -= 1
}
}
return resultArr
}
2.2 桶排序
- 核心思想：将有序序列拆分到若干桶中，然后再对每个非空桶进行排序，然后整合输出得到有序序列
- 代码实现
/*
1.首先找出数组中max和min
2.确定grap，确定桶的个数
3.将数据填充到桶中
4.对非空桶进行排序
5.合并所以桶
*/
func bucketSort(arr: [Int],grap: Int) -> [Int] {
//1
var min = Int.max
var max = Int.min
for num in arr {
if num < min {
min = num
}else if num > max {
max = num
}
}
//2.确定桶数量
let bucketCount = (max - min)/grap + 1
var bucketArr = [[Int]]()
for _ in 0..<bucketCount {
bucketArr.append([Int]())
}
//3.叫数据填入桶中
for num in arr {
let index = (num - min) / grap
bucketArr[index].append(num)
}
//4.对非空桶进行排序
for (index,var subArr )in bucketArr.enumerated() {
if subArr.count > 0 {
//进行排序(可以选择冒泡排序，选择排序，插入排序，希尔排序，归并排序，计数排序都可以)
let length = subArr.count - 1
for i in 0..<length {
let k = length - i
for j in 0..<k {
if subArr[j] > subArr[j+1] {
let tmp = subArr[j]
subArr[j] = subArr[j+1]
subArr[j+1] = tmp
}
}
}
bucketArr[index] = subArr
}
}
print(bucketArr)
//5.输出
var results = [Int]()
for subArr in bucketArr {
if subArr.count > 0 {
results.append(contentsOf: subArr)
}
}
return results
}
2.3 基数排序
- 核心思想：将整数按位分割，然后按位数用桶排序
- 代码实现
func radixSort(arr: [Int]) -> [Int] {
//1.分配0-9个桶数组
var bucketList = [[Int]]()
for _ in 0..<10 {
bucketList.append([Int]())
}
print(bucketList.count)
//2.找出数组中最大的整数
var max = 0
for num in arr {
if num > max {
max = num
}
}
//3计算出最大位数
var maxCount = 1
var tmp = max / 10
while tmp != 0 {
maxCount += 1
tmp = tmp / 10
}
print(maxCount)
var orignArr = arr
//4.按位数排序
for i in 1...maxCount {
print("开始处理位数 === \(i)")
//4.1 先排序
for j in orignArr {
//4.2获取数字所在的索引
var digitNum = i
var index = 0
if digitNum == 1 {
index = j % 10
}else {
var divisor = 1
while digitNum > 1 {
divisor = divisor * 10
digitNum -= 1
}
index = j / divisor
}
print(index)
bucketList[index].append(j)
}
print(bucketList)
//4.3 替换
var totalIndex = 0
for arr in bucketList {
for ele in arr {
orignArr[totalIndex] = ele
totalIndex += 1
}
}
bucketList = [[Int]]()
for _ in 0..<10 {
bucketList.append([Int]())
}
print(bucketList)
print(orignArr)
// break
}
print(orignArr)
return orignArr
