数组排序
1. 冒泡排序
- 嵌套遍历，相邻元素两两比较交换排序
原理
从左到右，相邻元素进行比较，如果前一个元素值大于后一个元素值（正序），则交换，这样一轮下来，将最大的数在最右边冒泡出来。这样一轮一轮下来，最后实现从小到大排序。
动图演示：
代码实现
/**
* @description 冒泡排序
*/
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 改进冒泡排序 --- 使用标识，遍历过程中再没有交换过程了就停止遍历，即所有排序已提前完成
function bubbleSort1(arr) {
for (let i = 0; i < arr.length; i++) {
// 提前退出冒泡循环的标识位
let flag = false;
2. 选择排序
- 嵌套遍历，查找到未排序中最小的，放在已排序序列的末尾，重复该操作
原理
从未排序的序列中找到最大（或最小的）放在已排序序列的末尾（为空则放在起始位置），重复该操作，直到所有数据都已放入已排序序列中。
动图演示：
代码实现
/**
* @description 选择排序
*/
function selectionSort(arr) {
let length = arr.length,
indexMin;
for (let i = 0; i < length - 1; i++) {
indexMin = i;
for (let j = i; j < length; j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
let temp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = temp;
}
}
}
3. 归并排序
原理
它采用了分治策略，将数组分成 2 个较小的数组，然后每个数组再分成两个更小的数组，直至每个数组里只包含一个元素，然后将小数组不断的合并成较大的数组，直至只剩下一个数组，就是排序完成后的数组序列。
实现步骤
- 将原始序列平分成两个小数组
- 判断小数组长度是否为 1，不为 1 则继续分裂
- 原始数组被分称了长度为 1 的多个小数组，然后合并相邻小数组（有序合并）
- 不断合并小数组，直到合并称一个数组，则为排序后的数组序列
4. 快排
- 随机取一个数组中的值，进行一次排序(小于该数的放在左侧，大于在右侧)；以该值所在位置划分两个数组重复之前操作
原理
和归并排序一致，它也使用了分治策略的思想，它也将数组分成一个个小数组，但与归并不同的是，它实际上并没有将它们分隔开。
代码实现
//快排
function quickSort(arr) {
quick(arr, 0, arr.length - 1);
}
function quick(arr, left, right) {
if (left < right) {
//划分数组
let index = partition(arr, left, right); //划分的元素下标
if (left < index - 1) {
quick(arr, left, index - 1);
}
if (index < right) {
quick(arr, index, right);
}
}
}
function partition(arr, left, right) {
//随机取一个数, 或默认取第一个
// var value = arr[left],
var value = arr[Math.floor(Math.random() * (right - left + 1)) + left],
i = left,
j = right;
while (i <= j) {
while (arr[i] < value) {
i++;
}
while (arr[j] > value) {
j--;
}
// console.log(i, j, arr);
if (i <= j) {
changeVal(arr, i, j);
i++;
j--;
}
}
// console.log(arr, i);
return i;
}
//交换
function changeVal(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// var arr = [1, 3, 19, 6, 8, 2, 8, 21, 11, 6, 4, 9, 1];
var arr = [1, 5, 2, 6, 7, 3];
// partition(arr, 0, arr.length - 1);
quickSort(arr);
console.log(arr);