1.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {        // 相邻元素两两对比
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

2.插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

3.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

4.快速排序

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
26
27
28
29
30
31
32
33
34
function quickSort(arr, left, right) {
    let len = arr.length,
        partitionIndex,
        left = typeof left != 'undefined' ? left : 0,
        right = typeof right != 'undefined' ? right : len - 1;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
 
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}
 
function partition(arr, left, right) {
    let pivot = arr[right],
        partitionIndex = left;
 
    for (let i = left; i < right; i++) {
        if (arr[i] < pivot) {
            swap(arr, i, partitionIndex);
            partitionIndex++;
        }
    }
    swap(arr, right, partitionIndex);
    return partitionIndex;
}
 
function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

5.归并排序

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
26
function mergeSort(arr) {
    let len = arr.length;
    if (len < 2) {
        return arr;
    }
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length)
        result.push(left.shift());
    while (right.length)
        result.push(right.shift());
    return result;
}

6.堆排序

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function heapSort(arr) {
    // 建堆
    buildHeap(arr);

    let len = arr.length;
    let temp;

    // 堆调整排序
    for (let i = len - 1; i > 0; i--) {
        // 将当前未排序序列中最大（或最小）元素放到序列的起始位置
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新对剩余未排序元素进行最大堆调整
        heapify(arr, 0, i);
    }
    return arr;
}

// 建堆
function buildHeap(arr) {
    let len = arr.length;
    // 从最后一个非叶子节点开始调整
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(arr, i, len);
    }
}

// 堆调整
function heapify(arr, i, len) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        let swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 递归调整子树
        heapify(arr, largest, len);
    }
}