数据结构-排序概述

几种常见的排序算法

排序

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列,使之按关键字递增(或递减)次序排序起来。在排序的过程中,数据的移动方式可分为“直接移动”和“逻辑移动”两种。

  • 直接移动:直接交换存储数据的位置。
  • 逻辑移动:并不会移动数据存储位置,仅改变指向这些数据的指针。

两者之间的优劣在于直接移动会浪费许多时间进行数据的改动,而逻辑移动只要改变指针指向的位置就能轻易达到排序的目的。

排序分类

在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称为内部排序(内排序);反之,若排序过程中要进行数据的内、外存转换,则称为外部排序(外排序)。

内排序

  • 插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子列表中的适当位置,直到全部记录插入完成为止。
  • 选择排序:每一趟从待排序的记录中选出关键字最小或最大的记录,顺序放在已排好序的子列表的最后,直到全部记录排序完毕。
  • 交换排序:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
  • 归并排序:将两个或两个以上的有序子序列“归并”为一个有效序列。
  • 分配排序:无需比较关键字,通过“分配”和“收集”过程实现排序。

外排序

  • 直接合并排序法
  • k路合并法
  • 多项和并法

排序有非递增排序和非递减排序两种,为了不失一般性,在后续介绍中将会使用按关键码非递减有序设计。

排序算法

这里主要说明算法的思想,其余的细节部分后续会分别进行介绍。

  • 直接插入排序:初始时,第一个数为有序区,其余为无序区;然后,逐步扩大有序区,依次从无序区中选择第一个数,从后向前遍历有序区,边遍历边移动数据,直到找到正确的位置进行插入。
  • 希尔排序:系尔排序是先做宏观调整,即跳跃式的插入排序,
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------