排序算法（一）（选择，插入，冒泡，归并，快速）

发表于 | 更新于: | 分类于 | | 阅读次数:
字数统计: 1.2k字 | 阅读时长 ≈ 5分钟
下面是选择排序，插入排序，冒泡排序，归并排序，快速排序五种算法的原理以及具体的代码实现

选择排序

  1. 从数组中选取一个元素 item，初次为第一个元素
  2. 在 item 剩余的元素中找到最小的元素
  3. 将这个最小的元素与 item 交换位置
  4. 重复 1，2， 3的过程，一直到数组结束
示意图如下代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectSort(arr) {
    for (let i = 0; i < arr.length; i ++) {
        let minIdx = i;
        let temp = arr[i];
        // 从剩余的元素中查找到最小的元素
        for (let j = i + 1; j < arr.length; j ++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        arr[i] = arr[minIdx];
        arr[minIdx] = temp
    }
    return arr;
}

插入排序

  1. 从数组中的第二个元素开始抽取元素 item
  2. 将 item 与 item 左边第一个元素进行比较，如果左边的元素大于item，那么继续与左边第二个元素继续比较，直到遇到不大于item 的元素，然后将这个元素插入到 item 的右边
  3. 继续选取第 3， 4， 5 个元素， 重复 2 过程， 直到数组结束
示意图如下代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function insertSort(arr) {
    for (let i = 1; i < arr.length; i ++) {
        let k = i;
        let item = arr[i]
        while (k >= 0) {
            k --;
            // 当找到比当前要插入的元素小的元素时
            // 将插入元素插入到小元素的右边
            // 或者 k < 0 时，这个时候表示找到最左边
            // 都没有找到比 arr[i] 还要小的元素
            if (item > arr[k] || k < 0) {
                arr[k + 1] = item;
                break
            } else {
                // 整体向右边移
                arr[k + 1] = arr[k]
            }
        }
    }
    return arr;
}

冒泡排序

  1. 将第一个元素与第二个元素进行比较，如果第一个元素比第二个大，那么交换他们的位置，接着继续比较第二个元素和第三个元素
  2. 经过一轮比较之后，现在最右边的元素是数组里面最大的元素
  3. 除去最右边已经筛选后的元素之后，再对剩余的元素执行 1 过程
示意图如下代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(arr, sortedIndex = arr.length - 1) {
    let i = 0;
    while (i < arr.length - 1) {
        let nextIdx = i + 1;
        if (arr[i] > arr[nextIdx]) {
            let temp = arr[i]
            arr[i] = arr[nextIdx]
            arr[nextIdx] = temp
        }
        i ++
    }
    sortedIndex --
    return  sortedIndex === 0 ? arr : bubbleSort(arr, sortedIndex)
}

归并排序

  1. 将大数组拆分为小数组，再拆分小数组，一直拆分到数组内只有一个元素
  2. 对于小数组内的元素进行排序操作，然后将小数组进行组合
  3. 最后组合的大数组为已经排好序的数组
示意图如下：代码如下：
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
function merge(arr, left, mid, right) {
	let a = new Array(right - left + 1)
	let i = left;
	let j = mid + 1;
	let k = 0;
  // 将两个数组进行组合
  // 这两个数组分别为 arr[left, ... mid] 以及 arr[mid + 1, ... right]
	while(i <= mid && j <= right) {
		if (arr[i] < arr[j]) {
			a[k++] = arr[i++]
		} else {
			a[k++] = arr[j++]
		}
	}
	// 当还有剩余的 i 数组元素时
  // 压入数组中
	while(i <= mid) {
		a[k++] = a[i++]
	}
	// 当还有剩余的 j 数组元素时
  // 同样压入数组中
	while(j <= right) {
		a[k++] = a[j++]
	}
	// 将排好序的 a 数组复制到 arr 中
  // 这里的数组 a 已经排好序了
	for(i = 0; i < k; i ++) {
		arr[left ++] = a[i]
	}
}

function mergeSort(arr, left, right) {
	if (left !== right) {
		let mid = Math.floor((right + left) / 2)
    // 对于左边的元素进行排序
		arr = mergeSort(arr, left, mid)
    // 对于右边的元素进行排序
    arr = mergeSort(arr, mid + 1, right)
		merge(arr, left, mid, right)
	}
}

快速排序

  1. 选取数组中的一个元素为中轴元素，将数组中所有小于中轴元素的元素放在左边，所有大于或者等于中轴元素的元素放在右边
  2. 进行完过程 1 之后，这时候中轴元素的位置已经确定了，这个元素左边都是比它小的元素，右边都是比它大的元素
  3. 对于中轴元素左右两边的元素再分别进行 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
26
27
28
29
30
31
function partition(arr, left, right) {
    let pivot = arr[left]
    let i = left + 1;
    let j = right;
    while (true) {
        while(i <= j && arr[i] <= pivot) {
            i ++;
        }
        while(i <= j && arr[j] >= pivot) {
            j --;
        }
        if (i >= j) {
            break
        }
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
    arr[left] = arr[j]
    arr[j] = pivot
    return j
}

function quickSort(arr, left, right) {
    if (left < right) {
        let mid = partition(arr, left, right)
        arr = quickSort(arr, left, mid - 1)
        arr = quickSort(arr, mid + 1, right)
    }
    return arr
}