常用排序,快速排序,归并排序算法讲解

您所在的位置：网站首页 › 遗传学讲解 › 常用排序,快速排序,归并排序算法讲解

常用排序,快速排序,归并排序算法讲解

2023-07-11 07:37| 来源: 网络整理| 查看: 265

文章目录快速排序归并排序

排序有很多种算法，常听的十大排序有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、希尔排序、计数排序、基数排序、桶排序。

这里只介绍两个常用的算法。

排序：

快速排序归并排序

你可能想知道什么时候该用哪个：

快速排序使用场景：快速排序平均时间复杂度为O(n log n)，最坏情况下为O(n²)，不太稳定，但优点是不占用额外空间，快速排序为原地排序。在实践中，快速排序通常优于其他时间复杂度为 O(n log n) 的算法，

归并排序使用场景：时间复杂度为O(n log n)。无论情况好坏都相对稳定。优点是稳定，但需要占用额外的O(n)空间。

快速排序

思路：选择一个基准元素，将所有小于基准的元素放置在其左侧，将所有大于基准的元素放置在其右侧。这种操作称为“分区”。然后分别对基准左侧和右侧的两个子元素执行相同的操作。

现在开始快速排序的基本步骤思路：

1: 数据数组

在这里插入图片描述 2: 选择基准

在这里插入图片描述

3: 设置左边界和右边界

在这里插入图片描述 4: 如果右边界小于基准值，则调换左边界和右边界的值，接着左边界i++，随后右边界j++(如果循环未结束)。否则仅j++

在这里插入图片描述

如果不理解，请仔细阅读第四标题的内容：如果右边界小于基准值，则调换左边界和右边界的值，接着左边界i++，随后右边界j++(如果循环未结束)。否则仅j++

5: 循环结束后，交换左边界和基准的值

在这里插入图片描述

6: 根据基准，截取两部分的值

在这里插入图片描述 7:将左右两部分分别执行 1-6 的步骤

在这里插入图片描述

JavaScript实现代码：

function myQuickSort(array, left = 0, right = array.length - 1) { if (left // 使用最右边的元素作为枢轴 let pivot = array[right] // 从左边开始 let i = left; // 遍历数组 for (let j = left; j [array[i], array[j]] = [array[j], array[i]] i++ } } // 最后，将枢轴放置在正确的位置 [array[i], array[right]] = [array[right], array[i]] // 返回枢轴的位置 return i; } console.log(myQuickSort([7, 2, 3, 1, 6, 8, 4, 5])) 归并排序

思路：将一个大列表分成两个较小的子列表，然后分别对两个子列表进行排序，最后将两个已排序的子列表合并为一个完整的排序列表。

现在开始归并排序的基本步骤思路：

1: 数据数组

在这里插入图片描述