//1.冒泡排序
//通过lastIndex减少外层循环，flag减少内层循环，平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，稳定排序
function bubbleSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let lastIndex = arr.length - 1;
while(lastIndex > 0) {
let flag = true,
k = lastIndex;
for(let i = 0;i < k;i++) {
if (arr[i] > arr[i + 1]) {
flag = false;
lastIndex = i;
[arr[i],arr[i + 1]] = [arr[i + 1],arr[i]];
}
}
if (flag) break;
}
}
let s = [1,6,8,3,6,2,3,9];
bubbleSort(s)
s
//2.选择排序
//选择排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，不是稳定排序
function selectSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let length = arr.length;
for(let i = 0;i < length - 1;i++) {
let minIndex = i;
for(let j = i + 1;j < length;j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
swap(arr,minIndex,i);
}
}
function swap(arr,left,right) {
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
let s = [1,6,8,3,6,2,3,9];
selectSort(s)
s
//3.插入排序
//平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序
function insertSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let length = arr.length;
for(let i = 1;i < length;i++) {
let j = i,
temp = arr[i];
while(j - 1 >= 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
let s = [1,6,8,3,6,2,3,9];
insertSort(s)
s
//4.希尔排序
//总体小于n^2,平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序
function hillSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let length = arr.length;
for(let gap = parseInt(length >> 1);gap > 0;gap = parseInt(gap >> 1)) {
for(let i = gap;i < length;i++) {
let temp = arr[i],
j = i;
while(j - gap >= 0 && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
let s = [1,6,8,3,6,2,3,9];
hillSort(s)
s
//归并排序
//平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序
function mergeSort(arr) {
if (!Array.isArray(arr) || arr.length < 1) return;
if (arr.length === 1) {
return arr;
}
let length = arr.length;
let midIndex = parseInt(length >> 1),
leftArr = arr.slice(0,midIndex),
rightArr = arr.slice(midIndex,length);
return merge(mergeSort(leftArr),mergeSort(rightArr));
}
function merge(left,right) {
let result = [],
llength = left.length,
rlength = right.length,
il = 0,
ir = 0;
while(il < llength && ir < rlength) {
if (left[il] < right[ir]) {
result.push(left[il++]);
}else {
result.push(right[ir++]);
}
}
while(il < llength) {
result.push(left[il++]);
}
while(ir < rlength) {
result.push(right[ir++]);
}
return result;
}
let s = [1,6,8,3,6,2,3,9];
let m = mergeSort(s)
m
//快速排序
//平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(logn) ，不是稳定排序 ，效率最高
function quickSort(arr,start,end) {
if (!Array.isArray(arr) || arr.length < 1 ||start > end) return;
let index = partition(arr,start,end);
quickSort(arr,start,index - 1);
quickSort(arr,index + 1,end);
}
function partition(arr,start,end) {
let pivot = arr[start];
while(start < end) {
while(start < end && arr[end] >= pivot) {
end--;
}
arr[start] = arr[end];
while(start < end && arr[start] < pivot) {
start++;
}
arr[end] = arr[start];
}
arr[start] = pivot;
return start;
}
let s = [1,6,8,3,6,2,3,9];
quickSort(s,0,s.length - 1);
s
//堆排序
//构建大顶堆，交换位置实现排序，平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(1) ，不是稳定排序
function heapSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let length = arr.length;
buildMaxHeap(arr);
for(let i = length - 1;i >= 0;i--) {
swap(arr,0,i);
adjustMaxHeap(arr,0,i);
}
}
function buildMaxHeap(arr) {
let length = arr.length,
iParent = parseInt(length >> 1) - 1;
for(let i = iParent;i >= 0;i--) {
adjustMaxHeap(arr,i,length);
}
}
function adjustMaxHeap(arr,index,heapSize) {
let iMax,
iLeft,
iRight;
while(true) {
iMax = index;
iLeft = 2 * iMax + 1;
iRight = 2 * iMax + 2;
if (iLeft < heapSize && arr[iLeft] > arr[iMax]) {
iMax = iLeft;
}
if (iRight < heapSize && arr[iRight] > arr[iMax]) {
iMax = iRight;
}
if (iMax !== index) {
swap(arr,iMax,index);
index = iMax;
}else {
break;
}
}
}
function swap(arr,left,right) {
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
let s = [1,6,8,3,6,2,3,9];
heapSort(s)
s
//基数排序
//非比较类排序算法，平均时间复杂度为 O(nk)，k 为最大元素的长度，最坏时间复杂度为 O(nk)，空间复杂度为 O(n) ，牺牲空间换速度，是稳定排序
function radixSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let max = arr[0],
buckets = [],
loop,
length = arr.length;
for(let i = 1;i < length;i++) {
if (arr[i] > max) {
max = arr[i];
}
}
loop = (max + '').length;
for(let i = 0;i < 10;i++) {
buckets[i] = [];
}
for(let i = 0;i < loop;i++) {
for(let j = 0;j < length;j++) {
let str = arr[j] + '';
let length = str.length;
if (length >= i + 1) {
let k = parseInt(str[length - 1 - i]);
buckets[k].push(arr[j]);
}else {
buckets[0].push(arr[j]);
}
}
arr.splice(0,length);
for(let i = 0;i < 10;i++) {
let k = buckets[i].length;
for(let j = 0;j < k;j++) {
arr.push(buckets[i][j]);
}
}
}
return arr;
}
let s = [1,6,8,3,6,2,3,9];
let m = radixSort(s)
m
上述八种排序算法，快速排序的效率最高，前几种的时间复杂度全部趋近于O(n^2)，堆排序，快速排序，归并排序的时间复杂度较低，三者中效率最高的是快速排序，由于缓存机制和操作有效性的区别，导致快速排序的效率最高
网友评论