数据结构中的各种排序.doc
版权申诉
199 浏览量
2022-07-11
15:22:08
上传
评论
收藏 62KB DOC 举报
数据结构中的各种排序
A）需求分析：
1、冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒。
冒泡排序是稳定的。算法时间复杂度 O(n2)--[n 的平方]
2、选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。算法复杂度 O(n2)--[n 的平方]
3、插入排序
直接插入排序是稳定的。算法时间复杂度 O(n2)--[n 的平方]
4、折半插入排序
折半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置
折半插入是一种稳定的排序 排序时间复杂度 O(n^2)附加空间 O(1)
5、快速排序
快速排序是不稳定的。最理想情况算法时间复杂度 O(nlog2n)，最坏 O(n2)
6、希尔排序
算法先将要排序的一组数按某个增量 d 分成若干组，每组中
记录的下标相差 d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到 1 时，整个要排序的数被分成
一组，排序完成。
7、堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调
用渗透函数
实现排序的函数。有最大堆和最少堆之分
堆排序是不稳定的。算法时间复杂度 O(nlog2n)。
8、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法
（Divide and Conquer）的一个非常典型的应用。
归并排序是一种较稳定的排序 时间复杂度为时间 O(nlogn)
9、基数排序
基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most
significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相
反，由键值的最左边开始。
基数排序是一种不稳定的排序，时间复杂度为：O(d(n+radix))
B）概要设计：
void insertsort(int *a );//插入排序函数
void Binsertsort(int *a ); //折半插入排序函数
void bubble_sort(int *a); //冒泡排序
剩余10页未读，继续阅读
评论0
最新资源