热门标签
当前位置: article > 正文
第八章 排序--以下代码由C语言实现
作者：我家自动化 | 2024-07-19 04:04:41
赞
踩
第八章 排序--以下代码由C语言实现
王道学习
考纲内容
（一）排序的基本概念
（二）插入排序
直接插入排序；折半插入排序；希尔排序(shell sort)
（三）交换排序
冒泡排序(bubble sort)；快速排序
（四）选择排序
简单选择排序；堆排序
（五）二路归并排序(merge sort)
（六）基数排序
（七）外部排序
（八）排序算法的分析和应用
知识框架
复习提示
堆排序、快速排序和归并排序是本章的重难点。读者应深入掌握各种排序算法的思想、排序过程(能动手模拟)和特征(初态的影响、复杂度、稳定性、适用性等)，通常以选择题的形式考查不同算法之间的对比。此外，对于一些常用排序算法的关键代码，要达到熟练编写的程度；看到某特定序列，读者应具有选择最优排序算法(根据排序算法特征)的能力。
8.1 排序的基本概念
8.1.1 排序的定义
8.1.2 本节试题精选
8.2 插入排序
插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。
8.2.1 直接插入排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 直接插入排序（无哨兵） */ void insertSortWithoutSentry(int *array,int length){ int tmp=0; int i=1; int j=0; for(;i<length;i++){ if(array[i]<array[i-1]){ tmp=array[i]; for(j=i-1;j>=0&&array[j]>tmp;j--){ array[j+1]=array[j]; } array[j+1]=tmp; } printf("第%d轮：",i); printfArray(array,length); } } /** * 直接插入排序（有哨兵） */ void insertSortWithSentry(int *array,int length){ int tmp=0; int i=2; int j=0; for(;i<length;i++){ if(array[i]<array[i-1]){ array[0]=array[i]; for(j=i-1;array[j]>array[0];j--){ array[j+1]=array[j]; } array[j+1]=array[0]; } array[0]=0; printf("第%d轮：",i-1); printfArray(array,length); } } int main(){ int arrayOne[8]={49,38,65,97,76,13,27,49}; insertSortWithoutSentry(arrayOne,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); int arrayTwo[9]={0,49,38,65,97,76,13,27,49}; insertSortWithSentry(arrayTwo,sizeof(arrayTwo)/sizeof(int)); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
8.2.2 折半插入排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 折半插入排序（有哨兵） */ void insertSortHalf(int *array,int length){ int tmp=0; int i=2; int j=0; int low=0; int high=0; int mid=0; for(;i<length;i++){ if(array[i]<array[i-1]){ array[0]=array[i]; low=1; high=i-1; while(low<=high){ mid=(low+high)/2; if(array[mid]>array[0]){ high=mid-1; }else{ low=mid+1; } } for(j=i-1;j>=high+1;--j){ array[j+1]=array[j]; } array[high+1]=array[0]; } array[0]=0; printf("第%d轮：",i-1); printfArray(array,length); } } int main(){ int arrayThree[9]={0,49,38,65,97,76,13,27,49}; insertSortHalf(arrayThree,sizeof(arrayThree)/sizeof(int)); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
8.2.3 希尔排序
从前面的分析得知，直接插入排序算法的时间复杂度为O(n^2)，但若待排序列为“正序”时，其时间复杂度可提高至O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进得来的，又称为缩小增量排序。
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 希尔排序（有哨兵） */ void shellSortOneWithSentry(int *array,int length){ int d=0; int i=0; int j=0; for(d=length/2;d>=1;d=d/2){ for(i=d+1;i<length;++i){ if(array[i]<array[i-d]){ array[0]=array[i]; for(j=i-d;j>0&&array[0]<array[j];j=j-d){ array[j+d]=array[j]; } array[j+d]=array[0]; } array[0]=0; printfArray(array,length); } } } /** * 希尔排序（有哨兵） */ void shellSortTwoWithSentry(int *array,int length){ int d=0; int i=0; int j=0; int tmp=0; for(d=length/2;d>=1;d=d/2){ for(tmp=1;tmp<=d;tmp++){ for(i=tmp+d;i<length;i=i+d){ if(array[i]<array[i-d]){ array[0]=array[i]; for(j=i-d;j>0&&array[0]<array[j];j=j-d){ array[j+d]=array[j]; } array[j+d]=array[0]; } array[0]=0; printfArray(array,length); } } } } int main(){ int arrayOne[9]={0,49,38,65,97,76,13,27,49}; shellSortOneWithSentry(arrayOne,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); int arrayTwo[9]={0,49,38,65,97,76,13,27,49}; shellSortTwoWithSentry(arrayOne,sizeof(arrayOne)/sizeof(int)); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
8.2.4 本节试题精选
8.3 交换排序
所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序，其中冒泡排序算法比较简单，一般很少直接考查，通常会重点考查快速排序算法的相关内容。
8.3.1 冒泡排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 冒泡排序 */ void bubbleSort(int *array,int length){ int i=0; int j=0; int tmp=0; for(i=0;i<length-1;i++){ for(j=length-1;j>i;j--){ if(array[j-1]>array[j]){ tmp=array[j-1]; array[j-1]=array[j]; array[j]=tmp; } } printfArray(array,length); } } /** * 改进版--冒泡排序 * 最好情况下的时间复杂度：如果元素本来就是有序的， * 那么一趟冒泡排序既可以完成排序工作，比较和移动元素的次数分别是n-1和0，因此最好情况的时间复杂度为O（n）。 * * 最差情况的时间复杂度：如果数据元素本来就是逆序的，许哟啊进行n-1趟排序， * 所需比较和移动次数分别为n（n-1）/2和3n(n-1)/2。因此最坏情况子下的时间复杂度为O(n^2)。 * * 稳定性：因为每次比较后如果两个相邻元素相等我们并不会将他们交换，所以冒泡不会改变相同元素的下标，所以冒泡排序是一个稳定的排序。 */ void bubbleSortTwo(int *array,int length){ int i=0; int j=0; int tmp=0; int didSwap=0; for(i=0;i<length-1;i++){ for(j=length-1;j>i;j--){ if(array[j-1]>array[j]){ tmp=array[j-1]; array[j-1]=array[j]; array[j]=tmp; didSwap=1; } } if(didSwap==0){ return ; } printfArray(array,length); } } int main(){ int arrayOne[9]={0,49,38,65,97,76,13,27,49}; bubbleSort(arrayOne,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
8.3.2 快速排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } int partition(int *array,int low,int high){ int pivot=array[low]; while(low<high){ while(low<high&&array[high]>=pivot){ --high; } array[low]=array[high]; while(low<high&&array[low]<=pivot){ ++low; } array[high]=array[low]; } array[low]=pivot; return low; } /** * 快速排序 */ void quickSort(int *array,int low,int high,int length){ if(low<high){ int pivotpos=partition(array,low,high); printfArray(array,length); quickSort(array,low,pivotpos-1,length); quickSort(array,pivotpos+1,high,length); } } int main(){ int low=0; int high=0; int length=0; int arrayOne[8]={49,38,65,97,76,13,27,49}; length=sizeof(arrayOne)/sizeof(int); high=length-1; quickSort(arrayOne,low,high,length); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
8.3.3 本节试题精选
8.4 选择排序
选择排序的基本思想是:每一趟（如第i趟）在后面n-i+1 (i= 1,2…,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完,待排序元素只剩下1个，就不用再选了。选择排序中的堆排序算法是历年考查的重点。
8.4.1 简单选择排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 简单选择排序 */ void selectSort(int *array,int length){ int i=0; int min=0; int j=0; int temp=0; for(;i<length-1;i++){ min=i; for(j=i+1;j<length;j++){ if(array[j]<array[min]){ min=j; } } if(min!=i){ temp=array[i]; array[i]=array[min]; array[min]=temp; } printfArray(array,length); } } int main(){ int arrayOne[8]={49,38,65,97,76,13,27,49}; selectSort(arrayOne,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
8.4.2 堆排序
8.4.2.1 建堆
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 建立大根堆 */ void buildMaxHeap(int *array,int sortLength,int length){ int i=0; for(i=sortLength/2;i>0;i--){ headAdjust(array,i,sortLength,length); } } /** * 将以k为根的子树调整为大根堆 */ void headAdjust(int *array,int k,int sortLength,int length){ int i=0; array[0]=array[k]; for(i=2*k;i<=sortLength;i=i*2){ if(i<sortLength&&i+1<sortLength){ if(array[i]<array[i+1]){ i++; } } if(array[0]>array[i]){ break; }else{ array[k]=array[i]; k=i; } } array[k]=array[0]; printfArray(array,length); } int main(){ int arrayOne[9]={0,53,17,78,9,45,65,87,32}; buildMaxHeap(arrayOne,sizeof(arrayOne)/sizeof(int)-1,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
8.4.2.2 基于大根堆进行排序
#include <stdio.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } /** * 建立大根堆 */ void buildMaxHeap(int *array,int length){ int i=0; for(i=length/2;i>0;i--){ headAdjust(array,i,length); } } /** * 将以k为根的子树调整为大根堆 */ void headAdjust(int *array,int k,int length){ int i=0; array[0]=array[k]; for(i=2*k;i<=length;i=i*2){ if(i<length&&i+1<length){ if(array[i]<array[i+1]){ i++; } } if(array[0]>array[i]){ break; }else{ array[k]=array[i]; k=i; } } array[k]=array[0]; } /** * 建立堆排序 */ void headSort(int *array,int sortLength,int length){ int i=0; int temp=0; buildMaxHeap(array,sortLength); for(i=sortLength;i>1;i--){ temp=array[i]; array[i]=array[1]; array[1]=temp; printfArray(array,length); headAdjust(array,1,i-1); } } int main(){ int arrayOne[9]={0,53,17,78,9,45,65,87,32}; headSort(arrayOne,sizeof(arrayOne)/sizeof(int)-1,sizeof(arrayOne)/sizeof(int)); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
8.4.2.3 算法效率分析
8.4.2.4 堆的插入与删除
8.4.3 本节试题精选
8.5 归并排序、基数排序和计数排序
8.5.1 归并排序
#include <stdio.h> #include <stdlib.h> void printfArray(int *array,int length){ int i=0; for(;i<length;i++){ printf("%d,",array[i]); } printf("\n"); } void merge(int *array,int low,int mid,int high){ int *b=(int *)malloc(7*sizeof(int)); int k=0; int i=0; int j=0; for(k=low;k<=high;k++){ b[k]=array[k]; } for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ if(b[i]<=b[j]){ array[k]=b[i++]; }else{ array[k]=b[j++]; } } while (i<=mid) { array[k++]=b[i++]; } while (j<=high) { array[k++]=b[j++]; } } void mergeSort(int *array,int low,int high){ if(low<high){ int mid=(low+high)/2; mergeSort(array,low,mid); mergeSort(array,mid+1,high); merge(array,low,mid,high); } } int main(){ //int arrayOne[9]={38,49,65,97,13,27,76}; // merge(arrayOne,0,3,6); // printfArray(arrayOne,7); int arrayOne[9]={49,38,65,97,76,13,27}; mergeSort(arrayOne,0,6); printfArray(arrayOne,7); printf("---------------------------\n"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
8.5.2 基数排序
8.5.3 计数排序
在计数排序算法的实现中，假设输入是一个数组A[n]，序列长度为n，我们还需要两个数组：B[n]存放输出的排序序列，C[k]存储计数值。用输入数组A中的元素作为数组C的下标(索引)，而该元素出现的次数存储在该元素作为小标的数组C中。算法如下：
8.5.3 本节试题精选
8.6 各种内部排序算法的比较和应用
8.6.1 内部排序算法的比较
8.6.2 内部排序算法的应用
通常情况，对排序算法的比较和应用应考虑以下情况。
8.6.3 本节试题精选
8.7 外部排序
8.7.1 外部排序的基本概念
前面介绍过的排序方法都是在内存中进行的(称为内部排序)。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。这种排序方法就称为外部排序。
8.7.2 外部排序的方法
8.7.3 败者树
8.7.4 置换-选择排序（生成初始归并段）
8.7.5 最佳归并树
8.7.6 本节试题精选
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/849314
推荐阅读
相关标签
