你还不会大厂必考的10个经典排序算法吗？
公众号：程序员白特，欢迎一起交流学习~
前言
众所周知，10个经典排序算法在大厂的校招、社招面试中频繁出现，那么今天我们就来用JS语言实现一下这10个经典排序算法吧。
概念
- 排序算法：
排序算法是《数据结构与算法》中最基本的算法之一。它可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等
- 大O表示法：
算法效率的计算方法常用大O表示法，大O表示法的推导方式如下：
（1）用常量1取代运行时间中的所有加法常量
（2）在修改后的运行次数函数中，只保留最高阶项
（3）如果最高存在且不为1，则去除与这个项相乘的常数
- 各排序算法复杂度对比：
实现
1、冒泡排序
1、代码实现
// 冒泡排序
function bubbleSort(array) {
// 1、获取数组的长度
let length = array.length;
for(let j=length-1; j>=0; j--) {
//第一次进来： i=0, 比较0和1的位置
//最后一次进来： i=length-2, 比较length-2和length-1的位置
for(let i=0; i<j; i++) {
if(array[i] > array[i+1]) {
let temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
return array;
}
console.log(bubbleSort([1,8,11,90,2,7,8]));//[1,2,7,8,8,11,90]
2、选择排序
1、代码实现
function selectionSort(array) {
// 1、获取数组长度
let length = array.length;
// 2、外层循环：从0位置开始取数据
for(let j=0; j<length-1; j++) {
let min = j;
// 3、内层循环: 从min+1位置开始，和后面的数据进行比较
for(let i=min+1; i<length; i++) {
if(array[min] >= array[i]) {
min = i;
}
}
let temp = array[j];
array[j] = array[min];
array[min] = temp;
}
console.log(array);
}
selectionSort([91,8,11,90,2,7,8])//[ 2, 7, 8, 8,11, 90, 91]
3、插入排序
1、代码实现
function insertionSort(array) {
// 1、获取数组的长度
let length = array.length;
// 2、外层循环： 从第一个位置开始，向前面局部有序插入数据
for(let i=1; i<length; i++) {
// 3、内层循环： 获取第i个位置的数据，和前面的数据依次进行比较
let temp = array[i];
let j = i;
while(array[j-1] > temp && j > 0) {
array[j] = array[j-1];
j--;
}
// 4、将j位置的数据，放置temp即可
array[j] = temp;
}
console.log(array);
}
insertionSort([91,8,1,90,2,7,8]);//[1, 2, 7, 8,8, 90, 91]
4、希尔排序
1、代码实现
function shellSort(array) {
// 1、获取数组长度
let length = array.length;
// 2、初始化的增量(gap -> 间隔/间隙)
let gap = Math.floor(length / 2);
// 3、while循环,gap不断减少
while(gap >= 1) {
// 4、以gap作为间隙，进行分组，对分组进行插入排序
for(let i=gap; i<length; i++) {
let temp = array[i];
let j = i;
while((array[j-gap] > temp) && (j > gap - 1)) {
array[j] = array[j-gap];
j-=gap;
}
// 5、将j位置的元素赋值为temp
array[j] = temp;
}
// 6、gap不断缩小
gap = Math.floor(gap / 2);
}
console.log(array);
}
shellSort([91,8,1,90,2,7,8]);//[1, 2, 7, 8, 8, 90, 91]
5、快速排序
1、代码实现
function swap(m, n, array) {
let temp = array[m];
array[m] = array[n];
array[n] = temp;
}
// 一、枢纽的选择
function median(left, right, array) {
// 1、取出中间位置
let center = Math.floor((left + right) / 2);
if(array[left] > array[right]) {
swap(left, right, array)
}
// 2、判断大小，并进行交换
if(array[left] > array[center]) {
swap(left, center, array);
}
if(array[center] > array[right]) {
swap(center, right, array);
}
// 3、将center换到right-1的位置上
swap(center, right-1, array);
return array[right-1];
}
// 二、快速排序的实现
function quickSort(array) {
quick(0, array.length-1, array);
return array;
}
// 因为要传很多参数，所以另起一个函数
function quick(left, right, array) {
if(left >= right) return;
let pivot = median(left, right, array);
let i = left;
let j = right-1;
while(true) {
while(array[++i] < pivot) {}
while(array[--j] > pivot) {}
if(i < j) {
swap(i, j, array);
}else {
break;
}
}
swap(i, right-1, array);
quick(left, i-1, array);
quick(i+1, right, array);
}
console.log(quickSort([91,8,1,90,2,7,8]));
6、堆排序
1、代码实现
function swap(tree, m, n) {
let temp = tree[m];
tree[m] = tree[n];
tree[n] = temp;
}
// 1、将每一层进行堆化
// (函数headify只考虑到局部(例如，左子树堆化了。右子树可能没堆化)，所以整棵树堆化需要重新调用 buildTree函数)
function headify(tree, n, i) {
if(i >= n) {
return;
}
let c1 = Math.floor(2*i+1);
let c2 = Math.floor(2*i+2);
let max = i;
// 如果有赋值，要用赋值的结果，否则会出错
if(c1 < n && tree[c1] > tree[max]) {
max = c1;
}
if(c2 < n && tree[c2] > tree[max]) {
max = c2;
}
if(max !== i) {
swap(tree, max, i);
headify(tree, n, max);
}
}
// 2、建立一棵完全堆化成功的树(即若数字的顺序很乱,怎么把整棵树都 heapify，需要调用buildTree)
function buildTree(tree, n) {
let lastNode = n-1;//最后一个节点的index值
let parent = Math.floor((lastNode - 1) / 2);
for(let i=parent; i>=0; i--) {
headify(tree, n, i);
}
}
// 3、堆排序
function heapSort(tree, n) {
buildTree(tree, n);
let i;
for(i=n-1; i>=0; i--) {
swap(tree, i, 0);
headify(tree, i, 0);
}
}
// 4、调用堆排序函数
let tree = [91,8,1,90,2,7,8];
let size = tree.length;
heapSort(tree, size);
console.log(tree);//[1, 2, 7, 8, 8, 90, 91]
7、归并排序
1、思路地址
https://www.bilibili.com/video/BV1Pt4y197VZ?from=search&seid=8783899578846664847
2、实现代码
// 归并排序
// 2、合并
function merge(arr, tempArr, left, mid, right) {
// 标记左半区第一个未排序的元素
let left_pos = left;
// 标记右半区第一个未排序的元素
let right_pos = mid + 1;
// 临时数组的下标
let pos = left;
// 合并
while(left_pos <= mid && right_pos <= right) {
if(arr[left_pos] < arr[right_pos]) {
tempArr[pos++] = arr[left_pos++];
}else {
tempArr[pos++] = arr[right_pos++];
}
}
// 合并左半区剩余的元素
while(left_pos <= mid) {
tempArr[pos++] = arr[left_pos++];
}
// 合并右半区剩余的元素
while(right_pos <= right) {
tempArr[pos++] = arr[right_pos++];
}
// 把临时数组中合并后的元素复制到原来的数组
while(left <= right) {
arr[left] = tempArr[left];
left++;
}
}
// 1、划分
function mergeSort(arr, tempArr, left, right) {
// 如果只有一个元素，那么不需要继续划分
// 只有一个元素的区域，本身就是有序的，只需要被归并就可以
if(left < right) {
// 找中间点
let mid = Math.floor((left + right) / 2);
// 递归划分左半区
mergeSort(arr, tempArr, left, mid);
// 递归划分右半区
mergeSort(arr, tempArr, mid + 1, right);
// 调用合并函数
merge(arr, tempArr, left, mid, right);
}
}
let arr = [1,8,11,90,2,7,8];
let n = arr.length;
let tempArr = [];
mergeSort(arr, tempArr, 0, n - 1);
console.log(arr);
8、计数排序
1、实现代码
// 计数排序
function countingSort(arr, maxValue) {
let bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
9、桶排序
1、实现代码
// 桶排序
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
let i;
let minValue = arr[0];
let maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}
//桶的初始化
let DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
let buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
//利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
10、基数排序
1、实现代码
// 基数排序
let counter = [];
function radixSort(arr, maxDigit) {
let mod = 10;
let 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 j = 0; j < counter.length; j++) {
let value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
查看5道真题和解析
我现在也只有一个保底
太难了
