当前位置:文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 数据结构排序方法总结
免费下载此文档

数据结构排序方法总结

本文档中总结了数据结构中内部排序的各种方法,让大家对排序的掌握有很大的帮助哦!

数据结构的内部排序

数据结构中的内部各种排序,大体上分为五大类,在我们对每个算法进行分析前,最重要的是搞清楚它的基本思想。

★插入类排序;

★交换类排序;

★选择类排序;

★归并排序;

★分配类排序;

数据结构排序方法总结

基本思想是:在一个已经排好序的序列中,每一步都将下一个待排序的记录插入到已排好序的记录中,直到所有待排序的记录全部插入为止。

插入类排序又分为三大类:

●直接插入排序; ●折半插入排序;

●希尔排序;

下面我们以直接插入排序与希尔排序为例。

(1) 直接插入排序 算法思想:将第i个记录(i一般是从2开始)插入到前面i-1个已经排好序的记录中。

具体过程:将第i个记录的关键字K顺次与其前面记录的关键字进行比较。将所有关键字大于K的记录依次向后移动一个位置,直到遇到小于或等于K的关键字,就把K插入到其后面即可。

下面我们以一个例子为例,讲解它的具体实现过程。

直接插入排序举例

以12 2 16 30 8 28 4 10 20 6 18序列为例

第一趟:2 12 16 30 8 28 4 10 20 6 18

第二趟:2 8 12 16 30 28 4 10 20 6 18

第三趟:2 8 12 16 28 30 4 10 20 6 18

第四趟:2 4 8 12 16 28 30 10 20 6 18

第五趟:2 4 8 10 12 16 28 30 20 6 18

第六趟:2 4 8 10 12 16 20 28 30 6 18

第七趟:2 4 6 8 10 12 16 20 28 30 18

第八趟:2 4 6 8 10 12 16 18 20 28 30

功能实现:

输入:数组名称(也就是数组首地址)、数组中元素个数

================================================

算法思想简单描述:在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。 直接插入排序是稳定的。算法时间复杂度O(n2 )

=====================================================

voidinsert_sort(int *x, int n)

{

int i, j, t;

第1页

免费下载Word文档免费下载:数据结构排序方法总结

(下载1-10页,共10页)

我要评论

返回顶部