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

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

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


3优化策略

交换标记

如果在一次遍历过程中没有发生过交换,那么意味着序列已经是有序的,不需要继续排序。我们可以通过设置一个标记来优化算法。如果在某次遍历中没有发生交换,则直接结束排序。

 

这个优化对于已经部分有序的序列来说,可以大幅度提高效率。

let array = [5, 3, 8, 4, 6];let swapped = true;
while(swapped) {
  swapped = false;
  for(let i = 0; i < array.length - 1; i++) {
    if(array[i] > array[i + 1]) {
      let temp = array[i];
      array[i] = array[i + 1];
      array[i + 1] = temp;
      swapped = true;
    }
  }}
console.log(array);  // 输出: [3, 4, 5, 6, 8]

双向冒泡排序

一趟遍历只能确保最大(或最小)的数被移到序列一端,在双向冒泡排序中,一趟遍历包括了两个过程,一个从头至尾,一个从尾至头,这样就能确保在一趟遍历后,最大和最小的数都被移到了正确的位置。

 

let array = [5, 3, 8, 4, 6];let swapped;let start = 0;let end = array.length - 1;
while(start < end) {
  for(let i = start; i < end; i++) {
    if(array[i] > array[i + 1]) {
      let temp = array[i];
      array[i] = array[i + 1];
      array[i + 1] = temp;
      swapped = i;
    }
  }
  end = swapped;
  for(let i = end; i > start; i--) {
    if(array[i] < array[i - 1]) {
      let temp = array[i];
      array[i] = array[i - 1];
      array[i - 1] = temp;
      swapped = i;
    }
  }
  start = swapped;
}
console.log(array);  // 输出: [3, 4, 5, 6, 8]

记录上次交换的位置

在实际的数据序列中,尾部的有序序列通常不只一个,因此我们可以记住最后一次交换发生的位置,下一次比较到这个位置即可。

 

let array = [5, 3, 8, 4, 6];let lastExchangeIndex = 0;let sortBorder = array.length - 1;
for(let i =
 0; i < array.length - 1; i++) {
  let isSorted = true;
  for(let j = 0; j < sortBorder; j++) {
    if(array[j] > array[j + 1]) {
      let temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
      isSorted = false;
      lastExchangeIndex = j;
    }
  }
  sortBorder = lastExchangeIndex;
  if(isSorted) {
    break;
  }}
console.log(array);  // 输出: [3, 4, 5, 6, 8]

带你读《图解算法小抄》十四、排序(3)https://developer.aliyun.com/article/1348147?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