排序算法

冒泡排序

  冒泡排序需要两个嵌套的循环. 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.

function bubbleSort(arr){
    for(var i =0;i<arr.length;i++){
        for(var j=0;j<arr.length-1-i;j++){
            if(arr[j]>arr[j+1]){
                var temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}
//<1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
//<2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
//<3>.针对所有的元素重复以上的步骤，除了最后一个；
//<4>.重复步骤1~3，直到排序完成

  传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

function superbubbleSort(arr){
            var low = 0
            var high = arr.length-1
            var temp
            var j 
            while(low < high){
                for(j=low;j<high;++j){
                    if(arr[j]>arr[j+1]){
                        temp = arr[j+1]
                        arr[j+1] = arr[j]
                        arr[j] = temp
                    }
                    //正向冒泡，取得最大值
                    --high
                    for(j=high;j>low;--j){
                            if(arr[j]<arr[j-1]){
                                temp = arr[j]
                                arr[j] = arr[j-1]
                                arr[j-1] = temp
                            }
                    }
                    //反向冒泡，找到最小值
                    ++low
                }
            }
            return arr
        }

选择排序

  选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

function selectSort(arr){
            var len = arr.length
            var minIndex
            var temp
            for(var i=0;i<len-1;i++){
                minIndex = i  
                for(var j= i+1;j<len;j++){
                    if(arr[j]<arr[minIndex]){  
                        minIndex = j    
                    }    
                }
                temp = arr[i]          
                arr[i] = arr[minIndex] 
                arr[minIndex] = temp
            }
            return arr
        }

插入排序

  插入排序--通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

function insertSort(arr){
            var len = arr.length
            var value
            var j
            
            for(var i=0;i<len;i++){
                value = arr[i] 
                for(j = i-1;j>=0 && arr[j]>value;j--){
                    arr[j+1] = arr[j] 
                }
                arr[j+1] = value
            }
            return arr
        }

avatar

快速排序

  它的基本思想很简单：先确定一个“支点”（pivot），将所有小于“支点”的值都放在该点的左侧，大于“支点”的值都放在该点的右侧，然后对左右两侧不断重复这个过程，直到所有排序完成

image.png
image.png
image.png
image.png
image.png

function quickSort(arr){
            if(arr.length <= 1){return arr}
            var pivotIndex = Math.floor(arr.length/2) //基点
            var pivot = arr.splice(pivotIndex,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))
        }