1排序算法分类
冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 推排序 计数排序 桶排序 基数排序
2 计算代码如下
冒泡排序 function bubbleSort(arr) {
let len = arr.length;
for(let i = 0;j<len-1-i;j++){
for(let j = 0;j< len-1-i;j++) {
if(arr[j]>arr[j+1]){
[arr[j+1],arr[j]] = [arr[j],arr[j+1]];
}
}
}
return arr;
}
//快排demo:
function quickSort(arr,left,right) {
let len = arr.length;
let partitionIndex;
left = typeof left != 'number'? 0 :left;
right = typeof right !='number'? len -1 :right;
if(left<right) {
partitionIndex = partition(arr,left,right);
quickSort(arr,left,partitionIndex-1);
quickSort(arr,partitionIndex+1,right);
}
return arr;
}
function partition(arr,left,right) {
let pivot = left;
let index = pivot + 1;
for(let i = index;i<=right;i++) {
if(arr[i]<arr[pivot]){
[arr[i],arr[index]] = [arr[index],arr[i]];
index++;
}
}
[arr[pivot],arr[index-1]] = [arr[index-1],arr[pivot]];
return index-1
}
// 选择demo
function selectionSort (arr){
let len = arr.length;
let minIndex;
for(let i=0;i<len-1;i++) {
minIndex = i;
for (let j=i+1;j<len;j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
[arr[i],arr[minIndex]] = [arr[minIdenx],arr[i]];
}
return arr
}
// 插入排序:每次排一个数组项,假设数组的第一项已经排序,接着,把第二项与第一项进行对比,第二项是该插入到第一项之前还是之后,第三项是该 插入到第一项之前还是第一项之后还是第三项
function insertionSort(arr) {
let len = arr.length;
let preIndex,current;
for(let i<len;i++) {
preIndex = i -1;
current = arr[i];
while (preIndex >=0 && arr[preIndex]>current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
// 归并排序:Mozilla Firefox 使用归并排序作为Array.prototype.sort的实现,而chrome使用快速排序的一个变体实现的,前面三种算法性能不好,但归并排序性能不错 算法复杂度O(nlog^n)
function mergeSort (arr) {
let len = arr.length;
if(len<2) {
return arr
}
let middle = Math.floor(len/2),
left = arr.slice(0,middle);
return merge(mergeSort(left),mergeSort(right));
}
function merge(left, right){
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
result.push(...left);
result.push(...right);
return result;
//堆排序:堆排序把数组当中二叉树来排序而得名。
var len;
function buildMaxHeap(arr) {
len = arr.length;
for(let i = Math.floor(len/2;i>=0;i--){
heapify(arr,i)
}
}
function heapify(arr,i) {
let left = 2* i+1;
let right = 2*i+2;
let largest = i;
if(left<len && arr[left]> arr[largest]) {
largest = left;
}
if(right < len && arr[right]>arr[largest]){
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, largest);
}
}
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
[arr[0],arr[i]]=[arr[i],arr[0]];
len--;
heapify(arr, 0);
}
return arr;
}