常见排序算法的实现和比较

发表于 | 分类于

1. 冒泡排序

比较相邻的两个元素,前一个比后一个大则交换，一趟下来，最大的就冒到最后面了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var testArray=[3,1,5,3,4,67,2];
function bubbleSort (argument) {
    for(var i=0;i<argument.length;i++){
        for(var j=0;j<argument.length-i;j++){
            if(argument[j]>argument[j+1]){
                var temp=argument[j];
                argument[j]=argument[j+1];
                argument[j+1]=temp;
            }
        }
    }
    return argument;
}
alert(bubbleSort(testArray));

*冒泡排序是稳定的，因为只有前一个比后一个大时才交换位置，相等不交换，时间复杂度是O(n^2)*

2. 选择排序

从第二个开始，都和第一个比，比第一个小则交换位置，一趟下来，最小放在第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
function selectSort (argument) {
    for(var i = 0; i < argument.length; i++) {
        for(var j = i+1; j < argument.length; j++) {
            if(argument[j] < argument[i]) {
                var temp = argument[j];
                argument[j] = argument[i];
                argument[i] = temp;
            }
        }
    }
    return argument;
}

选择排序不是稳定的，比如5 8 5 2 9 第一遍的时候一个5会和2交换,两个5的顺序就被破坏了.时间复杂度是O(n^2)

3. 快速排序

采用分治的思想，一趟排序后就把比标准值小的放在标准值左边，比标准值大的就放在标准值右边。然后再对这标准值左右两半采用同样的方法。过程为:确定一个标准值key，比如为arr[right],然后两边往中间找，只要比key值小，left++,left就会停留在第一个比key大的值，同理，right会停留在第一个比key小的值，这两个值互相交换，直到left>=right，我这里标准值是在右边(左边),则这时标准值和最后的right(left)位交换,则实现了一趟排序。

  • 方法1 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    function quickSort(arr, left, right) {
            if(left >= right) {
                return ;
            }
            var key = arr[right];
            var lp = left;
            var rp = right;
            while(lp < rp) {
                while(arr[lp] <= key && lp < rp) {
                    lp++;
                }
                while(arr[rp] >= key && lp < rp) {
                    rp--;
                }
                var temp = arr[lp];
                arr[lp] = arr[rp];
                arr[rp] = temp;
            }
            temp = arr[right];
            arr[right] = arr[rp];
            arr[rp] = temp;
            quickSort(arr, left, lp-1);
            quickSort(arr, rp+1, right);
            return arr;
    }

时间复制度为O(nlogn),不稳定
参考文章

  • 方法2(浪费空间，但是思路更清晰)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function quickSort(arr) {
        if (arr.length <= 1) {
            return arr;
        }
        var middle = Math.floor(arr.length / 2);
        var tag = arr.splice(middle, 1)[0];
        var left = [];
        var right = [];
        //console.log(arr);
        for(var i = 0; i < arr.length; i++) {
            if(arr[i] <= tag) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([tag], quickSort(right));
    }
    var arr = [3,5,1,8,2,52,423,4235,234,1,1,32];
    console.log(quickSort(arr));

4. 直接插入排序

默认左边是已经排好序的，从第一个开始，两层循环，只要左边的大于右边的就向右移动一个位置，直到出现小于右边第一个数的那个数出现，此时arr[j] = arr[i]

1
2
3
4
5
6
7
8
9
10
11
12
var a = [9,5,12,7,8,10,2]
function insertSort(arr) {
    for(var i = 1; i < arr.length; i++) {
        var temp = arr[i];
        for(var j = i-1; j >= 0 && arr[j] > temp; j--) {
            arr[j+1] = a[j];
        }
        arr[j + 1] = temp;
    }
    return arr
}
console.log(insertSort(a))

时间复杂度为最好的情况是原始数据都已经全部排好序，while循环执行次数是0,时间复复杂度是O(n),最坏的情况是倒序，则时间复杂度是O(n^2),这个排序是稳定的

5. 希尔排序

是分组进行直接插入排序。因为分组后，没组内是越接近与有序，所以直接插入排序会更快，所以整体的时间复杂度是优于直接插入排序的。

6. 堆排序

先创建最大堆，然后把栈顶元素与当前最大堆的最后一个元素交换，最大堆元素个数减一，判断交换元素后的堆是不是最大堆了，如果不是，重建最大堆，然后重复第一步即将栈顶元素和最后一个元素交换。