算法实现
⑴ 一趟快速排序算法的实现
int quick_one_pass(Sqlist *L , int low, int high)
L->R[0]=L->R[i] ; /* R[0]作为临时单元和哨兵 */ do
{ while (LQ(L->R[0].key, L->R[j].key)&&(j>i)) j-- ;
if (j>i) { L->R[i]=L->R[j] ; i++; } while (LQ(L->R[i].key, L->R[0].key)&&(j>i)) i++ ;
if (j>i) { L->R[j]=L->R[i] ; j--; }
} while(i!=j) ; /* i=j时退出扫描 */ L->R[i]=L->R[0] ; return(i) ; }
递归算法
void quick_Sort(Sqlist *L , int low, int high) { int k ;
if (low { k=quick_one_pass(L, low, high); quick_Sort(L, low, k-1); quick_Sort(L, k+1, high); } /* 序列分为两部分后分别对每个子序列排序 */ } 非递归算法 # define MAX_STACK 100 void quick_Sort(Sqlist *L , int low, int high) { int k , stack[MAX_STACK] , top=0; do { while (low { k=quick_one_pass(L,low,high); stack[++top]=high ; stack[++top]=k+1 ; /* 第二个子序列的上,下界分别入栈 */ high=k-1 ; } if (top!=0) { low=stack[top--] ; high=stack[top--] ; } }while (top!=0&&low ==============================================================================简单选择排序(Simple Selection Sort ，又称为直接选择排序) 排序示例 例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接选择排序的过程 算法实现 void simple_selection_sort(Sqlist *L) { int m, n , k; for (m=1; m for (n=m+1; n<=L->length; n++) if ( LT(L->R[n].key, L->R[k].key) ) k=n ; if (k!=m) /* 记录交换 */ { L->R[0]=L->R[m]; L->R[m]=L->R[k]; L->R[k]=L->R[0]; } } } 算法分析 整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。 进行第i趟排序时，关键字的比较次数为n-i，则： ∴ 时间复杂度是：T(n)=O(n) 空间复杂度是：S(n)=O(1) 从排序的稳定性来看，直接选择排序是不稳定的。 =============================================================================== 2 堆的定义 是n个元素的序列H={k1, k2 , … kn} ，满足： 堆的性质 ① 堆是一棵采用顺序存储结构的完全二叉树， k1是根结点； ② 堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆； ③ 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的； (4)堆中的任一子树也是堆。 利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。 堆排序思想 ① 对一组待排序的记录，按堆的定义建立堆； ② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的； ③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区； ④ 重复上述步骤，直到全部记录排好序为止。 结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。 堆排序算法实现 堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。 void Heap_Sort(Sqlist *H) { int j ; for (j=H->length/2; j>0; j--) Heap_adjust(H, j , H->length) ; /* 初始建堆 */ for (j=H->length/2; j>=1; j--) { H->R[0]=H->R[1] ; H->R[1]=H->R[j] ; H->R[j]=H->R[0] ; /* 堆顶与最后一个交换 */ Heap_adjust(H, 1, j-1) ; } } 堆排序的比较次数的数量级为： T(n)=O(n㏒2n)；而附加空间就是交换时所用的临时空间，故空间复杂度为： S(n)=O(1) ===============================================================================归并(Merging) ：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n) 。 归并排序的算法 开始归并时，每个记录是长度为1的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列的长度均扩大一倍；当有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列。算法是： void Merge_sort(Sqlist *L, RecType DR[]) { int d=1 ; while(d { Merge_pass(L->R, DR, d, L->length) ; Merge_pass(DR, L->R, 2*d, L->length) ; d=4*d ; } } 具有n个待排序记录的归并次数是㏒2n，而一趟归并的时间复杂度为O(n)，则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(n㏒2n)。在排序过程中，使用了辅助向量DR，大小与待排序记录空间相同，则空间复杂度为O(n)。归并排序是稳定的。 ===============================================================================各种内部排序的比较: 各种内部排序按所采用的基本思想(策略)可分为：插入排序、交换排序、选择排序、归并排序和基数排序，它们的基本策略分别是： 1 插入排序：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序一个子序列的适当位置，直到所有的记录都插入为止。具体的方法有：直接插入、表插入、2-路插入 和shell排序。 2 交换排序：对于待排序记录序列中的记录，两两比较记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。具体的方法有：冒泡排序、快速排序。 3 选择排序：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。具体的方法有：简单选择排序、堆排序。 4 归并排序：利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。 5 基数排序：按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。 各种内部排序方法的性能比较如下表。 文件的基本概念 ⑴ 数据项(Item或field) ：数据文件中最小的基本单位，反映实体某一方面的特征—属性的数据表示。 ⑵ 记录(Record) ：一个实体的所有数据项的集合。 用来标识一个记录的数据项集合(一个或多个)称为关键字项(Key) ，关键字项的值称为关键字；能唯一标识一个记录的关键字称为主关键字(Primary Key)，其它的关键字称为次关键字(Secondary Key) 。 利用外存对数据文件进行排序称为外部排序。 算法部分： 素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\\n” , n) ; else printf(“&d 不是一个素数\\n” , n) ; } ---------------------------------------------------------------------- 冒泡排序法。 Void bubble_sort(int a[]，int n)