|
|
|
《数据结构》自学方法指导 |
|
|
来源： 发布时间：2006-5-29 16:56:48 点击： |
下面用算法语言描述的希尔排序：
希尔排序中增量序列的选取是一个复杂的问题，涉及到一些数学上尚未解决的难题。我们不想加以详细讨论。到目前仅得出部分结论：如当增量序列为d[k]=2t-k+l -1时，希尔排序的运行时间为O(n3/2)，其中1≤k≤t≤└log2(n＋1)┘。增量序列还可以有各种取法, 如d[k]=2t-k，(d=…,9,5,3,2,1)。但请注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。
void shellpass(elem a[],int dh){
//进行一趟希尔排序，dh为增量
s=-dh+1; //监视哨位置
for (i=dh;i<=n;i++) { //进行插入排序
a[s]=a[i];
j=i-dh;
x=a[i].key;
while (x0)
s=-dh+1;
}
} void shellsort(elem a[],int d[]){
//希尔排序，d[k]为各趟排序增量序列，d[t]=1
k=1;
while (k<=t) {
shellpass(a,d[k]);
k++;
}
}
起泡排序(bubble sort)是交换排序中最简单的一种。其过程是这样的： 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序(即r[1].key＞r[2].key)， 则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。 依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。 上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录 的位置上，然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字 次大的记录被安置到第n-1个记录的位置上。
判别起泡排序结束的条件应该是"在一趟排序过程中没有进行过交换记录的操作"。在起泡排序的过程中，关键字较小的记录好比水中气泡逐趟向上飘浮，而关键字较大的记录好比石块往下沉，每一趟有一块"最大"的石头沉到水底。
具体算法如下：
void bubblepass(elem a[],int i){
for (j=1;ja[j+1]){
a[j]<->a[j+1]; //如逆序，则交换两个相邻元素
}
}
void bubblesort(elem a[]){//冒泡排序
for (i=n;i>1;i--)
bubblepass(a,i);
}
若初始序列为"正序"序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；反之，若初始序列为"逆序"序列，则需进行n-1趟排序，需进行n*(n-1)/2次比较；并作等数量级的记录移动。因此，总的时间复杂度为O(n2)。
快速排序(quick sort)是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
假设待排序的序列为{r[s],r[s+1],…,r[t]} .首先任意选取一个记录(通常可选第一个记录r[s])作为枢轴或支点)，然后重新排列其余记录，将所有关键字较它小的记录都安置在它的位置之前，所有关键字较它大的记录都安置在它的位置之后。由此可以该"枢轴"记录所在的位置。作分界线，将序列分割成两个子序列什{r[s],r[2], r[i-1]} 和{r[i+1],r[i+2],…,r[t]}。这个过程称作一趟快速排序(或一次划分)。
一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为s和t，设枢轴记录rp=r[s]，x=rp.key,则首先从j所指位置起向前搜索找到第一个关键字小于x的记录和rp互相交换，以保证该记录落在rp的前方；然后从i所指位置起向后搜索，找到第一个关键字大于x的记录和rp互相交换, 使其落在rp的后方。重复这两步直至i=j为止。以下是算法：
void QuickSort(SeqList r,int low,int high)
{//r[low..high]快速排序
int pivotpos;//划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(r,low,high);//对r[low..high]做划分
QuickSort(r,low,pivotpos-1);//对左区间递归排序
QuickSort(r,pivotpos+1,high);//对右区间递归排序
}
}//QuickSort
快速排序的平均时间为Tavg(n)=kn ln n，其中n为待排序序列中记录的个数，k为某个常数，经验证明，在所有同数量级的此类(先进的)排序方法中、快速排序的常数因子k 最小。因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。
查找表：
查找表是一种与前述几种数据结构均不同的数据结构，其特点是数据元素之间关系松散，也可以说没有逻辑关系(即集合结构)，并以查找为核心运算。因此本章的基本问题是如何高效率地实现查找，故本章地基本内容是，讨论各种不同地存储结构下地各种不同地查找算法。另外要清楚的是查找算法的好坏是用平均查找长度来衡量的。
静态查找表--适用于检索而不修改的场合
动态查找表--适用于既检索又修改的场合
19.索引顺序表上的查找--又称分块查找
⑴索引顺序表由顺序表和索引表两部分组成，其特点是：
①索引顺序表的元素"按块有序"
②索引表中的元素"按键值有序"
③其时间性能介于顺序查找和二分查找之间
⑵索引顺序表中查找的基本思想
①按顺序查找或二分查找方法在索引表上确定待查记录(即元素)所在的块
②在块内(即顺序表上)按顺序查找方法查找待查记录(元素)
20.树表的查找--通建立二叉树来实现
⑴一个无序序列可通过构造一颗二叉排序树而变成一个有序序列，即构造过程就是排序过程。
⑵一旦建好二叉排序树，在其上的插入、删除操作非常方便，都是根据键值大小从根结点开始查找插入、删除的位置(走了一条从根结点到叶子结点的路径)，因此效率很高。
21.散列表--散列表既表示一直存储方式，又表示一种查找方式，两者密不可分。
⑴从理论上讲，讲数据以散列表结构存放，查找一个数据所用的时间不依赖于数据元素的个数。
⑵散列技术的核心思想是用散列函数建立数据元素的键值与存储位置之间的关系，并使查找过程与之相对应。
⑶散列函数的构造方法有多种，但不管采用那种方法，都会出现冲突现象。
⑷解决冲突的方法与散列表的具体结构有关，注意比较它们的不同之处。
⑸开散列表实际上是同义词子表的数组，每个同义词子表是一个链表，因而它的存储空间大小可以动态变化。
⑹闭散列表是一个大小固定的数组，其解决冲突的基本思想是在冲突发生时构造后继散列地址。这种后继散列地址的构造方法有以下几种：线性探测法、二次探测法和多重散列法。◆
本新闻共 6页,当前在第 6页 1 2 3 4 5 6 |
|
|
|
