1. 冒泡排序
var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
for(let i = 0;i<arr.length-1;i++){
for(let j = 0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
let temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp
}
}
}
return arr
}
sort(arr)
console.log(arr);
2. 插入排序
var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
for(var i =1;i<arr.length;i++){
var val = arr[i];
var last = i-1;
while(last>=0 && arr[last]>val){
arr[last+1] = arr[last]
last--
}
arr[last+1] = val
}
return arr
}
sort(arr)
console.log(arr);
3. 快速排序
var arr = [1,56,9,6,3,5,8,2]
function quickSort(arr){
if(arr.length<2){
return arr
}
var mid = Math.floor(arr.length/2)
var pivot = arr.splice(mid,1)[0]
var left = [];
var right = [];
for(var i = 0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(pivot,quickSort(right))
}
console.log(quickSort(arr));
4. 归并排序
var arr = [1,56,9,6,3,5,8,2];
function mergeSort(arr) {
var len = arr.length
if(len<2){
return arr
}
var mid = Math.floor(arr.length/2)
var left = arr.slice(0,mid)
var right = arr.slice(mid)
return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right) {
var result = []
while(left.length>0 && right.length>0){
if(left[0]>right[0]){
result.push(right.shift())
} else {
result.push(left.shift())
}
}
while(left.length){
result.push(left.shift())
}
while(right.length){
result.push(right.shift())
}
arr = result
return arr
}
mergeSort(arr)
console.log(arr);
5. 希尔排序
var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
var gap = arr.length
for(gap = Math.floor(arr.length/2);gap>0;gap = Math.floor(gap/2)){
for(var i=gap;i<arr.length;i++){
var val = arr[i];
var j = i;
while(j-gap>=0 && arr[j-gap]>val){
arr[j] = arr[j-gap]
j = j-gap
}
arr[j] = val
}
}
return arr
}
sort(arr)
console.log(arr);
var arr = [1,56,9,6,3,5,8,2]
var len;
function buildMaxHeap(arr) {
len = arr.length
for(var i = 0;i<Math.floor(arr.length/2);i++){
heapify(arr,i)
}
}
function heapify(arr,i){
var left = i*2+1;
var right = i*2+2;
var largest = i;
if(left<len && arr[left]>arr[largest]){
largest = left
}
if(right<len && arr[right]>arr[largest]){
largest = right
}
if(largest !== i){
swap(arr,i,largest)
heapify(arr,largest)
}
}
function swap(arr,i,j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp
}
function heapSort(arr){
buildMaxHeap(arr)
for(var i = arr.length-1;i>=0;i--){
len-=1;
swap(arr,0,i)
heapify(arr,0)
}
return arr
}
console.log(heapSort(arr));
7. 计数排序
var arr = [1,56,9,6,3,5,8,2];
function countingSort(arr, maxValue){
var bucket = new Array(maxValue+1)
var index = 0
for(var i =0;i<arr.length;i++){
if(!bucket[arr[i]]){
bucket[arr[i]] = 0
}
bucket[arr[i]]++
}
for(var j = 0;j<bucket.length;j++){
while(bucket[j]>0){
arr[index++] = j
bucket[j]--
}
}
return arr
}
console.log(countingSort(arr,56));
8. 选择排序
var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
for(let i =0;i<arr.length-1;i++){
var index
let min = i
for(let j = i+1;j<arr.length;j++){
if(arr[j]<arr[min]){
min = j
}
}
var temp = arr[i];
arr[i] = arr[min];
arr[min] = temp
}
return arr
}
sort(arr)
console.log(arr);
网友评论