两个月了,终于把数据结构看完了.....完结篇
排序:假设含有n个记录的序列为{r1,r2, .......rn},其相应的关键字分别为{k1,k2,......kn},需确定1,2,......,n的一种排列p1,p2,.......,pn,使其相应的关键字满足kp1<= kp2<= .......kpn(非递增或非递减)关系,即使得到序列称为一个关键字有序的序列{rp1,rp2,.......rpn},这样的操作称为排序
1.冒泡排序
冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止.
//对顺序表L作冒泡排序
void BubbleSort0(SqList * L){
int i , j;
for (i = 1; i : L - >length; i++){
for (j = L ->length - 1; j >=i; j++){ //注意j是从后往前循环
if (L -> r[j] > L -> r[j + 1]){//前者大于后者
swap(L,j,j+ 1);//交换L -> r[j]与L -> r[j + 1]的值
}
}
}
}
冒泡排序
2.简单选择排序算法
简单选择排序算法:就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<= i <=n)个记录交换.
//对顺序表L作简单选择排序
void SelectSort (SqList * L){
int i ,j ,min;
for (i = 1; i < L ->length; i++){
min = i;//将当前下标定义为最小值下标
for (j = i + 1; j <= L -> length; j++){//循环之后的数据
if (L -> r[min] > r[j]) //如果有小于当前最小值的关键字
min = j;//将此关键字的下标赋值给min
}
if (i != min) //若min不等于i,说明找到最小值
swap(L,i,min);
}
}
}
简单选择排序
4.直接插入排序
直接插入排序:是将一个记录插入到已排序好的有序表中,从而得到一个新的,记录数增1的有序表
//对顺序表L作直接插入排序
void InsertSort(Sqlist * L){
int i , j;
for (i = 2; i < L ->length;i++){
if (L ->r[i] < L ->r[i - 1] ){//需将L ->r[i]插入有序子表
L -> r[0] = L -> r[i];;设置哨兵
for (j = i - 1; L -> r[j] > L ->r[0];j--)
L ->r[j+ 1] = L -> r[j];//记录后移
L -> r[j + 1] = L -> r[0];//插入到正确的位置
}
}
}
5.希尔排序
// 希尔排序
//对顺序表L作希尔排序
void ShellSort (Sqlist *L){
int i ,j;
int increment = L ->length;
do {
increment = increment / 3+1;//增量序列
for (i = increment + 1; i <= L -> length; i++){
if (L -> r[i] < L ->r[i - increment]){//需将L ->r[i]插入有序增量子表
L -> r[0] = L -> r[i];//暂存在L -> r[0]
for (j = i - increment ; j > 0&& L -> r[0] < L ->r[j]; j -= increment)
L -> r[j + increment ] = L ->r[0];插入;
}
}
}
while (increment > 1);
}
希尔排序
6.堆排序
堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,我们称为小顶堆
堆排序:将待排序的序列构成一个大顶堆.此时,整个序列的最大值就是堆顶的根结点.将他移走(其实也就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构成一个堆,这样就会得到n个元素中的次小值,如此反复执行,便能得到一个有序序列
堆排序的基本思想:
1.将一个无序序列构成一个堆
-
2.在输出堆顶元素后,调整剩余元素成为一个新的堆
//1.对顺序表L进行堆排序 void HeapSort (SqList *L){ int i; for (i = L -> length/ 2; i > 0; i--)//把L中的r构成一个大顶堆 HeapAdjust (L,i,L ->length); for (i = L ->length ; i > 1; i--){ swap (L, 1,I);//将堆顶记录和当前未经排序子序列的最后一个记录交换 HeapAdjust(L,1,i - 1);//将L ->r[1....i - 1]重新调整为大顶堆 } } //已知L -> r[s...m]中记录的关键字除L ->r[s]之外 均满足堆的定义 //本函数调整L -> r[s]的关键字,使L ->r[s...m]成为一个大顶堆 void HeapAjust (SqList * L, int s, int m){ int temp , j; temp = L ->r[s]; for (j = 2 * s; j <= m; j *= 2)//沿关键字较大的孩子结点向下筛选 { if (j < m && L -> r[j] < L -> r[j + 1]) ++j;//j为关键字中较大的记录的下标 if (temp >= L ->r[j]) break;//rc应插入在位置s上 L -> r[s] = L -> r[j]; s = j; } L -> r[s] = temp;//插入 }
大顶堆的创建
排序
7.快速排序算法
快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序的谜底
//对顺序表L作快速排序
void QulickSort (SqList * L){
QSort (L , 1,L ->length);
}
//对顺序表L中的子序列L ->r[low ...high]作快速排序
void QSort (SqList * L, int low, int high){
int privot;
if (low < high){
privot = Partition (L,low,high) //将L ->r[low...high]一分为二
QSort(L,low,privot - 1);//对低子表递归排序
QSort(L,privot + 1,high);//对高子表递归排序
}
}
//交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置
//此时在它之前(后)的记录均不大(小)于它
int Partition(Sqlist * L, int low, int high){
int privotkey;
privotkey = L -> r[low];//用子表的第一个记录作枢轴记录
while(low < higj){ //从表的两端交替向中间扫描
while(low < hight && l -> r[high] >= privotkey)
high--;
swap (L , low, high);//将比枢
轴记录小的记录交换到低端
while(low < high && L -> r[low] <= privotkey)
low++;
swap(L,low,high); //将比枢
轴记录大的记录交换到高端
}
return low;//返回枢轴所在的位置
}
I快速排序.jpg
