学习排序算法的目的
- 解决实际问题：排序算法是计算机科学中的基础算法之一，几乎在任何领域的软件开发中都会遇到排序的需求。了解各种排序算法能够帮助程序员解决实际问题，提供高效的数据处理和查询功能。
- 性能优化：排序算法的选择会对程序的性能产生直接影响。不同的排序算法在时间复杂度和空间复杂度上有不同的特点，了解不同排序算法的性能特点可以帮助程序员选择最适合的算法，优化程序的执行效率。
- 数据结构：排序算法与数据结构密切相关。对于不同类型的数据结构，选择合适的排序算法能够充分发挥数据结构的优势，提高数据处理的效率。例如，对于链表结构，插入排序可能更加适用，而对于数组结构，快速排序或堆排序可能更高效。
- 算法设计和分析：排序算法是算法设计和分析的经典案例之一。通过学习排序算法，程序员可以培养良好的算法设计思维，学会分析和评估算法的性能，提高解决问题的能力。
- 面试准备：排序算法是面试中常见的考点之一。许多技术面试会涉及排序算法的实现和性能分析，熟悉排序算法可以帮助程序员在面试中更好地展示自己的技术能力。
常见的十大排序算法分类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
冒泡排序（Bubble Sort）
重复地遍历要排序的列表，依次比较相邻的两个元素，并按照升序或降序交换它们的位置，直到整个列表排序完成。
实现原理
- 从列表的第一个元素开始，将其与下一个元素比较，如果顺序错误（升序时当前元素大于下一个元素，降序时当前元素小于下一个元素），则交换它们的位置。
- 继续比较下一个相邻元素，重复上述步骤，直到遍历到列表的最后一个元素。
- 重复步骤1和2，直到没有任何元素需要交换位置，即列表已排序完成。
冒泡.gif
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
使用场景
冒泡排序是一种简单但效率较低的排序算法，适用于小规模的列表；在大规模数据的情况下，其他高效的排序算法（如快速排序、归并排序）更常被使用。
列表几乎已经有序时，冒泡排序可能会比其他算法更加高效。
快速排序（Quick Sort）
快速排序（Quick Sort）是一种高效的排序算法，它的原理是通过选择一个基准元素，将数组分割成较小和较大两个子数组，然后对子数组进行递归排序，直到整个数组有序。
实现原理
- 选择一个基准元素（通常是数组中的中间元素）。
- 将数组分成两个子数组，比基准元素小的放在左边，比基准元素大的放在右边。
- 递归地对左右子数组进行快速排序。
- 合并左子数组、基准元素和右子数组，得到最终有序的数组。
function quickSort(arr) {
// 检查数组元素的个数，如果小于等于1，就返回
if (arr.length <= 1) return arr;
// 基准索引
let pivotIndex = Math.floor(arr.length / 2);
// 找到基准，并且把基准从原数组中删除
let pivot = arr.splice(pivotIndex, 1)[0];
// 定义左右数组
let left = [];
let right = [];
// 把基准小的放在left数组中，大的放在right中
arr.forEach(ele => {
if (ele < pivot) {
left.push(ele);
} else {
right.push(ele);
}
});
return quickSort(left).concat([pivot], quickSort(right));
}
console.log("快速排序",quickSort([49, 38, 65, 97, 76, 13, 27, 49]));
使用场景
适用于大规模数据的排序，它在实际应用中被广泛使用
许多编程语言和库中的默认排序算法，如JavaScript中的Array.prototype.sort()方法就使用了快速排序算法。
选择排序（Selection Sort）
在一组数据中，首先找到最小（或最大）的数据并放在最前面（数据的后面），以此类推，直到全部数据排序完毕。
实现原理
- 每一轮从待排序的元素中选择最小（或最大）的元素，将其与序列中的第一个元素交换位置
- 再从剩下的元素中选择最小（或最大）的元素，与序列中的第二个元素交换位置
- 以此类推，直到整个序列有序
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++) {
console.log("循环找最小的值", arr[j], arr[minIndex], minIndex);
if (arr[j] < arr[minIndex]) {
// 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
// 将当前遍历的项和查找到的最小项交换位置
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
// 使用
let arr = [3, 1, 5, 7, 2, 4, 6, 8];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
使用场景
由于选择排序的时间复杂度较高，对于大规模数据的排序效率较低，因此在实际应用中并不常用。更适合在小规模或部分有序的数组中使用。
插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法
实现原理
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
-
重复步骤2~5。
插入排序.gif
function insertionSort(arr) {
// current 是我们需要插入的当前元素。preIndex 是我们正在与 current 进行比较的元素的位置。
let preIndex, current;
for (let i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
// 将当前满足的条件的值和当前比较的
// 当 preIndex 存在且其对应元素值大于 current 时，我们一直将这些元素往后移。
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = insertionSort(array);
console.log(sortedArray); // 输出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]
使用场景
插入排序适用于小规模或部分有序的数组。当待排序数组基本有序时，插入排序的效率较高。它比冒泡排序和选择排序的性能稍好，且实现简单，适用于对于数据量较小的排序任务。插入排序也可以用作其他高级排序算法的子过程，例如快速排序的优化版本中的小数组排序。
希尔排序（Shell Sort）
希尔排序（Shell Sort），也称作缩小增量排序，是插入排序的一种改进版本。它通过将待排序数组分成多个子数组，并对每个子数组进行插入排序，逐步减小子数组的大小，最终完成整个数组的排序。
实现原理
- 选择一个初始增量（通常为数组长度的一半）。
- 将数组分成多个子数组，每个子数组相隔增量个位置。
- 对每个子数组进行插入排序，将子数组中的元素插入到正确的位置。
-
逐步减小增量，重复上述步骤，直到增量为1，完成整个数组的排序。
希尔排序.gif
希尔排序.gif
function shellSort(arr) {
let len = arr.length,
temp,
gap = Math.floor(len / 2); // 初始增量
while (gap > 0) {
// 对每个子数组进行插入排序
for (let i = gap; i < len; i++) {
temp = arr[i];
let preIndex = i - gap;
// 在子数组中进行插入排序
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = shellSort(array);
console.log(sortedArray); // 输出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]
使用场景
希尔排序适用于中等大小的数组排序，特别适用于需要在性能和简单实现之间取得平衡的场景。它在实际应用中常用于对大型数据集进行初步排序的预处理步骤，为后续排序算法提供更好的初始状态。希尔排序相对于其他简单的初级排序算法具有更好的性能，但仍然不如快速排序、归并排序等高级排序算法。
归并排序（Merge Sort）
归并排序（Merge Sort）是一种高效的排序算法，它的原理是将待排序的数组递归地分成两个子数组，分别对子数组进行排序，然后将两个排序好的子数组合并成一个有序的数组。
实现原理
- 将待排序数组分割成较小的子数组，直到每个子数组只包含一个元素（递归基线条件）。
- 递归地将子数组排序，直到得到排好序的子数组。
-
合并排好序的子数组，得到最终有序的数组。
归并排序.gif
function mergeSort(arr) {
if (arr.length <= 1) {
return arr; // 基线条件：数组为空或只有一个元素，直接返回
}
const mid = Math.floor(arr.length / 2); // 找到数组的中间位置
const left = arr.slice(0, mid); // 分割为左子数组
const right = arr.slice(mid); // 分割为右子数组
console.log("分组",left,right)
return merge(mergeSort(left), mergeSort(right)); // 递归地对左右子数组进行归并排序并合并
}
// 合并两个有序数组
function merge(left, right) {
console.log("获取的数组",left,right)
const merged = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
merged.push(left[leftIndex]); // 左子数组元素较小，放入合并数组
leftIndex++;
} else {
merged.push(right[rightIndex]); // 右子数组元素较小，放入合并数组
rightIndex++;
}
}
// 将剩余的元素放入合并数组
return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = mergeSort(array);
console.log(sortedArray); // 输出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]
使用场景
归并排序适用于大规模数据的排序，特别适用于外部排序，即排序数据量大到无法全部加载到内存中的场景。归并排序的优势在于排序速度较快且稳定，对于处理大规模乱序数据或需要保持相同元素相对顺序的排序任务非常有效。
堆排序（Heap Sort）
堆排序（Heap Sort）是一种高效的排序算法，它利用堆这种数据结构进行排序。堆是一种特殊的完全二叉树，它满足堆的性质：对于每个节点，其值大于（或小于）其子节点的值。
实现原理
- 构建最大堆：从最后一个非叶子节点开始，依次将数组转换为最大堆，保证每个节点的值大于或等于其子节点的值。
- 依次取出堆顶元素：将堆顶元素与最后一个元素交换，然后调整堆，将剩余元素重新构建为最大堆。
- 重复上述步骤，直到堆中的所有元素都被取出并排好序。
function heapSort(arr) {
const len = arr.length;
// 构建最大堆
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
console.log("sss===构建堆循环前" + i, arr, len, i);
heapify(arr, len, i);
console.log("sss===构建堆循环后" + i, arr, len, i);
}
// 依次取出堆顶元素并调整堆
for (let i = len - 1; i > 0; i--) {
console.log("sss===调整前" + i, arr, i);
[arr[0], arr[i]] = [arr[i], arr[0]]; // 将堆顶元素与最后一个元素交换
console.log("sss===调整交换中" + i, arr, i);
heapify(arr, i, 0); // 调整堆
console.log("sss===调整后" + i, arr, i);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i; // 当前节点索引
const left = 2 * i + 1; // 左子节点索引
const right = 2 * i + 2; // 右子节点索引
// 找出最大值的索引
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值的索引不是当前节点，则交换节点并继续调整堆
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
console.log("sss===内部调用前" + largest, arr, largest);
heapify(arr, n, largest);
console.log("sss===内部调用后" + largest, arr, largest);
}
}
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 5, 6, 2, 3，10];
const sortedArray = heapSort(array);
console.log(sortedArray); // 输出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]
使用场景
堆排序适用于大规模数据的排序，尤其适用于需要找出最大或最小的K个元素的问题。由于堆排序的构建最大堆操作具有线性时间复杂度，因此可以在一些特定场景中提供较好的性能，如优先队列的实现、Top K 问题等。
