浙大数据结构Week9
课程地址：https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。
这周主要讲了几种排序算法，下面回顾下。
Part1:回顾
首先老师提了几个前提条件。
这里内部排序是指排序的数据可以一次性在内存中进行排序，与此对应的是外部排序，外部排序是指数据量很大，超过内存容量，无法一次性排序完成。
注：下述的$N$均代表排序元素个数，数组元素记为$A[i]$
1.冒泡排序
冒泡排序的算法是这样的，一共$N$轮，第$i$轮对前$N-i+1$个元素进行如下操作：从第一个元素开始，如果后一个元素比前一个元素小，则交换两个元素，操作完一步之后对第二个元素重复此操作，直至第$N-i+1$个元素。这样第$i$轮可以保证第$N-i+1$个元素是前$N-i+1$个元素中最大元素，所以第$1$轮使得第$N$个元素为最大元素，第$2$轮使得第$N-1$个元素为第二大的元素，以此类推$N$轮之后排序完成。
从以上过程中可以看出，只有两个元素不相等时才会进行交换，所以冒泡排序是稳定的。
伪代码如下：
2.插入排序
插入排序同样进行$N$轮操作，第$i$轮将第$i$个元素$A[i]$和前$i-1$个元素比较，找到第$j$个元素$A[j]$，使得 $ A[j]\le {A[i]}$且$A[j+1]>{A[i]}$,随后将$A[i]$放到$A[j]$后面，其余元素后移一位即可。这样操作使得第$i$轮之后前$i$个元素为从小到大排列，$N$轮之后元素按从小到大排列。
从以上操作可以看出,如果排序前$A[i]=A[j] {(i < j)}$,那么排序之后$ A[j]$ 依然在 $A[i]$之后。最后提一点，插入排序的过程可以用整理扑克牌来想象。
3.希尔排序
希尔排序是对插入排序的改进，具体如下所示。
不过对于希尔排序保序性的暂时不会证明，先留个坑。
最后列出常用的增量:
4.堆排序
堆排序的思路是利用堆的性质进行排序，老师这里介绍了两种算法。
算法1
构造最小堆，每次抛出最小元素，但这样需要额外的$O(N)$,不是很理想，所以老师给出了算法2。
算法2
构造最大堆，每次将最大堆的第一个元素和堆末尾的元素交换,这样最大元素的位置就确定了，然后将前$N-1$变为最大堆，重复此操作即可，这样就不需要额外的空间。
5.归并排序
归并排序的思路是分而治之，这里又有两种思路。
递归算法
先对数组前一半元素和后一半元素分别排序，然后对这两排序好的数组进行归并,将其整合为一个有序数组，如下图所示：
不妨设将$A,B$归并为数组$C$
从数组$A$和$B$的第一个元素开始，如果$A[0] < B[0]$,则$C[0]=A[0]$，然后比较$A[1]$和$B[0]$，否则$C[0]=B[0]$,然后比较$A[0]$和$B[1]$，重复此操作直至归并完成。从这个过程中可以看出需要使用递归算法,因为要排序$C$,需要$A$和$B$排序完成才能操作。
非递归算法
这里的思路是自底向上，结合图来说明。
第$i$步对相邻的$2^{i-1}$个元素进行排序，具体操作如下，第$i-1$步已对相邻的$2^{i-2}$个元素排序完毕，第$i$步对相邻两组已排序的元素进行归并操作即可。
这部分总结的比较简练，因为老师给的都是代码，所以这里不列出了，一并在后面作业中列出。
Part2:作业
- 作业1
09-排序1 排序（25 分）
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
数据6：105个顺序整数；
数据7：105个逆序整数；
数据8：105个基本有序的整数；
数据9：105个随机正整数，每个数字不超过1000。输入格式:
输入第一行给出正整数N（≤100000），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。输出格式:
在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。输入样例:
11
4 981 10 -17 0 -20 29 50 8 43 -5输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981
这题就是最基本的排序问题，下面分别使用各种排序算法尝试了一下。
冒泡排序
#include <stdio.h>
int main(){
int n;
scanf("%d",&n);
int a[n];
int i;
for (i=0;i<n;i++){
scanf("%d",&a[i]);
}
int p,j;
for(p=n-1;p>=0;p--){
int flag=0;
for(j=0;j<p;j++){
if(a[j]>a[j+1]){
int temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
flag=1;
}
}
if(flag==0){
break;
}
}
printf("%d",a[0]);
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
return 0;
}插入排序
#include <stdio.h>
int main(){
int n;
scanf("%d",&n);
int a[n];
int i;
for (i=0;i<n;i++){
scanf("%d",&a[i]);
}
int p,j;
for(p=1;p<n;p++){
int temp=a[p];
for(j=p;j>0&&a[j-1]>temp;j--){
a[j]=a[j-1];
}
a[j]=temp;
}
printf("%d",a[0]);
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
return 0;
}希尔排序
#include <stdio.h>
int main(){
/* 希尔排序 - 用Sedgewick增量序列 */
int n;
scanf("%d",&n);
int a[n];
int i;
for (i=0;i<n;i++){
scanf("%d",&a[i]);
}
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
int s;
for(s=0;Sedgewick[s]>=n;s++);
int D;
for(D=Sedgewick[s];D>0;D=Sedgewick[++s]){
int p,j;
for(p=D;p<n;p++){
int temp=a[p];
for(j=p;j>=D&&a[j-D]>temp;j-=D){
a[j]=a[j-D];
}
a[j]=temp;
}
}
printf("%d",a[0]);
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
return 0;
} 堆排序
#include <stdio.h>
void Swap(int *a,int *b);
void PercDown( int A[], int p, int N );
void HeapSort( int A[], int N );
int main(){
int n;
scanf("%d",&n);
int a[n];
int i;
for (i=0;i<n;i++){
scanf("%d",&a[i]);
}
HeapSort(a,n);
printf("%d",a[0]);
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
return 0;
}
//交换
void Swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
//最大堆下滤
void PercDown( int A[], int p, int N ){
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent,Child,x;
x=A[p];
for(Parent=p;(2*Parent+1)<N;Parent=Child){
Child=Parent*2+1;
if((Child<N-1)&&(A[Child]<A[Child+1])){
Child++;
}
if(x>=A[Child]){
break;
}else{
A[Parent]=A[Child];
}
}
A[Parent]=x;
}
//堆排序
void HeapSort( int A[], int N ){
int i;
//从有子节点的点开始
for(i=N/2-1;i>=0;i--){
PercDown(A,i,N);
}
for(i=N-1;i>0;i--){
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}归并排序
#include <stdio.h>
void Merge( int A[], int TmpA[], int L, int R, int RightEnd );
void Merge_pass(int A[],int TmpA[], int N, int length );
int main(){
int n;
scanf("%d",&n);
int a[n];
int i;
for (i=0;i<n;i++){
scanf("%d",&a[i]);
}
//判断是否为merge sort
int temp[n];
int length=1;
//printf("%d\n",flag1);
while(length<n){
//printf("%d %d\n",length,n);
Merge_pass(a,temp,n,length);
length*=2;
//printf("%d %d\n",length,a[0]);
Merge_pass(temp,a, n, length );
length*=2;
//printf("%d %d\n",length,a[0]);
}
printf("%d",a[0]);
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
return 0;
}
void Merge( int A[], int TmpA[], int L, int R, int RightEnd ){
//printf("1\n");
/* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd,NumElements,Tmp;
int i;
LeftEnd=R-1;/* 左边终点位置 */
Tmp=L; /* 有序序列的起始位置 */
NumElements=RightEnd-L+1;
while(L<=LeftEnd&&R<=RightEnd){
if(A[L]<=A[R]){
TmpA[Tmp++]=A[L++];/* 将左边元素复制到TmpA */
}else{
TmpA[Tmp++]=A[R++];/* 将右边元素复制到TmpA */
}
}
while(L<=LeftEnd){
TmpA[Tmp++]=A[L++];/* 直接复制左边剩下的 */
}
while(R<=RightEnd){
TmpA[Tmp++]=A[R++];/* 直接复制右边剩下的 */
}
for(i=0;i<NumElements;i++,RightEnd--){
A[RightEnd]=TmpA[RightEnd];/* 将有序的TmpA[]复制回A[] */
}
}
/* 两两归并相邻有序子列 */
void Merge_pass(int A[],int TmpA[], int N, int length ){
int i,j;
for(i=0;i<=N-2*length;i+=2*length){
Merge(A,TmpA,i,i+length,i+2*length-1);
}
if(i+length<N){
Merge(A,TmpA,i,i+length,N-1);
}else{
for(j=i;j<N;j++){
TmpA[j]=A[j];
}
}
}- 作业2
09-排序2 Insert or Merge（25 分）
According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.Output Specification:
For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0Sample Input 2:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6Sample Output 2:
Merge Sort
1 2 3 8 4 5 7 9 0 6
题目的意思是根据输出序列判断是归并排序还是插入排序，我的思路比较直接，就是按照插入排序的操作实施，如果中间有一步的结果和目标一致，则为插入排序，否则为归并排序。
#include <stdio.h>
void Merge( int A[], int TmpA[], int L, int R, int RightEnd );
void Merge_pass(int A[],int TmpA[], int N, int length );
int compare(int a[],int b[],int n);
int main(){
int n;
scanf("%d",&n);
int a[n],b[n],c[n];
int i;
//读取第一行,a[]给merge sort使用,b[]给Insertion Sort使用
for (i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
//读取第二行
for (i=0;i<n;i++){
scanf("%d",&c[i]);
}
//判断是否为merge sort
int temp[n];
int length=1;
int flag1=0;
int flag2=0;
//printf("%d\n",flag1);
while(length<n){
Merge_pass(a,temp,n,length);
length*=2;
//判断是否和题目相等，如果相等，再完成一遍
if(flag1==0){
flag1=compare(temp,c,n);
}else{
int k;
for(k=0;k<n;k++){
a[k]=temp[k];
}
break;
}
Merge_pass( temp, a, n, length );
length*=2;
//判断是否和题目相等，如果相等，再完成一遍
if(flag1==0){
flag1=compare(a,c,n);
}else{
break;
}
}
//printf("%d\n",flag1);
if(flag1){
printf("Merge Sort\n");
printf("%d",a[0]);
int i;
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
}else{
int p,j;
for(p=1;p<n;p++){
int temp=b[p];
for(j=p;j>0&&b[j-1]>temp;j--){
b[j]=b[j-1];
}
b[j]=temp;
if(flag2){
break;
}
flag2=compare(b,c,n);
}
printf("Insertion Sort\n");
printf("%d",b[0]);
int i;
for(i=1;i<n;i++){
printf(" %d",b[i]);
}
}
}
void Merge( int A[], int TmpA[], int L, int R, int RightEnd ){
/* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd,NumElements,Tmp;
int i;
LeftEnd=R-1;/* 左边终点位置 */
Tmp=L; /* 有序序列的起始位置 */
NumElements=RightEnd-L+1;
while(L<=LeftEnd&&R<=RightEnd){
if(A[L]<=A[R]){
TmpA[Tmp++]=A[L++];
}else{
TmpA[Tmp++]=A[R++];
}
}
while(L<=LeftEnd){
TmpA[Tmp++]=A[L++];
}
while(R<=RightEnd){
TmpA[Tmp++]=A[R++];
}
for(i=0;i<NumElements;i++,RightEnd--){
A[RightEnd]=TmpA[RightEnd];
}
}
/* 两两归并相邻有序子列 */
void Merge_pass(int A[],int TmpA[], int N, int length ){
int i,j;
for(i=0;i<=N-2*length;i+=2*length){
Merge(A,TmpA,i,i+length,i+2*length-1);
}
if(i+length<N){
Merge(A,TmpA,i,i+length,N-1);
}else{
for(j=i;j<N;j++){
TmpA[j]=A[j];
}
}
}
/*判断是否和输出一样*/
int compare(int a[],int b[],int n){
int flag=1;
int i;
for(i=0;i<n;i++){
if (a[i]!=b[i]){
flag=0;
break;
}
}
return flag;
} - 作业3
09-排序3 Insertion or Heap Sort（25 分）
According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.Output Specification:
For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0Sample Input 2:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9Sample Output 2:
Heap Sort
5 4 3 1 0 2 6 7 8 9
这题我的思路和上题一样，就是按照插入排序的操作实施，如果中间有一步的结果和目标一致，则为插入排序，否则为堆排序。
#include <stdio.h>
void Swap(int *a,int *b);
void PercDown( int A[], int p, int N );
int compare(int a[],int b[],int n);
int main(){
int n;
scanf("%d",&n);
int a[n],b[n],c[n];
int i;
//读取第一行,a[]给merge sort使用,b[]给Insertion Sort使用
for (i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
//读取第二行
for (i=0;i<n;i++){
scanf("%d",&c[i]);
}
//判断是否为heap sort
int temp[n];
int length=1;
int flag1=0;
int flag2=0;
//printf("%d\n",flag1);
//从有子节点的点开始
for(i=n/2-1;i>=0;i--){
PercDown(a,i,n);
}
for(i=n-1;i>0;i--){
Swap(&a[0],&a[i]);
PercDown(a,0,i);
if(flag1){
break;
}
flag1=compare(a,c,n);
}
if(flag1){
printf("Heap Sort\n");
printf("%d",a[0]);
int i;
for(i=1;i<n;i++){
printf(" %d",a[i]);
}
}else{
int p,j;
for(p=1;p<n;p++){
int temp=b[p];
for(j=p;j>0&&b[j-1]>temp;j--){
b[j]=b[j-1];
}
b[j]=temp;
if(flag2){
break;
}
flag2=compare(b,c,n);
}
printf("Insertion Sort\n");
printf("%d",b[0]);
int i;
for(i=1;i<n;i++){
printf(" %d",b[i]);
}
}
}
//交换
void Swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
//最大堆下滤
void PercDown( int A[], int p, int N ){
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent,Child,x;
x=A[p];
for(Parent=p;(2*Parent+1)<N;Parent=Child){
Child=Parent*2+1;
if((Child<N-1)&&(A[Child]<A[Child+1])){
Child++;
}
if(x>=A[Child]){
break;
}else{
A[Parent]=A[Child];
}
}
A[Parent]=x;
}
/*判断是否和输出一样*/
int compare(int a[],int b[],int n){
int flag=1;
int i;
for(i=0;i<n;i++){
if (a[i]!=b[i]){
flag=0;
break;
}
}
return flag;
}