带你读《图解算法小抄》十四、排序(4)

简介: 带你读《图解算法小抄》十四、排序(4)

带你读《图解算法小抄》十四、排序(3)https://developer.aliyun.com/article/1348147?groupCode=tech_library


2选择排序优化

这是基本的选择排序算法实现。接下来,我将介绍一种优化方法,称为“双向选择排序”。

双向选择排序是对传统选择排序的一种改进,它通过同时寻找未排序序列中的最大和最小元素,然后分别将它们放到已排序序列的两端,从而减少了一半的比较次数。

 

function bidirectionalSelectionSort(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    let minIndex = left;
    let maxIndex = right;
    for (let i = left; i <= right; i++) {
      if (arr[i] < arr[minIndex]) {
        minIndex = i;
      }
      if (arr[i] > arr[maxIndex]) {
        maxIndex = i;
      }
    }
    if (minIndex !== left) {
      [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
    }
    if (maxIndex === left) {
      // 如果最大元素移到了最小元素的位置,更新最大元素的索引
      maxIndex = minIndex;
    }
    if (maxIndex !== right) {
      [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
    }
    left++;
    right--;
  }
  return arr;
}
// 示例用法:const array = [64, 25, 12, 22, 11];const sortedArray = bidirectionalSelectionSort(array);
console.log(sortedArray); // 输出:[11, 12, 22, 25, 64]

 

双向选择排序的优化使得每一轮循环可以同时找到最大和最小元素,从而减少了比较次数。这样,在大型数据集上,它的性能优于传统的选择排序算法。

3复杂度

名称

最佳情况

平均情况

最坏情况

内存

稳定性

备注

选择排序

n^2

n^2

n^2

1

 

 

4参考资料

维基百科


带你读《图解算法小抄》十四、排序(5)https://developer.aliyun.com/article/1348145?groupCode=tech_library

相关文章
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
22天前
|
搜索推荐 Shell
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
37 9
|
15天前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
17 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
14天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
27 0
|
21天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
54 0
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
28 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
3月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
41 0
|
3月前
|
算法 关系型数据库 MySQL
揭秘MySQL中的版本号排序:这个超级算法将颠覆你的排序世界!
【8月更文挑战第8天】在软件开发与数据管理中,正确排序版本号对软件更新及数据分析至关重要。因MySQL默认按字符串排序版本号,可能出现&#39;1.20.0&#39;在&#39;1.10.0&#39;之前的不合理情况。解决办法是将版本号各部分转换为整数后排序。例如,使用`SUBSTRING_INDEX`和`CAST`函数从`software`表的`version`字段提取并转换版本号,再按这些整数排序。这种方法可确保版本号按逻辑正确排序,适用于&#39;major.minor.patch&#39;格式的版本号。对于更复杂格式,需调整处理逻辑。掌握此技巧可有效应对版本号排序需求。
154 3
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
41 0