排序算法

20130801171021937.jpg

动画演示

var arr = generateRandomArr(50);

maopao(arr);

select(arr);

insert_sort(arr);

arr = quick_sort(arr);

console.log(arr);

// 产生随机数
function generateRandomArr(n){
    let arr = [];
    let temp;

    for(let i = 0; i < n; i++){
        temp = Math.round(Math.random()*1000);
        arr.push(temp);
    }

    console.log(arr)
    return arr;    
}

冒泡排序

function maopao(arr){   

    for(let j = arr.length-1; j > 0; j--){
    
        let temp;
        for(let i = 0; i < j; i++){

            if(arr[i] > arr[i+1]){
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }  
}

选择排序

1. 在未排序序列中找到最小元素，存放到排序序列的起始位置，
2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
3. 重复步骤2

function select(arr){
    for(let i = 0; i < arr.length; i++){
        let index = i;
        for(let j = i+1; j < arr.length; j++){
            if(arr[index] > arr[j]){   // 找出最小值，从小到大排序
                index = j;
            }
        }

        if(index !== i){
            var temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

插入排序

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

function insert_sort(arr){
    for(let i = 1; i < arr.length; i ++){
        let temp = arr[i];
        for(let j = i - 1; j >= 0; j--){
            if(temp < arr[j]){                
                arr[j+1] = arr[j];
            }else{
                arr[j+1] = temp;
            }
        }
    }
}

快速排序

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quick_sort(arr){  
    if(arr.length <= 1) return arr;
    let pivotIndex = Math.floor(arr.length / 2) ;
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++){
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quick_sort(left).concat(pivot, quick_sort(right));
}