排序算法总结
数组真正乱序的实现
应用经典的Fisher–Yates
洗牌算法;实现思路:数组从后向前遍历,然后将当前元素与前面(包括自身)随机位置的数进行交换
v8 在处理 sort 方法时,使用了插入排序和快排两种方案。当目标数组长度小于10时,使用插入排序;反之,使用快排。
function shuffle(arr) {
let m = arr.length;
while (m > 1){
let index = Math.floor(Math.random() * m--);
[arr[m] , arr[index]] = [arr[index] , arr[m]]
}
return arr;
}
冒泡排序
实现思路:循环数组,比较当前元素与下一个元素;如果当前元素大于下一个元素,则向上冒泡(交换位置);这样一次循环下来后,最后一个数就是整个数组最大的;下次循环循环上面的操作;
复杂度: O(n2)
function bubbleSort(arr) {
const len = arr.length-1
for (let i = 0; i < len; i++) {
for (let j = 0;j < len-i;j++){
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
冒泡排序的优化版
优化思路:设置变量pos
用来记录每趟循环中最后一次进行交换的位置,由于pos
之后的元素都没有进行过交换,则说明pos
之后的元素是已经排序好的,下一次循环是扫描到pos
位置即可
function bubbleSort1(arr) {
let i = arr.length-1; // 初始时,最后位置保持不变
while (i > 0) {
let pos = 0;//每趟开始时,无记录交换
for (let j = 0;j < i;j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
pos = j;//记录最后交换的位置
}
}
i = pos;//为下一趟排序作准备
}
return arr;
}
插入排序
实现思路:将左侧看成有序的序列,每次遍历的时候,将元素插入到这个序列的对应位置;每次插入的时候从右侧开始比较;若比较的数较大,则向后移;
复杂度: O(n2)
function insertionSort(arr){
const len = arr.length
var prevIndex, cur;
for (var i = 1;i < len;i++) {
prevIndex = i-1
cur = arr[i]
while (prevIndex >= 0 && arr[prevIndex] > cur) {
arr[prevIndex+1] = arr[prevIndex]
prevIndex--
}
arr[prevIndex+1] = cur
}
return arr
}
选择排序
实现思路:每次循环选择最小的数字放在前面有序序列的末尾;
复杂度: O(n2)
function selectionSort(array) {
for (let i = 0; i < array.length; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
[array[i], array[minIndex]] = [array[minIndex], array[i]];
}
}
快速排序
实现思路:通过一趟遍历都将数据分为两部分,其中一部分的所有数据比另一部分的所有数据小,再将两部分数据按前面步骤递归,最终使整个数据变成有序的序列;
复杂度: 平均O(nlogn)
,最坏O(n2)
,实际上大多数情况下小于O(nlogn)
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const target = array[0];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([target], quickSort(right));
}
快速排序的优化版本
原 因: 如果数据原来就是有序的或者接近有序的,每次分区点都选择最后一个数 据,那快速排序算法就会变得非常糟糕,时间复杂度就会退化为O(n2);
实现思路:
- 三数字取中,如果数据特别多,可考虑五数或十数取中等
- 随机法
归并排序
实现思路:其是建立在归并操作上的一种排序算法,该算法是采用分治法(Divide and Conquer)的一个典型的应用,把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列;
复杂度: O(nlogn)
function merge(leftArr, rightArr){
var result = [];
while (leftArr.length > 0 && rightArr.length > 0){
if (leftArr[0] < rightArr[0])
result.push(leftArr.shift()); //把最小的最先取出,放到结果集中
else
result.push(rightArr.shift());
}
return result.concat(leftArr).concat(rightArr); //剩下的就是合并,这样就排好序了
}
function mergeSort(array){
if (array.length == 1) return array;
var middle = Math.floor(array.length / 2); //求出中点
var left = array.slice(0, middle); //分割数组
var right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right)); //递归合并与排序
}
小红包免费领
小礼物走一走
部分内容来源于网络,如有侵权,请留言或联系994917123@qq.com;访问量:waiting;访客数:waiting