JavaScript对几个排序算法的实现

分手后的思念是犯贱 2022-06-03 07:46 163阅读 0赞

**冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序的代码实现**

var arr=[2,1,3,6,5,7,4,9,8];

*  **冒泡排序**

![bubble][]

/** * 冒泡排序： * 每次都要从头开始比，两两相比。 */
    function bubble(arr) {
        var temp;
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            for (var j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    
    arr = [2, 6, 9, 3, 5, 1, 7, 8, 4];
    console.log(bubble(arr)); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

*  选择排序
    
    ![select][]

/** * 选择排序： * 从一个元素开始，选择一个符合条件的与之交换 */
    function selectSort(arr) {
        var minVal, temp;
        for (var i = 0; i < arr.length; i++) {
            minVal = i;
            for (var j = i + 1; j < arr.length; j++) {
                if (arr[minVal] > arr[j]) {
                    minVal = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minVal];
            arr[minVal] = temp;
        }
        return arr;
    }
    arr = [2, 6, 9, 3, 5, 1, 7, 8, 4];
    console.log(selectSort(arr)); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

*  插入排序  
    ![insertion][]

/** * 插入排序 * 将当前元素与前一元素进行对比，符合规则就与之交换，不符合继续向前比较，直到符合。 * 扑克牌排牌 */
    function insertion(arr) {
        var proIndex, temp;
        for (var i = 1; i < arr.length; i++) {
            proIndex = i - 1;
            temp = arr[i];
            while (proIndex >= 0 && arr[proIndex] > temp) {
                arr[proIndex + 1] = arr[proIndex];
                proIndex--;
            }
            arr[proIndex + 1] = temp;
        }
        return arr;
    }
    
    arr = [2, 6, 9, 3, 5, 1, 7, 8, 4];
    console.log(insertion(arr)); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

*  快速排序  
    ![quickSort][]

/** * 快速排序的js实现 * 快速排序思想： * 把数组分成两部分，取中间数组坐标为中间值得元素，新建两个数组left[]和right[] * 遍历数组，与这个中间数比较，小的放在left[],大的放在right[] * 使用concat（）将left[]、中间数、right[]连接返回。 */
    
    function quickSort(arr) {
        if (arr.length <= 1) { return arr; }
        var num = Math.floor(arr.length / 2);
        var numVal = arr.splice(num, 1)[0];
        var left = [];
        var right = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < numVal) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([numVal], quickSort(right));
    }
    
    var arr = [2, 6, 9, 3, 5, 1, 7, 8, 4];
    console.log(quickSort(arr)); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

动态演示图来至于[微信公众号“前端大全”的一片文章][Link 1]。

[bubble]: /images/20220603/9a179ece90c740db8724c5180cb6614c.png
[select]: /images/20220603/e22abdf4c3484f87a6b638fbfeaa558f.png
[insertion]: /images/20220603/c40c149b08674600b5c9df037a23ecd0.png
[quickSort]: /images/20220603/91562a6c954144ac8d8487a498080b00.png
[Link 1]: http://mp.weixin.qq.com/s/rh8CI7LgoXy8yI7AgUYc0g