- 全国计算机等级考试教程:二级公共基础与C语言
- 董琴 邵洪成 陈瑾 孙久 严长虹
- 276字
- 2021-03-31 07:36:34
1.1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
1.交换类排序法
①冒泡排序法:对于长度为n的线性表,最坏情况下,需要比较n(n-1)/2次。
②快速排序法:对于长度为n的线性表,最坏情况下,需要比较nlog2n次。
2.插入类排序法
①简单插入排序法:对于长度为n的线性表,最坏情况下,需要比较n(n-1)/2次。
②希尔排序法:对于长度为n的线性表,最坏情况下,需要比较n1.5次。
3.选择类排序法
①简单选择排序法:对于长度为n的线性表,最坏情况下,需要比较n(n-1)/2次。
②堆排序法:对于长度为n的线性表,最坏情况下,需要比较nlog2n次。
4.各种排序比较(见表1-1-1)
表1-1-1 各种排序比较
![](https://epubservercos.yuewen.com/A8A3F7/14615858205714806/epubprivate/OEBPS/Images/img00023001.jpg?sign=1734463535-Vm34Z7gcCZuY2FCsb62scerz8SJPGbyn-0-186c61477ed2c5a1dde40ee033023d2b)