前端中的数据结构-排序

99 乘法表

在写排序之前，先写一个 99 乘法表

document.write(`99乘法表`)
document.write(`<table>`)
for (let i = 1; i < 10; i++) {
    document.write(`<tr>`)
    for (let j = 1; j <= i; j++) {
        document.write(`<td style="padding:5px">
        ${i} * ${j} = ${i * j}
        </td>`)
    }
    document.write(`</tr>`)
}
document.write(`</table>`)

冒泡排序

它是最慢的排序算法之一，数据值就会像气泡一样从数组的一端漂浮到另一端

let arr = [2, 1, 7, 3, 5]

function bubbleSort(arr) {
    for (let outer = 0, len = arr.length; outer < len; outer++) {
        for (let inner = 0, len = arr.length - outer; inner < len; inner++) {
            if (arr[inner + 1] < arr[inner]) {
                [arr[inner], arr[inner + 1]] = [arr[inner + 1], arr[inner]]
            }
        }
    }
    return arr;
}

console.log(bubbleSort(arr))

选择排序

实现思路：从数组的开头开始，将第一个元素同其他数组元素进行对比，较最小的元素会被放到数组的第一个位置，再从第二个位置继续。

let arr = [3, 1, 55, 6, 9, 2, 8, 10]

function selectSort(arr) {
    for (let outer = 0; outer < arr.length - 1; outer++) {
        for (let inner = outer + 1; inner < arr.length; inner++) {
            if (arr[outer] > arr[inner]) {
                [arr[outer], arr[inner]] = [arr[inner], arr[outer]];
            }
        }
    }
    return arr;
}
console.log(selectSort(arr))

插入排序就像打牌一样

插入排序是稳定的排序，处理小规模数据或者基本有序数据时，十分高效

 function insertSort(arr) {
    for (let outer = 1; outer < arr.length; outer++) {
        for (let inner = outer; inner > 0 && arr[inner] < arr[inner - 1]; inner--) {
            [arr[inner], arr[inner - 1]] = [arr[inner - 1], arr[inner]]
        }
    }
    return arr;
}
var arr = [7, 3, 8, 4, 9, 11];
console.log(insertSort(arr))

while 实现 😢

 function insert(arr) {
    for (let outer = 1; outer < arr.length; outer++) {
        let inner = outer;
        while (inner > 0 && arr[inner] < arr[inner - 1]) {
            [arr[inner], arr[inner - 1]] = [arr[inner - 1], arr[inner]]
            inner--;
        }
    }
    return arr;
}
var arr = [7, 3, 8, 4, 9, 11];
console.log(insert(arr))

快速排序

在列表中选择一个元素作为基准值，排序围绕这个基准值进行，将列表中小于基准值的放入数组底部大于放顶部。

function quickSort(arr) {
    if (arr.length === 0) {
        return []
    }
    let base = arr[0],
        less = [],
        big = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > base) {
            big.push(arr[i])
        } else {
            less.push(arr[i])
        }
    }
    return quickSort(less).concat(base, quickSort(big))
}
var arr = [7, 3, 8, 4, 9, 11];
console.log(quickSort(arr))

希尔排序

它会首先比较较远的元素而非相邻的元素。让元素尽快回到正确的位置。通过定义一个间隔序列来表示在排序过程中进行比较的元素间。公开的间隔序列是 701，301，132，57，23，10，4，1.(质数)。

function shellSort(array) {
    // 定义间隔序列，这里写死了，可以动态定义
    const gaps = [5, 3, 1];
    for (let index = 0; index < gaps.length; index++) {
        const gap = gaps[index];

        for (let outer = gap; outer < array.length; outer++) {
            // 检查的数字
            const temp = array[outer];
            for (
                let inner = outer - gap;
                // 如果比之前的 gap 小，就交换一下，直到交换到第一个 gap 处
                inner >= 0 && array[inner] > temp; inner -= gap
            ) {
                [array[inner], array[inner + gap]] = [array[inner + gap], array[inner]]
                swap(array, inner, inner + gap);
            }
        }
    }
    return array;
}

归并排序

把一系列排好序的子序列合并成一个大的完整有序序列。

// 归并排序算法
function mergeSort(array) {
  // 避免污染传入的数组
  const temp = [...array];
  splitArray(temp, 0, array.length - 1);
  return temp;
}

// 将大数组拆分成两个小数组
function splitArray(array, start, end) {
  if (start < end) {
    const mid = Math.floor((start + end) / 2);
    splitArray(array, 0, mid);
    splitArray(array, mid + 1, end);
    mergeArray(array, start, mid, end);
  }
}

// 合并两个排序好的数组
function mergeArray(array, start, mid, end) {
  var i = start;
  var j = mid + 1;
  var k = 0;
  var temp = [];
  while (i <= mid && j <= end) {
    if (array[i] <= array[j]) {
      temp[k] = array[i];
      i++;
    } else {
      temp[k] = array[j];
      j++;
    }
    k++;
  }

  while (i <= mid) {
    temp[k] = array[i];
    i++;
    k++;
  }

  while (j <= end) {
    temp[k] = array[j];
    j++;
    k++;
  }

  for (let index = 0; index < k; index++) {
    array[index + start] = temp[index];
  }
}
var arr = [2, 3, 7, 9, 8, 5, 4, 6, 1];
console.log('原始数组：', arr);
const result = mergeSort(arr);
console.log('排列后数组：', result);

总结

来张图一目了然 😊