下载文档原格式
数据结构第9章排序数据结构第9章排序第9章排名本章主要内容：1、插入类排序算法2、交换类排序算法3、选择类排序算法4、归并类排序算法5、基数类排序算法本章重点难点1、希尔排序2、快速排序3、堆排序4.合并排序9.1基本概念1.关键字可以标识数据元素的数据项。
如果一个数据项可以唯一地标识一个数据元素，那么它被称为主关键字；否则，它被称为次要关键字。
2．排序是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。
如果排序依据的是主关键字，排序的结果将是唯一的。
3.排序算法的稳定性如果要排序的记录序列中多个数据元素的关键字值相同，且排序后这些数据元素的相对顺序保持不变，则称排序算法稳定，否则称为不稳定。
4.内部排序与外部排序根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。
内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放在内存中，另一部分放在外围设备上。
整个排序过程需要在内存和外存之间进行多次数据交换才能得到排序结果。
本章仅讨论常用的内部排序方法。
5.排序的基本方法内部排序主要有5种方法：插入、交换、选择、归并和基数。
6.排序算法的效率评估排序算法的效率主要有两点：第一，在一定数据量的情况下，算法执行所消耗的平均时间。
对于排序操作，时间主要用于关键字之间的比较和数据元素的移动。
因此，我们可以认为一个有效的排序算法应该是尽可能少的比较和数据元素移动；第二个是执行算法所需的辅助存储空间。
辅助存储空间是指在一定数据量的情况下，除了要排序的数据元素所占用的存储空间外，执行算法所需的存储空间。
理想的空间效率是，算法执行期间所需的辅助空间与要排序的数据量无关。
7.待排序记录序列的存储结构待排序记录序列可以用顺序存储结构和和链式存储结构表示。
在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。
第一个关键字：auto用来声明自动变量。
可以显式的声明变量为自动变量。
只要不是声明在所有函数之前的变量，即使没加auto关键字，也默认为自动变量。
并且只在声明它的函数内有效。
而且当使用完毕后，它的值会自动还原为最初所赋的值。
自动变量使用时要先赋值，因为其中包含的是未知的值。
例：auto int name=1;第二个关键字：static用来声明静态变量。
可以显式的声明变量为静态变量。
也为局部变量。
只在声明它的函数内有效。
它的生命周期从程序开始起一直到程序结束。
而且即使使用完毕后，它的值仍旧不还原。
即使没有给静态变量赋值，它也会自动初始化为0.例：static int name=1.第三个关键字：extern用来声明全局变量。
同时声明在main函数之前的变量也叫全局变量。
它可以在程序的任何地方使用。
程序运行期间它是一直存在的。
全局变量也会初始化为0.例：extern int name；第四个关键字：register用来声明为寄存器变量。
也为局部变量，只在声明它的函数内有效。
它是保存在寄存器之中的。
速度要快很多。
对于需要频繁使用的变量使用它来声明会提高程序运行速度。
例：register int name=1;第五个关键字：int用来声明变量的类型。
int为整型。
注意在16位和32位系统中它的范围是不同的。
16位中占用2个字节。
32位中占用4个字节。
还可以显式的声明为无符号或有符号：unsigned int signed int .有符号和无符号的区别就是把符号位也当作数字位来存储。
也可用short和long来声明为短整型，或长整行。
例：int num;第六个关键字：float用来声明变量的类型。
float为浮点型，也叫实型。
它的范围固定为4个字节。
其中6位为小数位。
其他为整数位。
例：float name;第七个关键字：double用来声明为双精度类型。
它的范围为8个字节。
14位为小数位。
也可使用更高精度的long double 它的范围则更大，达到10字节。
C语言常用算法归纳应当掌握的一般算法一、基本算法：交换、累加、累乘二、非数值计算常用经典算法：穷举、排序（冒泡，选择）、查找（顺序即线性）三、数值计算常用经典算法：级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法）四、其他：迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形）详细讲解一、基本算法1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。
main(){ int a,b,t;scanf("%d%d",&a,&b);printf("%d,%d\n",a,b);t=a; a=b; b=t;printf("%d,%d\n",a,b);}【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。
假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。
其中t为中间变量，起到“空杯子”的作用。
注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。
main(){ int a,b,c,t;scanf("%d%d%d",&a,&b,&c);/*以下两个if语句使得a中存放的数最小*/if(a>b){ t=a; a=b; b=t; }if(a>c){ t=a; a=c; c=t; }/*以下if语句使得b中存放的数次小*/if(b>c) { t=b; b=c; c=t; }printf("%d,%d,%d\n",a,b,c);}2．累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。
常用的c语言排序算法主要有三种即冒泡法排序、选择法排序、插入法排序。
一、冒泡排序冒泡排序：是从第一个数开始，依次往后比较，在满足判断条件下进行交换。
代码实现（以降序排序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp;for (int i = 0; i < 10; i++){//循环次数for (int j = 0; j <10 - i-1; j++){if (array[j] < array[j+1]){//前面一个数比后面的数大时发生交换temp = array[j];array[j] = array[j+1];array[j + 1] = temp;}}} //打印数组for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}二、选择排序以升序排序为例：就是在指定下标的数组元素往后（指定下标的元素往往是从第一个元素开始，然后依次往后），找出除指定下标元素外的值与指定元素进行对比，满足条件就进行交换。
与冒泡排序的区别可以理解为冒泡排序是相邻的两个值对比，而选择排序是遍历数组，找出数组元素与指定的数组元素进行对比。
（以升序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp, index;for (int i = 0; i < 9; i++) {index = i;for (int j = i; j < 10; j++){if (array[j] < array[index])index = j;}if(i != index){temp = array[i]; array[i] = array[index]; array[index] = temp; }for(int i=0;i<10:i++) printf("%2d"array[i]）return 0；}三、快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
一插入排序1.1 直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。
图解：代码实现：[cpp]view plaincopy1.//直接顺序排序2.void InsertSort(int r[],int n)3.{4.for(int i=2;i<n;i++)5.{6.r[0]=r[i];//设置哨兵7.for(int j=i-1;r[0]<r[j];j--)//寻找插入位置8.r[j+1]=r[j];//记录后移9.r[j+1]=r[0];10.}11.for(int k=1;k<n;k++)12.cout<<r[k]<<"";13.cout<<"\n";14.}1.2 希尔排序基本思想是：先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
图解：代码实现：[cpp]view plaincopy1.<spanstyle="font-size:14px;">//希尔排序2.void ShellSort(int r[],int n)3.{4.int i;5.int d;6.int j;7.for(d=n/2;d>=1;d=d/2)//以增量为d进行直接插入排序8.{9.for(i=d+1;i<n;i++)10.{11.r[0]=r[i];//暂存被插入记录12.for(j=i-d;j>0&&r[0]<r[j];j=j-d)13.r[j+d]=r[j];//记录后移d个位置14.r[j+d]=r[0];15.}16.}17.for(i=1;i<n;i++)18.cout<<r[i]<<"";19.cout<<"\n";20.}</span>二交换排序2.1 起泡排序起泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。
一、常量数字常量i.普通数字：1，35，2.7ii.指数形式：2.45e-2等价于2.45*10-2注意e大小写皆可，e前面的数字不能省，就算是1也不能省，后面的数字一定要是整数iii.长整型，单精度浮点型：3235L，32.5F分别表示3235是长整型数据，32.5是单精度浮点型左，若不写上L，F则表示3235是整型，32.5是双精度浮点型，L，F大小写皆可字符常量i.普通字符常量：用单引号把一个字符括起来，如’A’,’@’ii.转义字符常量：一对单引号括起来并以“\”开头的字符序列，如’\n’(回车)、’\123’(8进制123对应的字符),’\x23’(16进制23对应的字符)字符串常量用一对双引号把一个字符序列括起来，如“ABCef”，系统存放字符串常量，每个字符分配一个字节，各字符所占字节紧邻，并且字符串末尾会给再开一个字节里面放一个’\0’做为结束标志。
符号常量定义格式#define符号常量名符号常量值，如#define N20则定义了符号常量N，其值为20，注意符号常量名和符号常量值之间是用空格隔开，而不是写上=号，#define和符号常量名之间也有空格的。
题目：P7—1，5，6，7，9，10二、标识符命名规则以数字，字母，下划线这三类字符组成，但只能以字母或下划线开头，而不能也数字开头，另外不能将关键字做为标识符。
32个关键字表在P365附录B变量名，函数名，符号常量名全都是标识符题目：P7—2，3，4三、变量变量的定义格式类型名变量名;如int a;定义了一个整型常量a。
变量名是由人类随便定义的，符合命名规则的前提下，爱写啥就写啥。
所以什么flag，cc，y1或者函数名fun,find等全部是自定的用来做为名字而已，没有更特别的意义。
类型名int整型，long长整型：用于存放整数，只是数值范围不同float单精度浮点型double双精度浮点型：用于存放实数，数值范围，精度不同char字符型：用于存放字符变量赋值，初始化int a=3;定义的同时初始化a=6*9;定义后在程序中进行赋值变量的值只有在赋值操作时才会被改变，即将其放在等号左边时才会改变它的值，或自增自减操作：a=5,a++,a--，像a+3并未改变a的值，只是使用了a的值而已.自增自减运算变量++,++变量，变量--，--变量使变量的值自增1或自减1等价于变量=变量+1变量=变量-1++，--放于变量前后效果的区别：当自增自减运算做为表达式的一部分时，++，--放在变量前面是先自增自减再使用变量的值，放在变量后面则是先使用变量的值，再自增自减。
c语言基数排序算法基数排序是一种非比较整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
以下是基数排序的C语言实现：```cinclude <>include <>void radixsort(int arr, int n) {int max_digit = 0;for (int i = 0; i < n; i++) {int num = arr[i];int count = 0;while (num) {num /= 10;count++;}if (count > max_digit) {max_digit = count;}}for (int exp = 1; max_digit >= exp; exp = 10) { int count[10] = {0};for (int i = 0; i < n; i++) {int num = arr[i] / exp;count[num % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}int temp[n];for (int i = n - 1; i >= 0; i--) {temp[count[arr[i] / exp % 10] - 1] = arr[i]; count[arr[i] / exp % 10]--;}for (int i = 0; i < n; i++) {arr[i] = temp[i];}}}int main() {int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};int n = sizeof(arr) / sizeof(arr[0]);radixsort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;}```该算法的时间复杂度为O(d(n+k))，其中d为整数的位数，n为待排序数组的长度，k为桶的数量。
C语言9种常用排序法1.冒泡排序2.选择排序3.插入排序4.快速排序5.希尔排序6.归并排序7.堆排序8.带哨兵的直接插入排序9.基数排序例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序#include<stdio.h>int main(){int i, j, n, a[100], temp;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n-1;i++) //总共需冒泡n-1次{for(j=0;j<n-i-1;j++) //第i趟冒泡{if(a[j]>a[j+1]) //比较a[j]与a[j+1],使a[j+1]大于a[j] {temp = a[j+1];a[j+1] = a[j];a[j] = temp;}}}for(i=0;i<n;i++) //打印printf("%d ",a[i]);printf("\n");}return 0;}2.选择排序#include<stdio.h>int main(){int i, j, n, a[100], t, temp;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n-1;i++) //总共排序n-1趟{t = i;for(j=i+1;j<n;j++) //第i趟从a[i+1]~a[n-1]中选最小的数与a[i]交换 {if(a[t]>a[j])t = j;}temp = a[i];a[i] = a[t];a[t] = temp;}for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}return 0;}3.快速排序/*1.假设数组为a[n]；2.第一次排序过程如下：取x = 0 ( a[0]为中轴 )；i=0 (第一个元素下标), j=n-1(最后一个元素下标)；重复下面过程：(直到i>=j){从a[j]起，向前找小于a[x]的元素，同时j--，找到后，a[j]与a[x]交换，x=j;从a[i]起，向后找大于a[x]的元素，同时i++，找到后，a[i]与a[x]交换，x=i; }3.注意快排函数是迭代函数，必须要有结束条件 (因为忽略结束条件,调试了很久......)4.再对a[low]~a[x-1]、a[x+1]~a[high]分别调用快排函数*/#include<stdio.h>void quicksort(int a[],int low,int high);int main(){int i, n, a[100];while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);quicksort(a,0,n-1);for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}return 0;}void quicksort(int a[],int low,int high){if(low>=high) return; //坑爹的结束条件，return后面不能跟数值 int i=low, j= high, x=i, temp;while(i<j){for(;a[j]>=a[x]&&i<j;j--);if(i<j){temp = a[j];a[j] = a[i];a[i] = temp;x = j;i++;}elsebreak; //i>=j即可跳出本次while循环for(;a[i]<=a[x]&&i<j;i++);if(i<j){temp = a[i];a[j] = temp;x = i;j--;}elsebreak; //跳出本次while循环 }quicksort(a,low,x-1);quicksort(a,x+1,high);}4.插入排序法#include<stdio.h>void show(int a[],int n) //输出数组{int i;for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}void insertsort(int a[],int n);int main(){while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);insertsort(a,n);show(a,n);}return 0;}void insertsort(int a[],int n){int i ,j ,k ,temp;for(i=1;i<n;i++) //插入a[i]{j=i-1;for(;a[i]<a[j]&&j>=0;j--); //寻找插入点j++;if(j==i) //该数有序，不需要前插continue;else{temp=a[i];for(k=i-1;k>=j;k--) //将插入点后面的数依次后移一位 {a[k+1]=a[k];}}}}5.shell排序法#include<stdio.h>void show(int a[],int n) //输出数组{int i;for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}void shellsort(int a[],int n);int main(){int i, n, a[100];while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);shellsort(a,n);show(a,n);}return 0;}void shellsort(int a[],int n){int k ,i ,j ,l ,temp;k = n/2;while(k>=1){for(i=k;i<n;i++){if(a[i]>=a[i-k]) //已经有序，不需要移动continue;else{for(j=i-k;a[j]>=a[i]&&j>=0;j=j-k); j+=k; //寻找插入点a[j] temp = a[i]; // 保存a[i]for(l=i-k;l>=j;l-=k) //依次向后移动k个位置{a[l+k] = a[l];}a[j]=temp; //插入}}k = k/2;}}6.归并排序归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。
并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。
串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。
在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序算法流程图：/*伪代码：mergesort(int a[],int low,int high)；if(high-low+1>2)执行如下几步：(3个及以上)mid = (0+n)/2;mergesort(a,low,mid-1);mergesort(a,mid,high);进行本轮二路归并；bsort(int low,int mid,int high);i=low,j=mid;while(i<mid&&j<=high){先归并入other[];}将剩下的归并入数组other[]；将other[low~high],复制到a[low~high];else: (3个以下)if(a[low]>=a[high]) 交换a[low],a[high]; */#include<stdio.h>int other[100];void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}void show(int a[],int n) //输出数组{int i;for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}void mergesort(int a[],int low,int high);int main(){int i, n, a[100];while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);mergesort(a,0,n-1);show(a,n);}return 0;}void mergesort(int a[],int low,int high) {if((high-low+1)>2) //含3个以上 {int mid = (high+low)/2;mergesort(a,low,mid);mergesort(a,mid+1,high);int i=low, j=mid+1, k=low;while(i<=mid&&j<=high){if(a[i]<=a[j]){other[k++]=a[i++]; }if(a[i]>a[j]){other[k++]=a[j++]; }}while(i<=mid){other[k++]=a[i++];}while(j<=high){other[k++]=a[j++];}for(i=low;i<=high;i++)a[i]=other[i];}else //含2及个以下{if(a[low]>a[high]){exchange(a+low,a+high); }}}7.堆排序//堆排序/*(堆是一个完全二叉树，根结点值最大(小))1.heapadjust(int a[],int i,int sizea) 功能:以a[i]为根，形成一个堆buildheap(int a[],int sizea) 功能:调用heapadjust()，使a[]形成一个堆 heapsort(int a[],int sizea) 功能:do{建堆，输出堆顶}while(堆不空) */#include<stdio.h>void show(int a[],int n) //输出数组{int i;for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");}void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}void heapadjust(int a[],int i,int sizea){int maxi=i;int l=2*i+1;int r=2*i+2;if(i<(sizea/2)) //a[i]为叶结点，则不需要调整{if(l<=(sizea-1)&&a[l]>a[i]) //左孩子比a[i]大的，取左孩子下标{maxi=l;}if(r<=(sizea-1)&&a[r]>a[maxi]) //右孩子最大，取右孩子下标{maxi=r;}if(maxi!=i) //取比根大的孩子，与根调换{exchange(&a[maxi],&a[i]);heapadjust(a,maxi,sizea); //跌倒，以a[maxi]为根，向下调整为大根堆。
