排序的对象
顺序结构
类似线性表的顺序存储，将文件f=(R1,R2,R3.....Rn)存在一片连续的
存储空间，逻辑上相邻的记录在存储器中的物理位置也是相邻的。在这种结构上对文件排序，一半要
作记录的移动，当发生成片记录移动时，是一个很耗时的工作。
链表结构
类似与线性表的链式存储，文件中记录用结点来表示，其物理位置任意，结点之间用指针相连
排序算法
交换法——冒泡排序
设待排序文件f=(R1,R2,R3.....Rn),相应key集合k={k1,k2,k3,k4......kn}。
排序方法，从k1起，两两key进行比较，逆序时交换，即：
k1~k2,若k1>k2,则R1<=>R2(交换);
k2~k3,若k2>k3,则R2<=>R3(交换);
......
kn-1~kn,若kn-1>kn,则Rn-1<=>Rn(交换);
经过一趟比较之后，最大key的记录被沉低，类似水泡。接着对n-1个记录重复上述过程知道排序完毕
冒泡排序的时间复杂度T(n) = O(n^2).
注意：在某一趟排序比较中，若发现两两笔记哦啊无一记录交换说明文件已经有序，不必进行到最后两个记录的比较。
冒泡排序属于稳定排序，跑的总趟数等于n-1趟。
算法描述
void Bunsort(sqfile F) {
int i, flag, j;
Retype temp;
for (i = F.len; i >= 2; i--) {
flag = 0;
for(j = 1; j <= i-1; j++) {
if(F.R[j].key>F.R[j+1]) {
temp = F.R[j];
F.R[j] = F.R[j+1];
F.R[j+1] = temp;
flag = 1;
}
}
if(flag == 0) {
break;
}
}
}
c语言算法 链表冒泡排序
typedef int Datatype;
typedef struct node{
Datatype data;
struct node *next;
}linkNode, *linkP;
int BubbleSort(linkP L) {
linkP p = L,x,y;
LinkP tMax = NULL;
if (L->next == NULL) {
return 0;
} else if (L->next->next == NULL) {
return 0
} else {
while (tMax != L->next->next) {
for (p=L; p ->next->next != tMax;p=p->next) {
if (p->next->data > p->next->next->data) {
x = p->next;
y = p->next->next;
p->next = y;
x->next = y->next;
y->next = x;
}
}
tMax = p->next;
}
}
}
快速排序
排序方法
经过key的一趟比较后，确定某个记录在排序后的最终位置。
快速排序的基本思想是，通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。
详细描述：首先在要排序的序列 a 中选取一个中轴值，而后将序列分成两个部分，其中左边的部分 b 中的元素均小于或者等于 中轴值，右边的部分 c 的元素 均大于或者等于中轴值，而后通过递归调用快速排序的过程分别对两个部分进行排序，最后将两部分产生的结果合并即可得到最后的排序序列。
“基准值”的选择有很多种方法。最简单的是使用第一个记录的关键字值。但是如果输入的数组是正序或者逆序的，就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”，这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。
为了实现一次划分，我们可以从数组（假定数据是存在数组中）的两端移动下标，必要时交换记录，直到数组两端的下标相遇为止。为此，我们附设两个指针（下角标）i 和 j， 通过 j 从当前序列的有段向左扫描，越过不小于基准值的记录。当遇到小于基准值的记录时，扫描停止。通过 i 从当前序列的左端向右扫描，越过小于基准值的记录。当遇到不小于基准值的记录时，扫描停止。交换两个方向扫描停止的记录 a[j] 与 a[i]。 然后，继续扫描，直至 i 与 j 相遇为止。扫描和交换的过程结束。这是 i 左边的记录的关键字值都小于基准值，右边的记录的关键字值都不小于基准值。
通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。快速排序方法在要排序的数据已经有序的情况下最不利于发挥其长处。
下面我们通过一个案例来演示一下快速排序的基本步骤： 以序列 46 30 82 90 56 17 95 15 共8个元素
算法描述
初始状态： 46 30 82 90 56 17 95 15 选择46 作为基准值，i = 0， j = 7
i = 0 j = 7
15 30 82 90 56 17 95 46 15 < 46， 交换 15 和 46，移动 i， i = 1
i = 1 j = 7
15 30 82 90 56 17 95 46 30 < 46， 不需要交换，移动 i ， i = 2
i = 2 j = 7
15 30 46 90 56 17 95 82 82 > 46， 交换82 和 46，移动 j ， j = 6
i = 2 j = 6
15 30 46 90 56 17 95 82 95 > 46， 不需要交换，移动 j ， j = 5
i = 2 j = 5
15 30 17 90 56 46 95 82 17 < 46， 交换46 和 17，移动 i， i = 3
i = 3 j = 5
15 30 17 46 56 90 95 82 90 > 46， 交换90 和 46，移动 j ， j = 4
3 = i j = 4
15 30 17 46 56 90 95 82 56 > 46， 不需要交换，移动 j ， j = 3
i = j = 3
i = j = 3， 这样序列就这样分割成了两部分，左边部分{15， 30， 17} 均小于 基准值（46）；右边部分 {56， 90，95，82}，均大于基准值。这样子我们就达到了分割序列的目标。在接着对子序列用同样的办法进行分割，直至子序列不超过一个元素，那么排序结束，整个序列处于有序状态。
算法c语言实现
#define MAX_NUM 80
void quicksort(int* a, int p,int q) {
int i = p;
int j = q;
int temp = a[p];
while(i < j) {
// 越过不小于基准值的数据
while( a[j] >= temp && j > i ) j--;
if( j > i ) {
a[i] = a[j];
i++;
// 越过小于基准值的数据
while(a[i] <= temp && i < j ) i++;
if( i < j ) {
a[j] = a[i];
j--;
}
}
}
a[i] = temp;
for(int k = p; k <= q;k++) {
if( k == i ) {
printf("(%d) ",a[k]);
continue;
}
printf("%d ",a[k]);
}
printf("\n");
if( p < (i-1)) quicksort(a,p,i-1);
if((j+1) < q ) quicksort(a,j+1,q);
}
插入法排序
插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。
然后第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序；
第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序；
.....
.....
第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了。
它的递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了。
算法实现
void insertSort<T>(T a[]){
for(int p = 1; p < a.length; p++) {
T tmp = a[p];//保存当前位置p的元素，其中[0,p-1]已经有序
int j;
for(j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--) {
a[j] = a[j-1];//后移一位
}
a[j] = tmp;//插入到合适的位置
}
}
复杂度分析
①插入排序的时间复杂度 就是判断比较次数有多少，而比较次数与 待排数组的初始顺序有关，当待排数组有序时，没有移动操作（第8行for不成立），此时复杂度为O(N)，当待排数组是逆序时，比较次数达到最大--对于下标 i 处的元素，需要比较 i-1 次。总的比较次数：1+2+...+N-1 ，故时间复杂度为O(N^2)
①可以看出，算法中只用到了一个临时变量（第6行），故空间复杂度为O(1)
其实，插入排序的比较次数与数组的逆序数相关，因为插入排序在将某个元素插入到合适位置时（代码第12行），其实就是消除这个元素的逆序数。
由定理：N个互异数的数组的平均逆序数是 N(N-1)/4，可知：基于相邻元素之间的比较和交换的算法的时间复杂度的一个下界为O(N^2)
比较冒泡排序啊。。。。它采用的思路是：相邻两个元素比较，将小的放在前头。故冒泡排序的时间复杂度为O(N^2)。。。
基于上面这个定理，另外一个排序算法：希尔排序，采用了增量序列。因此，它可能获得一个更好的时间复杂度。
比如，当希尔排序使用Hibbard增量序列时，它的最坏运行时间为O(N3/2)
网友评论