JS实现排序算法

看动画学排序

冒泡排序

        // 冒泡排序
        let bubbleSort = (arr) => {
            if (arr.length <= 1) {
                return arr;
            }
            for (let i = 0; i < arr.length -1; i++) {
                for (let j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        let temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            return arr;
        }
        console.log('bubbleSort', bubbleSort([2, 3, 11, 6, -3]));

选择排序

遍历数组n次，每次将最小的数拿出来按顺序放到新数组中返回

 // 选择排序
        let getMinIndex = (arr) => {
            if (arr.length === 0) {
                return;
            }
            let minIndex = 0;
            for (let i=0; i<arr.length; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
            }
            return minIndex;
        }
        let swap = (arr, i, j) => {
            if (i !== j) {
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        let selectSort = (arr) => {
            if (arr.length <= 1) {
                return arr;
            }
            for (let i=0; i<arr.length-1; i++) {
                swap(arr, i, getMinIndex(arr.slice(i)) + i);
            }
            return arr;
        }
        console.log('selectSort', selectSort([2, 3, 11, 6, -3]));

快速排序

从数组中间取一个数，遍历整个数组，比这个数小的放左边，比这个数大的放右边

 // 快速排序
        let quickSort = (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 quickSort(left).concat([pivot], quickSort(right));
        }
        console.log('quickSort', quickSort([2, 3, 11, 6, -3]));

归并排序

将数组从中间分成左右两个数组，分别排序后合并

// 归并排序
        let mergeSort = (arr) => {
            let k = arr.length;
            if (k <= 1) {
                return arr;
            }
            let left = arr.slice(0, Math.floor(k/2));
            let right = arr.slice(Math.floor(k/2));
            return merge(mergeSort(left), mergeSort(right));
        }
        let merge = (a, b) => {
            if (a.length === 0) {
                return b;
            }
            if (b.length === 0) {
                return a;
            }
            return a[0] > b[0]? [b[0]].concat(merge(a, b.slice(1))) : 
                                [a[0]].concat(merge(a.slice(1), b));
        }
        console.log('mergeSort', mergeSort([2, 3, 11, 6, -3]));

计数排序

使用哈希表将每个数出现的次数保存起来，再遍历哈希表排序

        // 计数排序, 只能排整数数组
        let countSort = (arr) => {
            if (arr.length <= 1) {
                return arr;
            }
            let hashTable = {},
                max = arr[0],
                min = arr[0],
                result = [];
            for (let i = 0; i < arr.length; i++) {
                // console.log(i, arr[1]);
                if (!(arr[i] in hashTable)) {
                    hashTable[arr[i]] = 1;
                } else {
                    hashTable[arr[i]] += 1;
                }
                if (arr[i] > max) {
                    max = arr[i];
                }
                if (arr[i] < min) {
                    min = arr[i];
                }
            }
                // 遍历哈希表
                for (let i = min; i <= max; i++) {
                    if (i in hashTable) {
                        // console.log('2',i)
                        for (let j = 0; j < hashTable[i]; j++) {
                            result.push(i);
                            // console.log(i)
                        }
                    }
                }
            return result;
        }
        console.log('countSort', countSort([2, 3, 11, 6, -3]));

插入排序（待更新）

希尔排序（待更新）

基数排序（待更新）

堆排序（待更新）

时间空间复杂度