排序实验报告
- 格式：doc
- 大小：83.00 KB
- 文档页数：9
实验五 排序
实验目的: 掌握几种排序的思想及算法
问题分析：
(一)直接插入排序
1. 排序思想
将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。
设待排序的记录顺序存放在数组R[1…n]中，在排序的某一时刻，将记录序列分成两部分：
◆ R[1…i-1]：已排好序的有序部分；
◆ R[i…n]：未排好序的无序部分。
显然，在刚开始排序时，R[1]是已经排好序的。
2 . 算法实现
void straight_insert_sort(Sqlist R)
{ int i, j ;
for (i=2; i<=n; i++)
{ R[0]=R[i]; j=i-1; /*设置哨兵*/
while( LT(R[0].key, R[j].key) )
{ R[j+1]=R[j];
j--;
} /* 查找插入位置 */
R[j+1]=R[0]; /* 插入到相应位置*/
}
}
（二）希尔排序
1. 排序思想
① 先取一个正整数d1(d1
② 取新的增量d2
2. 算法实现
先给出一趟希尔排序的算法，类似直接插入排序。
void shell_pass(Sqlist R, int d)
/* 对顺序表L进行一趟希尔排序, 增量为d */
{ int j, k ;
for (j=d+1; j<=n; j++)
{ R[0]=R[j] ; /* 设置监视哨兵 */
k=j-d ;
while (k>0&<(R[0].key, R[k].key) )
{ R[k+d]=R[k] ; k=k-d ; }
R[k+d]=R[0] ; }
}
然后在根据增量数组dk进行希尔排序。
void shell_sort(Sqlist R, int dk[], int t)
/* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序 */
{ int m ;
for (m=0; m
shll_pass(R, dk[m]) ;
}
增量序列取法
◆ 无除1以外的公因子；
◆ 最后一个增量值必须为1。
（三）简单选择排序
1. 排序思想
基本操作是：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，然后和第i个记录进行交换，i=1, 2, … n-1 。
2. 算法实现
void simple_selection_sort(Sqlist R)
{ int i, j,k;
for (i=1; i
{ k=i ;
for (j=i+1; j<=n;j++)
if ( LT(R[j].key, R[k].key) ) k=j ;
if (k!=i) /* 记录交换 */
{ R[0]=R[k]; R[k]=R[i];
R[i]=R[0];
}
}
}
（四）堆排序
1. 排序思想
① 对一组待排序的记录，按堆的定义建立堆；
② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；
③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；
④ 重复上述步骤，直到全部记录排好序为止。
排序过程中，若采用小根堆，排序后得到的是递减序列；若采用大根堆，排序后得到的是递增序列。
堆的调整——筛选
⑴ 堆的调整思想
输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”，如图10-10所示。
⑵ 堆调整算法实现
void Heap_adjust(Sqlist R, int low, int high) /* R[low..high]中记录关键字除R[low].key均满足堆定义 */
/* 调整R[low]的位置使之成为小根堆 */
{ R[0]=R[low] ; /*临时保存调整点R[low] */
for (k=2*low; k<=high; k=k*2)
{ if ((k
k++ ; /* 选择左、右孩子中关键字的最小者 */
if ( LT(R[k].key, R[0].key) )
{ R[j]=R[k] ; low=k ; }
else break ;
}
R[j]=R[0] ;
}
2. 堆的建立
利用筛选算法，可以将任意无序的记录序列建成一个堆，设R[1],R[2], …,R[n]是待排序的记录序列。
将二叉树的每棵子树都筛选成为堆。只有根结点的树是堆。第⌊n/2⌋个结点之后的所有结点都没有子树，即以第n/2个结点之后的结点为根的子树都是堆。因此，以这些结点为左、右孩子的结点，其左、右子树都是堆，则进行一次筛选就可以成为堆。同理，只要将这些结点的直接父结点进行一次筛选就可以成为堆…。
只需从第n/2个记录到第1个记录依次进行筛选就可以建立堆。
3.堆排序算法实现
堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。
void Heap_Sort(Sqlist R)
{ int i ;
for (i=n/2; i>0;ij--)
Heap_adjust(R, i , n) ; /*初始建堆*/
for (i=n; i>=1; i--)
{ R[0]=R[1] ; R[1]=R[i] ;
R[i]=R[0] ; /* 堆顶与最后一个交换 */
Heap_adjust(R, 1, i-1) ;
}
}
（五）快速排序
1. 排序思想
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。
2. 排序过程
设待排序的记录序列是R[s…t] ，在记录序列中任取一个记录(一般取R[s])作为参照(又称为基准或枢轴)，以R[s].key为基准重新排列其余的所有记录，方法是：
◆ 所有关键字比基准小的放R[s]之前；
◆ 所有关键字比基准大的放R[s]之后。
以R[s].key最后所在位置i作为分界，将序列R[s…t]分割成两个子序列，称为一趟快速排序。
3. 一趟快速排序方法
从序列的两端交替扫描各个记录，将关键字小于基准关键字的记录依次放置到序列的前边；而将关键字大于基准关键字的记录从序列的最后端起，依次放置到序列的后边，直到扫描完所有的记录。 设置指针low，high，初值为第1个和最后一个记录的位置。
设两个变量i，j，初始时令i=low，j=high，以R[low].key作为基准(将R[low]保存在R[0]中) 。
① 从j所指位置向前搜索：将R[0].key与R[j].key进行比较：
◆ 若R[0].key≤R[j].key ：令j=j-1，然后继续进行比较， 直到i=j或R[0].key>R[j].key为止；
◆ 若R[0].key>R[j].key ：R[j]R[i]，腾空R[j]的位置， 且令i=i+1；
② 从i所指位置起向后搜索：将R[0].key与R[i].key进行比较：
◆ 若R[0].key≥R[i].key ：令i=i+1，然后继续进行比较， 直到i=j或R[0].key
◆ 若R[0].key
重复①、②，直至i=j为止，i就是R[0](基准)所应放置的位置。
4. 算法实现
⑴ 一趟快速排序算法的实现
int quick_one_pass(Sqlist R , int low, int high)
{ int i=low, j=high ;
R[0]=R[i] ; /* R[0]作为临时单元和哨兵 */
do {
while (LQ(R[0].key, R[j].key)&&(j>i))
j-- ;
if (j>i) { R[i]=R[j] ; i++; }
while (LQ(R[i].key, R[0].key)&&(j>i))
i++ ;
if (j>i) { R[j]=R[i] ; j--; }
} while(i!=j) ; /* i=j时退出扫描 */
R[i]=R[0] ; return(i) ;
}
⑵ 快速排序算法实现
当进行一趟快速排序后，采用同样方法分别对两个子序列快速排序，直到子序列记录个为1为止。
① 递归算法
void quick_Sort(Sqlist R , int low, int high)
{ int k ;
if (low
{ k=quick_one_pass(R, low, high);
quick_Sort(R, low, k-1);
quick_Sort(R, k+1, high);
} /* 序列分为两部分后分别对每个子序列排序 */
}
② 非递归算法
void quick_Sort(Sqlist R , int low, int high)
{ int k , stack[MAX_STACK] , top=0;
do { while (low
{ k=quick_one_pass(R,low,high);
stack[++top]=high ; stack[++top]=k+1 ;
/* 第二个子序列的上,下界分别入栈 */
high=k-1 ;
}
if (top!=0)
{ low=stack[top--] ; high=stack[top--] ; }
