常见排序算法

1. 冒泡排序

   1. 按顺序依次两两对比,把大的放到后面,直到最后的数最大.
   2. 将最后的数固定,再重新对比n-1的数.

const arr = [1,20,30,10,50,100,999]

function bubbleSort(arr){
    for(let i = 0;i<arr.length - 1;i++){
        for(let j = 0;j < arr.length - i -1;j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1)
            }
        }
    }
}

function swap(arr,n,m){
    let temp = arr[n]
    arr[n] = arr[m]
    arr[m] = temp
}

2. 选择排序

   1. 找出数列里最小的数,将其移到第一位.
   2. 再从n+1开始,依次排序.

function selectionSort(arr){
    for(let i = 0;i < arr.length - 1;i++){
        let index = i;
        for(let j = i+1;j < arr.length;j++){
            if(arr[index] > arr[j]){
                index = j
            }
        }
        swap(arr,i,index)
    }
}

3. 插入排序
   1.建立一个空数组,从原数组中抽出一个数插入到空数组,形成有序数组
   2.每次将原的一个数插入到有序的数组中去

function insertSort(arr){
    for(let i= 0;i < arr.length;i++){
        let temp = arr[i]
        for(let j = 0;j < i;j++){
            if(temp < arr[j] && j === 0){
                arr.splice(i,1)
                arr.unshift(temp)
                break
            }else  if(temp > arr[j] && temp < arr[j+1] && j < i - 1){
                arr.splice(i,1)
                arr.splice(j+1,0,temp)
            }
        }
    }
}

4. 快排

   1. 先随机取一个数,将比这个数小的放左边,大的放右边.
   2. 左边和右边的数都用上面的步骤,继续分.
   3. 不断重复.

5. 归并排序

   1. 将相邻的两个数进行排序，形成n/2对，然后在每对合并，不断重复

6. 基数排序

   1. 比较个位大小，将数组的顺序变成按个位一次递增，之后比较十位，最后到最后一位.