1 前言
排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,究竟
各有什么特点呢?当我们要对一组数据排序的时候,我们应该如何何种排序算法了?
常用的排序算法分别为直接排序、冒泡排序、快速排序、选择排序、堆排序、希尔
排序算法。
2 需求分析
2.1 原理
2.1.1、直接排序
算法描述:经过 i-1 遍处理后,L[1..i-1]己排好序。第 i 遍处理仅将 L[i]插入
L[1..i-1]的适当位置,使得 L[1..i]又是排好序的序列。要达到这个目的,我们可以
用顺序比较的方法。首先比较 L[i]和 L[i-1],如果 L[i-1]≤ L[i],则 L[1..i]已排好序,
第 i 遍处理就结束了;否则交换 L[i]与 L[i-1]的位置,继续比较 L[i-1]和 L[i-2],直
到找到某一个位置 j(1≤j≤i-1),使得 L[j] ≤L[j+1]时为止。
2.1.2、冒泡排序
算法描述:核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找
到这两个项目后,交换项目的位置然后继续扫描。重复上面的操作直到所有的项目
都按顺序排好。
2.1.3、快速排序
算法描述:首先检查数据列表中的数据数,如果小于两个,则直接退出程序。
如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点
的数据放在一组,其余的放在另一组,然后分别对两组数据排序。通常分割点的数
据是随机选取的。这样无论你的数据是否已被排列过,你所分割成的两个字列表的
大小是差不多的。而只要两个子列表的大小差不多。
2.1.4、选择排序
算法描述:首先找到数据清单中的最小的数据,然后将这个数据同第一个数据交
换位置;接下来找第二小的数据,再将其同第二个数据交换位置,以此类推。
2.1.5、堆排序
(1) 基本思想:堆排序是一树形选择排序,在排序过程中,将 R[1..N]看成是一
颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在
关系来选择最小的元素。