介绍一下十大经典排序算法及其复杂度
以下是十大经典排序算法及其时间复杂度的介绍：
冒泡排序（Bubble Sort）： 冒泡排序是一种简单的排序算法，它通过反复交换相邻的元素将最大的元素逐渐移动到末尾。时间复杂度为 O(n^2)。
选择排序（Selection Sort）： 选择排序是一种简单直观的排序算法，每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。时间复杂度为 O(n^2)。
插入排序（Insertion Sort）： 插入排序通过构建有序序列，对于未排序的元素逐个插入到已排序的部分中。时间复杂度为 O(n^2)，但在部分有序的情况下性能较好。
希尔排序（Shell Sort）： 希尔排序是一种改进的插入排序，它通过将序列分割成多个子序列进行插入排序，最后合并成一个有序序列。时间复杂度为 O(n log n)。
归并排序（Merge Sort）： 归并排序采用分治法，将待排序序列分为两部分，分别进行排序，然后合并两个有序的子序列。时间复杂度为 O(n log n)。
快速排序（Quick Sort）： 快速排序也是一种分治算法，通过选择一个基准元素将序列分为两部分，左边的元素小于基准，右边的元素大于基准，然后递归地对两部分进行排序。时间复杂度为 O(n log n)，但在最坏情况下可能达到 O(n^2)。
堆排序（Heap Sort）： 堆排序利用堆的数据结构，将待排序序列构建成一个最大堆（或最小堆），然后依次取出堆顶元素并调整堆，得到有序序列。时间复杂度为 O(n log n)。
计数排序（Counting Sort）： 计数排序是一种非比较排序算法，它通过统计序列中每个元素的出现次数，然后根据计数结果重新构建有序序列。时间复杂度为 O(n + k)，其中 k 是序列中元素的取值范围。
桶排序（Bucket Sort）： 桶排序将元素分配到不同的桶中，对每个桶中的元素进行排序，然后按顺序将各个桶的元素合并得到有序序列。时间复杂度取决于桶的数量和元素的分布情况。
基数排序（Radix Sort）： 基数排序是一种按照位数进行排序的算法，它将待排序序列按照个位、十位、百位等依次排序，最终得到有序序列。时间复杂度为 O(d * (n + k))，其中 d 是最大元素的位数，k 是基数。
这些排序算法具有不同的特点和适用场景，选择适当的排序算法取决于数据规模、数据分布和性能要求。
使用 JavaScript 实现一个冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
当输入一个数组，你可以使用 JavaScript 实现冒泡排序算法如下：
function bubbleSort(arr) {
const len = arr.length;
// 外循环：未排序区间为 [0, i]
for (let i = len - 1; i > 0; i--) {
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
从左到右，每一轮将最大的一个冒泡到最右边。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(bubbleSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过冒泡排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
当输入一个数组，你可以使用 JavaScript 实现选择排序算法如下：
function selectionSort(arr) {
var len = arr.length;
for (let i = 0; i < len - 1; i++) {
//这里len-1是因为下面j是从i+1开始的
var minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
}
return arr;
}
在上述代码中，selectionSort函数接受一个数组作为输入，并使用两层嵌套循环进行排序。外层循环控制当前需要找到最小值的位置，内层循环用于遍历剩余的未排序部分，找到最小元素的索引。然后，将当前位置的元素与最小元素进行交换，将最小元素放到正确的位置。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(selectionSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过选择排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
当输入一个数组，你可以使用 JavaScript 实现插入排序算法如下：
function insertionSort(arr) {
var len = arr.length;
for (let i = 1; i < len; i++) {
const current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
在上述代码中，insertionSort函数接受一个数组作为输入，并使用一个循环进行排序。循环从数组的第二个元素开始，将当前元素与前面已排序的部分进行比较。如果前面的元素大于当前元素，则将前面的元素后移一位，直到找到合适的位置插入当前元素。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(insertionSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过插入排序后，数组被排序为[2, 3, 4, 5, 8]。
TODO:使用 JavaScript 实现一个希尔排序（Shell Sort）
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第 4 版》的合著者 Robert Sedgewick 提出的。
当输入一个数组，你可以使用 JavaScript 实现希尔排序算法如下：
function shellSort(arr) {
var len = arr.length;
var gap = Math.floor(len / 2); // 初始化间隔值
while (gap > 0) {
for (var i = gap; i < len; i++) {
var current = arr[i];
var j = i;
while (j >= gap && arr[j - gap] > current) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = current;
}
gap = Math.floor(gap / 2); // 更新间隔值
}
return arr;
}
在上述代码中，shellSort函数接受一个数组作为输入，并使用希尔排序算法对数组进行排序。该算法通过不断缩小间隔值来对数组进行分组和插入排序，直到间隔值为 1 时完成最后一次排序。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(shellSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过希尔排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 路归并。
当输入一个数组，你可以使用 JavaScript 实现归并排序算法如下：
function mergeSort(arr) {
if (arr.length <= 1) {
return arr; // 当数组长度为1或更小时，直接返回
}
var mid = Math.floor(arr.length / 2); // 找到数组的中间位置
var left = arr.slice(0, mid); // 分割数组为左右两部分
var right = arr.slice(mid);
// 递归地对左右两部分进行归并排序
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
var i = 0;
var j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 将剩余的元素添加到结果数组中
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
在上述代码中，mergeSort函数接受一个数组作为输入，并使用归并排序算法对数组进行排序。该算法通过将数组分割成较小的部分，然后递归地对这些部分进行排序，最后将排序好的部分合并起来。
merge函数用于将两个已排序的数组合并为一个有序数组。它使用两个指针i和j分别指向左右两个数组的元素，比较两个指针所指的元素大小，将较小的元素添加到结果数组result中，并将相应指针向后移动。最后，将剩余的元素添加到结果数组中。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(mergeSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过归并排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
当输入一个数组，你可以使用 JavaScript 实现快速排序算法如下：
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // 当数组长度为1或更小时，直接返回
}
var pivotIndex = Math.floor(arr.length / 2); // 选择基准元素的索引
var pivot = arr[pivotIndex]; // 基准元素的值
var left = [];
var right = [];
// 将除基准元素外的元素分为左右两部分
for (var i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue; // 跳过基准元素
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归地对左右两部分进行快速排序，并将结果与基准元素合并
return quickSort(left).concat(pivot, quickSort(right));
}
在上述代码中，quickSort函数接受一个数组作为输入，并使用快速排序算法对数组进行排序。该算法选择一个基准元素，将数组分为小于基准元素和大于基准元素的两部分，然后递归地对这两部分进行排序，最后将结果合并起来。
以下是一个使用示例：
var array = [5, 3, 8, 4, 2];
console.log(quickSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过快速排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个堆排序（Heap Sort）
堆排序可以说是一种利用堆的概念来排序的选择排序。
当输入一个数组，你可以使用 JavaScript 实现堆排序算法如下：
function heapSort(arr) {
const len = arr.length;
// 建立最大堆
buildMaxHeap(arr, len);
// 依次取出堆顶元素并调整堆
for (let i = len - 1; i > 0; i--) {
swap(arr, 0, i); // 将堆顶元素与最后一个元素交换位置
heapify(arr, i, 0); // 调整新的堆顶元素
}
return arr;
}
function buildMaxHeap(arr, len) {
// 从最后一个非叶节点开始，依次进行堆化操作
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, len, i);
}
}
function heapify(arr, len, i) {
let largest = i; // 初始化最大元素的索引
const left = 2 * i + 1; // 左子节点的索引
const 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) {
swap(arr, i, largest);
heapify(arr, len, largest);
}
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
在上述代码中，heapSort函数接受一个数组作为输入，并使用堆排序算法对数组进行排序。该算法首先建立一个最大堆，然后依次从堆顶取出最大元素并调整堆，直到所有元素都被取出并排好序。
buildMaxHeap函数用于建立最大堆，从最后一个非叶节点开始，依次对每个节点进行堆化操作。
heapify函数用于将以节点i为根的子树进行堆化，它比较节点及其左右子节点的大小关系，并将最大的元素交换到父节点位置。如果交换发生，则继续对交换后的子树进行堆化。
swap函数是一个辅助函数，用于交换数组中两个元素的位置。
你可以使用以下方式调用heapSort函数：
const array = [5, 3, 8, 4, 2];
console.log(heapSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过堆排序后，数组被排序为[2, 3, 4, 5, 8]。
使用 JavaScript 实现一个计数排序（Counting Sort）
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于特定范围的整数排序。下面是使用 JavaScript 实现计数排序的代码：
function countingSort(arr) {
// 找出数组中的最大值和最小值
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// 创建计数数组，并初始化为0
const countArrayLength = max - min + 1;
const countArray = new Array(countArrayLength).fill(0);
// 统计每个元素出现的次数
for (let i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
// 根据计数数组重新排序原始数组
let sortedIndex = 0;
for (let i = 0; i < countArrayLength; i++) {
while (countArray[i] > 0) {
arr[sortedIndex] = i + min;
sortedIndex++;
countArray[i]--;
}
}
return arr;
}
在上述代码中，countingSort函数接受一个数组作为输入，并使用计数排序算法对数组进行排序。算法首先找到数组中的最小值和最大值，然后创建一个计数数组，用于统计每个元素出现的次数。接下来，根据计数数组重新排序原始数组，最后返回排序后的数组。
下面是使用示例：
const array = [5, 3, 8, 4, 2];
console.log(countingSort(array)); // 输出 [2, 3, 4, 5, 8]
在这个示例中，输入的数组是[5, 3, 8, 4, 2]。经过计数排序后，数组被排序为[2, 3, 4, 5, 8]。
需要注意的是，计数排序适用于特定范围的整数排序，因为它依赖于计数数组的长度，计数数组的长度等于最大元素与最小元素之差加 1。如果输入数组包含负数或浮点数，需要对算法进行适当的修改。
使用 JavaScript 实现一个桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
具体算法描述如下：
<1>.设置一个定量的数组当作空桶； <2>.遍历输入数据，并且把数据一个一个放到对应的桶里去； <3>.对每个不是空的桶进行排序； <4>.从不是空的桶里把排好序的数据拼接起来。
桶排序（Bucket Sort）是一种分布式排序算法，适用于一定范围内的浮点数排序。下面是使用 JavaScript 实现桶排序的代码：
function bucketSort(array, num) {
if (array.length <= 1) {
return array;
}
var len = array.length,
buckets = [],
result = [],
min = (max = array[0]),
regex = "/^[1-9]+[0-9]*$/",
space,
n = 0;
num = num || (num > 1 && regex.test(num) ? num : 10);
// 找出数组中的最大值和最小值
for (var i = 1; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
//每个桶的大小
space = (max - min + 1) / num;
for (var j = 0; j < len; j++) {
var index = Math.floor((array[j] - min) / space);
if (buckets[index]) {
// 非空桶，插入排序
var k = buckets[index].length - 1;
while (k >= 0 && buckets[index][k] > array[j]) {
buckets[index][k + 1] = buckets[index][k];
k--;
}
buckets[index][k + 1] = array[j];
} else {
//空桶，初始化
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
在上述代码中，bucketSort函数接受一个数组和桶的大小（可选参数，默认为 5）作为输入，并使用桶排序算法对数组进行排序。算法首先找到数组中的最小值和最大值，然后根据桶的大小计算桶的数量，并创建一个二维数组 buckets 来存储桶。接下来，将元素根据值的范围分配到不同的桶中。对每个桶内的元素可以使用其他排序算法进行排序，这里使用了插入排序算法。最后，将每个桶内排好序的元素合并成最终的排序结果。
下面是使用示例：
const array = [0.42, 0.32, 0.64, 0.12, 0.91, 0.25, 0.76];
console.log(bucketSort(array)); // 输出 [0.12, 0.25, 0.32, 0.42, 0.64, 0.76, 0.91]
在这个示例中，输入的数组是 [0.42, 0.32, 0.64, 0.12, 0.91, 0.25, 0.76]，它包含一些浮点数。经过桶排序后，数组被排序为 [0.12, 0.25, 0.32, 0.42, 0.64, 0.76, 0.91]。
需要注意的是，桶排序适用于一定范围内的浮点数排序，可以根据实际情况调整桶的大小。在桶内排序的过程中，可以选择其他适合的排序算法。
使用 JavaScript 实现一个基数排序（Radix Sort）
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为 O(kn),为数组长度，k 为数组中的数的最大的位数；
基数排序（Radix Sort）是一种线性时间复杂度的排序算法，适用于整数或字符串等类型的排序。下面是使用 JavaScript 实现基数排序的代码：
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
var counter = [];
console.time("基数排序耗时");
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if (counter[bucket] == null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for (var j = 0; j < counter.length; j++) {
var value = null;
if (counter[j] != null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
console.timeEnd("基数排序耗时");
return arr;
}
在上述代码中，radixSort函数接受一个数组作为输入，并使用基数排序算法对数组进行排序。算法首先获取数组中的最大值，然后根据最大值的位数进行多次桶排序。每次桶排序都是使用计数排序算法，根据当前位数的值将元素分配到不同的桶中，并按照桶的顺序重新组合元素。经过多次桶排序后，数组被排序完成。
getMax函数用于获取数组中的最大值。
countingSort函数是一个辅助函数，使用计数排序算法对数组按照指定位数进行排序。它创建计数数组用于统计每个数字出现的次数，并计算累积次数。然后，根据计数数组将元素放入正确的位置，最后将输出数组复制回原数组。
下面是使用示例：
const array = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(array)); // 输出 [2, 24, 45, 66, 75, 90, 170, 802]
在这个示例中，输入的数组是 [170, 45, 75, 90, 802, 24, 2, 66]。经过基数排序后，数组被排序为 [2, 24, 45, 66, 75, 90, 170, 802]。
需要注意的是，基数排序适用于整数或字符串等类型的排序，每个元素的位数必须相同。当元素数量较大或位数较多时，基数排序可能会占用较多的内存空间。
function swap(array, x, y) {
let temp = array[x];
array[x] = array[y];
array[y] = temp;
}
// 冒泡排序是一种简单的排序算法。
// 它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
// 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
// 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
// 冒泡排序 时间复杂度O(n2) 空间复杂度O(1) 稳定
function bubleSort(array) {
console.time("冒泡排序耗时");
let len = array.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
console.timeEnd("冒泡排序耗时");
return array;
}
// 冒泡排序增强版，记录一趟最后交换的位置 时间复杂度O(n2) 空间复杂度O(1) 稳定
function bubleSort2(array) {
console.time("改进后冒泡排序耗时");
let last = array.length - 1;
while (last > 0) {
let pos = 0;
for (let j = 0; j < last; j++) {
if (array[j] > array[j + 1]) {
pos = j;
swap(array, j, j + 1);
}
}
last = pos;
}
console.timeEnd("改进后冒泡排序耗时");
return array;
}
// 冒泡排序再次增强版，一次找到左侧最小值和右侧最大值
function bubleSort3(array) {
console.time("2次改进后冒泡排序耗时");
let low = 0;
let high = array.length - 1;
while (low < high) {
for (let j = low; j < high; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
--high;
for (let j = high; j > low; j--) {
if (array[j] < array[j - 1]) {
swap(array, j, j - 1);
}
}
++low;
}
console.timeEnd("2次改进后冒泡排序耗时");
return array;
}
// 选择排序(Selection-sort)是一种简单直观的排序算法。
// 它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
// 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
// 以此类推，直到所有元素均排序完毕。
// 选择排序 时间复杂度O(n2) 空间复杂度O(n1) 不稳定
function selectionSort(array) {
console.time("选择排序耗时");
let len = array.length;
let minIndex;
for (let i = 0; i < len; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, minIndex, i);
}
console.timeEnd("选择排序耗时");
return array;
}
// 插入排序（Insertion - Sort）的算法描述是一种简单直观的排序算法。
// 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
// 插入排序在实现上，通常采用in - place排序（即只需用到O(1)的额外空间的排序），
// 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
// 也就是说，左侧是排好的序列，从右侧第一个位置拿出1个元素，不断跟左侧对比，比左面小就把对比的元素往后挪一位留出1个空
// 直到不比左边小，把这个坑换成对比的元素
// 插入排序 O(n2) O(1) 稳定
function insertionSort(array) {
console.time("插入排序耗时");
let len = array.length;
for (let i = 1; i < len; i++) {
let j = i - 1;
let key = array[i];
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
console.timeEnd("插入排序耗时");
return array;
}
// 改进插入排序： 查找插入位置时使用二分查找的方式
function insertionSort2(array) {
console.time("二分插入排序耗时");
let len = array.length;
for (let i = 1; i < len; i++) {
let key = array[i];
let left = 0,
right = i - 1;
while (left <= right) {
let middle = Math.floor(left + (right - left) / 2);
if (array[middle] < key) {
left = middle + 1;
} else {
right = middle - 1;
}
}
for (let j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = key;
}
console.timeEnd("二分插入排序耗时");
return array;
}
// 希尔排序的核心在于间隔序列的设定。
// 既可以提前设定好间隔序列，也可以动态的定义间隔序列。
// 动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
// 希尔排序 O(nlog2n) O(1) 不稳定
function shellSort(array) {
console.time("希尔排序耗时");
const interval = 5;
let len = array.length;
let gap = 1;
while (gap < len / interval) {
gap = gap * interval + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / interval)) {
for (let right = gap; right < len; right++) {
let key = array[right];
let left = right - gap;
for (; left >= 0 && array[left] > key; left = left - gap) {
array[left + gap] = array[left];
}
array[left + gap] = key;
}
}
console.timeEnd("希尔排序耗时");
return array;
}
// 归并排序是建立在归并操作上的一种有效的排序算法。
// 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
// 归并排序是一种稳定的排序方法。
// 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
// 若将两个有序表合并成一个有序表，称为2 - 路归并。
// 归并排序 O(nlogn) O(nlogn) 稳定
function mergeSort(array) {
let len = array.length;
if (len < 2) return array;
let middle = Math.floor(len / 2);
let left = array.slice(0, middle);
let right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
if (left.length > 0) {
result = result.concat(left);
}
if (right.length > 0) {
result = result.concat(right);
}
return result;
}
// 快速排序的基本思想：
// 通过一趟排序将待排记录分隔成独立的两部分，
// 其中一部分记录的关键字均比另一部分的关键字小，
// 则可分别对这两部分记录继续进行排序，以达到整个序列有序。
// 快速排序 时间复杂度O(nlogn) 空间复杂度O(nlogn) 不稳定
function quickSort(arr) {
if (arr.length <= 1) return arr;
let kValue = arr.splice(Math.floor(arr.length / 2), 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] <= kValue) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([kValue], quickSort(right));
}
// 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
// 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
// 堆排序 时间复杂度O(nlogn) 空间复杂度O(1) 不稳定
function heapSort(array) {
let len = array.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(array, i, len);
}
for (let j = len - 1; j >= 1; j--) {
swap(array, 0, j);
heapify(array, 0, --len);
}
return array;
}
function heapify(array, i, size) {
let lastIndex = size - 1;
while (true) {
let leftIndex = i * 2 + 1;
let rightIndex = i * 2 + 2;
let current = i;
if (leftIndex <= lastIndex && array[leftIndex] > array[current]) {
current = leftIndex;
}
if (rightIndex <= lastIndex && array[rightIndex] > array[current]) {
current = rightIndex;
}
if (current !== i) {
swap(array, current, i);
i = current;
} else {
break;
}
}
}
// 计数排序(Counting sort)是一种稳定的排序算法。
// 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
// 然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
// 计数排序 时间复杂度O(n+k) 空间复杂度O(k) 稳定
function countingSort(array) {
let len = array.length;
if (len <= 1) return array;
let result = [];
let C = [];
let min = (max = array[0]);
for (let i = 0; i < len; i++) {
min = Math.min(min, array[i]);
max = Math.max(max, array[i]);
C[array[i]] = (C[array[i]] ? C[array[i]] : 0) + 1;
}
// 这个是为了计算C的第j个位置前面加上自己上的值合起来，就是在最终结果中的索引值，
// 举例：比如C[17] = 2,C[18] = 1,原来表示有2个17，1个18
// 处理完之后，C[18] = 2+1 = 3, 表示C[18]前面包括自己有3个数，那么在最终数组中，18的索引就是(3-1)=2.
for (let j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
}
for (let k = len - 1; k >= 0; k--) {
let index = C[array[k]] - 1;
result[index] = array[k];
C[array[k]]--;
}
return result;
}
// 桶排序 (Bucket sort)的工作的原理：
// 假设输入数据服从均匀分布，将数据分到有限数量的桶里，
// 每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
// 桶排序 时间复杂度O(n+k) 空间复杂度O(n+k) 稳定
function bucketSort(array, bucketNum) {
let len = array.length;
if (len <= 1) return array;
let result = [];
let buckets = [];
let min = (max = array[0]);
bucketNum = bucketNum || 10; //桶数量
for (let i = 1; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
}
let space = Math.ceil((max - min + 1) / bucketNum); // 每个桶要装多少个
for (let j = 0; j < len; j++) {
let bucketIndex = Math.floor((array[j] - min) / space);
if (Array.isArray(buckets[bucketIndex])) {
//插入排序
let k = buckets[bucketIndex].length - 1; //从当前需要插入的bucket最后1个元素开始对比
while (k >= 0 && buckets[bucketIndex][k] > array[j]) {
buckets[bucketIndex][k + 1] = buckets[bucketIndex][k];
k--;
}
buckets[bucketIndex][k + 1] = array[j];
} else {
buckets[bucketIndex] = [];
buckets[bucketIndex].push(array[j]);
}
}
// 最后把桶合并起来
let n = 0;
while (n < bucketNum) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
// 基数排序是按照低位先排序，然后收集；
// 再按照高位排序，然后再收集；
// 依次类推，直到最高位。
// 有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
// 最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
// 基数排序基于分别排序，分别收集，所以是稳定的。
// 基数排序 时间复杂度O(n*k) 空间复杂度O(n+k) 稳定
function radixSort(array) {
if (array.length <= 1) {
return array;
}
let max = array[0];
for (let i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
let maxLength = (max + "").length; //最大的数字是几位数
let dev = 1,
mod = 10;
for (let i = 0; i < maxLength; i++, dev *= 10, mod *= 10) {
let counter = [];
for (let j = 0; j < array.length; j++) {
let curNum = parseInt((array[j] % mod) / dev); //从后往前分别找出要处理的第几位数字
if (!Array.isArray(counter[curNum])) {
counter[curNum] = [];
}
counter[curNum].push(array[j]);
}
let pos = 0;
for (let k = 0; k < counter.length; k++) {
if (Array.isArray(counter[k])) {
while (counter[k].length > 0) {
array[pos] = counter[k].shift();
pos++;
}
}
}
}
return array;
}
const data = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
bubleSort([...data]);
bubleSort2([...data]);
bubleSort3([...data]);
console.log("======================");
selectionSort([...data]);
console.log("======================");
insertionSort([...data]);
insertionSort2([...data]);
console.log("======================");
shellSort([...data]);
console.log("======================");
console.time("归并排序耗时");
mergeSort([...data]);
console.timeEnd("归并排序耗时");
console.log("======================");
console.time("快速排序耗时");
quickSort([...data]);
console.timeEnd("快速排序耗时");
console.log("======================");
console.time("堆排序耗时");
heapSort([...data]);
console.timeEnd("堆排序耗时");
console.log("======================");
console.time("计数排序耗时");
countingSort([...data]);
console.timeEnd("计数排序耗时");
console.log("======================");
console.time("桶排序耗时");
bucketSort([...data], 4);
console.timeEnd("桶排序耗时");
console.log("======================");
console.time("基数排序耗时");
radixSort([...data]);
console.timeEnd("基数排序耗时");
console.log("======================");