1 分类
- 内部排序
将所有数据加载到内部存储器中排序 - 外部排序
数据量过大，需要借助外部存储进行排序
2 算法性能
时间复杂度是用来描述算法运行时间的，那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，也可以这样考虑，时间复杂度就是操作一个单元的次数。
这里上几个例子，
（1）对数阶
let i = 1
while(i<n){
i = i * 3
}
n = 3^x，即x = log3(n)，循环执行了x次，因此这里时间复杂度为对数阶
（2）线性对数阶
for(let j = 0; j < n; j++) {
let i = 1
while(i<n){
i = i * 3
}
}
也就是将时间复杂度为对数阶的代码重复了n次，所以线性对数阶
一般讨论时间复杂度都是在最坏情况下的时间复杂度
3 排序算法
3.1 交换排序
冒泡
如果数据有序，这里就会提前终止循环，这样就相当于只有外层一个遍历，所以最好情况的时间复杂度为O(n)
function fn(arr) {
let len = arr.length
// 优化：如果一趟循环，没有发生交换，说明数组有序，可以提前终止遍历
let flag = false
//外层循环控制趟数
for (let i = 0; i < len - 1; i++) {
//内层循环控制每趟需要交换的次数
for (let j = 0; j < len - i - 1; j++) {
// 从小到大
if (arr[j] > arr[j + 1]) {
flag = true
;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
if (flag === false) {
break
} else {
flag = false
}
}
return arr
}
快速排序
快速排序的基本思想是找一个基准值，然后把小于基准值的元素放在一边，大于基准值的元素放在一边，然后在左右两边重复进行这样的操作
一个最简单的未优化的快速排序算法代码如下：
function sort(nums) {
// 利用dfs解决快速排序问题（从小到大）
function dfs(start, end) {
// 当区间中只有一个元素时，就不用分区了
if (start >= end) return
// 把每个区间的最后一个元素作为基准（比基准小的放左边，大的放右边），实现分区，返回分区基准所在的位置，方便下次分区
let temp = partition(start, end)
dfs(start, temp - 1)
dfs(temp + 1, end)
}
// 分区函数，利用的是双指针
function partition(start, end) {
// 最后一个元素作为基准
let pivot = nums[end]
// 快慢指针
let less = start
let great = start
for (; great < end; great++) {
// 比基准小的放左边，大的放右边
if (nums[great] < pivot) {
swap(nums, less, great)
less++
}
}
// 把基准元素放到对应位置
swap(nums, less, end)
return less
}
// 交换两个元素
function swap(data, i, j) {
let temp = data[i]
data[i] = data[j]
data[j] = temp
}
dfs(0, nums.length - 1)
}
3.2 选择排序
遍历所有元素，每遍历一个元素，都要拿到这个元素之后的元素的最小值，并替换当前元素
不稳定：举个例子，序列5 8 5 2 9
function fn(arr) {
let len = arr.length
for (let i = 0; i < len - 1; i++) {
let index = i
let min = arr[i]
// 获取当前元素之后元素的最小值
for (let j = i + 1; j < len; j++) {
// 从小到大
if (arr[j] < min) {
min = arr[j]
index = j
}
}
// 如果当前值就是最小值，就不要换了
if (index !== i) {
;[arr[i], arr[index]] = [arr[index], arr[i]]
}
}
return arr
}
3.3 插入排序
直接插入
把数组分为一个有序表和一个无序表，遍历无序表，每遍历一个元素从有序表中找到合适位置插入（这里也就需要一个循环）
如果数据有序，就不会经过内层循环，这样就相当于只有外层一个遍历，所以最好情况的时间复杂度为O(n)
function fn(arr) {
// 遍历无序表
for (let i = 1; i < arr.length; i++) {
let insertVal = arr[i]
let insertIndex = i - 1
// 遍历有序表，确定插入位置;从小到大
//给insertVal找到插入位置
//说明
//1 insertIndex >= 0 保证在给insertVal 找插入位置的时候，不越界
//2 insertVal < arr[insertIndex] 说明待插入的数，还没有找到插入位置
//3 就需要将arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex]
insertIndex--
}
//当退出while循环时，说明插入的位置找到
arr[insertIndex + 1] = insertVal
}
return arr
}
arr = [2, 1, -3, 5]
console.log(fn(arr))
希尔排序
缩小增量的方式,当增量减为1的时候，算法结束
function fn(arr) {
let len = arr.length
// 本层循环控制需要几趟循环
for (let gap = len / 2; gap > 0; gap = parseInt(gap / 2)) {
//遍历各组中所有元素（共gap组，每组有10/gap个元素），步长gap
for (let i = gap; i < len; i++) {
for (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
;[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]]
}
}
}
}
return arr
}
3.4 归并排序
在递的时候不断将区间一分为二，直到每个区间只有一个元素；在归的时候，完成合并，在合并时要做顺序的调整文章来源：https://www.toymoban.com/news/detail-535749.html
function sort(nums) {
// 从小到大
function dfs(start, end) {
if (start >= end) return
// 对数组区间不断一分为二，直到每个区间只有一个元素
let mid = parseInt((start + end) / 2)
dfs(start, mid)
dfs(mid + 1, end)
// 在归的时候，完成合并，在合并时要做顺序的调整
merge(start, mid, end)
}
function merge(start, mid, end) {
let temp = []
// 需要两个指针，分别指向两个区间开始的位置
let i = start
let j = mid + 1
// 操作temp的指针，直接使用temp.push()也是可以的
let tmpPos = 0
// 排序，把有序的元素保存到temp数组中
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) {
temp[tmpPos++] = nums[i++]
} else {
temp[tmpPos++] = nums[j++]
}
}
// 若第一个区间还有元素，直接全部放进temp中
while (i <= mid) {
temp[tmpPos++] = nums[i++]
}
// 若第二个区间还有元素，直接全部放进temp中
while (j <= end) {
temp[tmpPos++] = nums[j++]
}
// temp数组拷贝给nums
for (let i = 0; i < temp.length; i++) {
nums[start++] = temp[i]
}
}
dfs(0, nums.length - 1)
}
3.4 基数排序
4 小结
注：图片来自于网络，如有侵权，请联系删除文章来源地址https://www.toymoban.com/news/detail-535749.html
- 快速排序和归并排序都可以用递归来做，用迭代应该也可以，对于递归原理可以查看 递归（原理学习）
到了这里，关于常用排序算法汇总的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
