【算法】常见排序算法算法排序

常见排序算法

排序方式	分类	排序算法	平均时间复杂度	空间复杂度	稳定性
内部排序	插入排序	直接插入排序	O(n2)	O(1)	稳定
		折半插入排序	O(n2)	O(1)	稳定
		希尔排序	O(n1.3~2)	O(1)	不稳定
	交换排序	冒泡排序	O(n2)	O(1)	稳定
	交换排序	快速排序	O(nlogn)	O(nlogn)	不稳定
	选择排序	简单选择排序	O(n2)	O(1)	不稳定
	选择排序	堆排序	O(nlogn)	O(1)	不稳定
	基数排序		O(n×k)	O(n+k)	稳定
	桶排序		O(n+k)	O(n+k)	稳定
	计数排序		O(n+k)	O(k)	稳定
外部排序	归并排序		O(nlogn)	O(n)	稳定
	多路归并	循环遍历归并排序	O(n×k)	O(k)	*
		最小堆K路归并排序	*	*	*
		败者树K路归并排序	*	*	*

1 内部排序内部排序指待排序完全放在内存中进行的排序过程，适合不太大的元素序列

插入排序
交换排序
选择排序
其他内部排序

1.1 插入排序
循环将待排序的一个元素插入到已排序的序列中

直接插入排序
折半插入排序
希尔排序

1.1.1 直接插入排序算法思想

将原序列分为已排序与未排序的两部分
外层循环遍历整个序列，标记当前待插入元素
内层循环遍历已排序序列，从有序表的尾部开始与当前值进行比较移动

文章图片

算法实现

function insertSort(arr) { //遍历整个序列 for (let i = 0; i < arr.length; i++) { //当前待插入值 let temp = arr[i] //遍历已排序序列，待插入值小则与前值交换 for (let j = i - 1; j >= 0 && arr[j] > temp; j--) { //解构赋值方式交换 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } return arr }

边找边移动

1.1.2 折半插入排序算法思想

与直接插入排序的思想基本一致，需要将原序列分为已排序和未排序两部分
不同的在于在比较时不从末尾以此比较，而是使用折半查找的方式查找排序位置

算法实现

function midInsertSort(arr) { //折半向下取整 function absInt(a, b) { return Math.abs(parseInt((a + b) / 2)) } for (let i = 1; i < arr.length; i++) { let temp = arr[i]; let left = 0, right = i - 1, mid = absInt(left, right) let tag = 0 //折半查找插入位置 while (left < right) { if (temp > arr[mid]) { left = mid + 1 mid = absInt(left, right) } else if (temp < arr[mid]) { right = mid - 1 mid = absInt(left, right) } else break } //保证稳定性 if (temp >= arr[mid]) tag = 1 //移动 for (let move = mid + tag; move <= i; move++) { [arr[move], temp] = [temp, arr[move]] } } return arr }

其核心是折半查找(也称为二分查找)，先通过查找算法找到插入位置再统一移动

1.1.3 希尔排序算法思想

对原序列按照一个增量(间隔)进行分组
对已分组的子序列使用直接插入排序
减小增量再分组然后排序，以此类推
当增量为1时，使用直接插入排序返回结果

文章图片

算法实现

function shelltSort(arr) { //定义初始增量 let gap = Math.floor(arr.length / 2) //增量减至1时执行最后一次直接插入排序 while (gap >= 1) { //子序列的直接插入排序 for (let i = gap; i < arr.length; i += gap) { let temp = arr[i] for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]] } } //增量减半 gap = Math.floor(gap / 2) } return arr }

希尔排序的核心排序算法还是直接插入排序，先按照增量进行分组，组内使用直接插入排序，不断缩小增量重分组再排序，至到增量缩小为1进行最后一次直接插入排序
如果 gap为1其排序的部分就是上面介绍的 直接插入排序

1.2 交换排序

冒泡排序
快速排序

1.2.1 冒泡排序算法思想

相邻两两比较交换位置，先将最大或最小的值交换至顶端
外层的一次循环可以确定一个最大或最小值
根据已经确定的值不断缩小比较区间，最终返回结果

文章图片

该算法是最简单最暴力性能最差的一种排序算法

算法实现

function bubbleSort(arr) { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } } return arr }

通过不断交换， 每一趟确定一个值的位置
下一趟该值不再参与排序

1.2.2 快速排序算法思想

从序列中选取一个值作为基准
通过不断的交换，将所有元素中比基准小或大的值放在其两侧
这样就确定了一个值的位置，称为一趟换分
再递归的将两侧的区间进行同样的划分，最终得到排序的序列

文章图片

算法实现

function quickSort(arr, low, high) { //确定两侧指针 low = typeof low != 'number' ? 0 : low high = typeof high != 'number' ? arr.length - 1 : high; //指针重合结束循环 if (low < high) { //根据基准进行划分，返回基准坐标 let pivotIndex = partition(arr, low, high) //基准左侧递归 quickSort(arr, low, pivotIndex - 1) //基准右侧递归 quickSort(arr, pivotIndex + 1, high) } return arr } function partition(arr, low, high) { //以子序列起点为基准 let pivot = arr[low] //指针重合结束循环 while (low < high) { //从右侧寻找小于等于基准的值 while (low < high && arr[high] > pivot) --high //将小于等于基准的值前移 arr[low] = arr[high] //从左侧找大于基准的值 while (low < high && arr[low] <= pivot) ++low //将大于基准的值后移 arr[high] = arr[low] } //将基准放入重合的指针左边 arr[low] = pivot //返回基准坐标 - 左侧均小于基准，右侧均大于基准 return low }

上述快速排序算法是经典的以子序列为基准来递归划分
也可以以中间值或尾部为基准进行划分，实现不太相同，思想基本一致

1.3 选择排序

简单选择排序
堆排序

1.3.1 简单选择排序算法思想

外层遍历确定位置
内层遍历寻找子序列中最大或最小的值

也是一种简单的暴力的性能差的排序算法，时间复杂度始终是O(n 2)

算法实现

function selectSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let index = i for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[index]) { index = j } } [arr[i], arr[index]] = [arr[index], arr[i]] } return arr }

1.3.2 堆排序算法思想

根据原序列创建一个完全二叉树
将完全二叉树重排为堆(父节点大于/小于子节点)
将堆首和堆尾互换，堆首为最大/最小值，将其选出，堆尺寸缩小1
将互换后的完全二叉树再重排位堆
重复3 4 只到堆的尺寸为1

算法实现

function heapSort(arr) { let len = arr.length //创建一个大根堆 - 从最后一个非叶子节点开始，保证能比较交换出最大值 for (let i = Math.floor(len / 2 - 1); i >= 0; i--) { heapify(arr, i, len) } //交换当前堆顶与堆尾，堆尺寸减1，调整堆 for (let i = arr.length - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]] len-- //从对顶调整即可，次大值就是其左右子节点中的一个 heapify(arr, 0, len) } return arr } function heapify(arr, i, len) { //确定父节点的两个子节点下标 let left = i * 2 + 1, right = i * 2 + 2, largest = i //找出父节点、左右子节点中的最大值，并标记下标 if (left < len && arr[left] > arr[largest]) largest = left if (right < len && arr[right] > arr[largest]) largest = right //最大值不是父节点 if (largest !== i) { //交换父节点与子节点的值 [arr[largest], arr[i]] = [arr[i], arr[largest]] //子节点向下继续调整 heapify(arr, largest, len) } }

该算法的核心在堆的调整
创建堆时从 最后一个非叶子节点开始比较交换
首尾互换后，从 首节点开始向下比较交换一个方向即可

1.4 其他内部排序

基数排序：根据键值的每位数据来分配桶
桶排序：每个桶存储一定范围的数值
计数排序：每个桶只存储单一键值

这三种排序算法都是基于桶，将数值进行分类后再排序
这里仅介绍基数排序的方式

1.4.1 基数排序算法思想

从个位开始按顺序入桶
从桶号最小的开始，先进桶的先出桶
再从十位开始入桶出桶的操作，以此类推

文章图片

算法实现

function radixSort(arr, maxDigit) { //初始化容器，进制，被除数 let counter = [], mod = 10, dev = 1 //根据最大位数进行遍历进桶 for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { //根据当前位按数据进桶 for (let j = 0; j < arr.length; j++) { let bucket = parseInt((arr[j] % mod) / dev) if (counter[bucket] == null) { counter[bucket] = [] } counter[bucket].push(arr[j]) } let pos = 0 //从小为桶号开始，先进桶的先出桶 for (let z = 0; z < counter.length; z++) { let value = https://www.it610.com/article/null if (counter[z] != null) { while ((value = counter[z].shift()) != null) { arr[pos++] = value } } } } return arr }

2 外部排序

归并排序
多路归并排序

2.1 归并排序
算法思想

自上而下将原序列递归的分成两部分，直至左右长度为1
双指针法逐次比较两个序列的值，小值添加至合并空间并移动其指针
将另一序列未添加到合并空间的剩余值与合并空间进行拼接
自下而上的迭代2 3进行合并，最终完成顶层左右序列的合并

文章图片

算法实现

function mergeSort(arr) { //递归分治 - 直到长度为1 if (arr.length > 1) { let middle = Math.floor(arr.length / 2), left = mergeSort(arr.slice(0, middle)), right = mergeSort(arr.slice(middle)) arr = merge(left, right) } return arr } function merge(left, right) { //定义两个指针，在左右序列中移动 let i = 0, j = 0, result = [] //双指针法依次比较两个序列的值， //选择小值添加到result中，并移动其指针 //有一个移动结束循环结束 while (i < left.length && j < right.length) { result.push(left[i] < right[j] ? left[i++] : right[j++]) } //将另一个指针未移动结束序列的剩余值与result进行拼接 return result.concat(i < left.length ? left.slice(i) : right.slice(j)) }