关于排序的三种算法

  • 算法

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 let bubbleSort = function (arr:number[]):number[]{
    let temp:number = 0;
    for(let i = 0;i<arr.length;i++){
        for(let j = 0;j<arr.length;j++){
            if(arr[i]<arr[j]){
                let temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    return arr; 
}
let result = bubbleSort([4,5,6,7,2,9,7,9,7,56,45,4,34,3,3,1]);

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let selectSort = function (arr:number[]):number[]{
    let resultArr:number[] = [];
    let recursion = function (){
        if(arr.length===0){
            return;
        }
        let minValue:number = Math.min(...arr);
        console.log(minValue);
        let index = arr.indexOf(minValue);
        minValue = arr.splice(index,1)[0];
        resultArr.push(minValue);
        recursion();
    }
    recursion();
    return resultArr; 
}

let result = selectSort([4,5,6,7,2,9,7,9,7,56,45,4,34,3,3,1]);

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let quickSort = function (arr:number[]):number[]{
    let sort = function (arr:number[]):number[]{
        if(arr.length<2){
            return arr;
        }
        let pv:number = arr.splice(0,1)[0];
        let leftArr:number[] = [];
        let rightArr:number[] = [];
        arr.forEach(v=>{
            if(v<=pv){
                leftArr.push(v);
            }
            if(v>pv){
                rightArr.push(v);
            }
        })
        return sort(leftArr).concat(pv,sort(rightArr));
    }

    return sort(arr);

}

let result = quickSort([4,5,6,7,2,9,7,9,7,56,45,4,34,3,3,1]);