NOI排序算法课程胶片

排序冒泡排序快速排序直接插入排序希尔排序选择排序小结冒泡排序算法描述设待排序记录序列中的记录个数为n一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。算法示例1212525*16080123452125*49251649chang=10825*chang=10816chang=125*2521492125160849i=0i=1i=2i=3算法示例225*012345i=44916chang=108252125*i=54916chang=0082521总体演示210825492516214925251608214925251608214925251608214925251608214925251608初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序算法实现输入n个数给a[1]到a[n]forj=1ton-1fori=1ton-ja[i]>a[i+1]真假a[i]a[i+1]输出a[1]到a[n]#include<stdio.h>main(){inta[11],i,j,t;printf("Input10numbers:\n");for(i=1;i<11;i++){scanf("%d",&a[i]);}printf("\n");for(j=1;j<=9;j++){for(i=1;i<=10-j;i++){if(a[i]>a[i+1]){

t=a[i];a[i]=a[i+1];a[i+1]=t;}}}printf("Thesortednumbers:\n");for(i=1;i<11;i++){ printf("%d",a[i]);}}冒泡排序快速排序直接插入排序希尔排序选择排序小结快速排序快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分一部分所有记录的关键码大于等于支点记录的关键码另一部分所有记录的关键码小于支点记录的关键码算法描述任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列左侧子序列中所有记录的关键字都小于或等于基准记录的关键字右侧子序列中所有记录的关键字都大于基准记录的关键字基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey指针low指向序列第一个记录位置指针high指向序列最后一个记录位置算法示例12108254925*16始关键字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交换二次交换三次交换high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法示例212254925*162108254925*162108完成一趟排序分别进行快速排序有序序列08254925*1621算法分析快速排序是一个递归过程;利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况13冒泡排序快速排序直接插入排序希尔排序选择排序小结直接插入排序算法描述：记录存放在数组R[0….n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]和R[i….n-1]，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。基本操作将当前无序区的第1个记录R[i]插入到有序区R[0….i-1]中适当的位置，使R[0…i]变为新的有序区

直接插入排序操作细节：当插入第i(i≥1)个对象时,前面的r[0],r[1],…,r[i-1]已经排好序。用r[i]的关键字与r[i-1],r[i-2],…的关键字顺序进行比较(和顺序查找类似)，如果小于，则将r[x]向后移动(插入位置后的记录向后顺移)找到插入位置即将r[i]插入直接插入排序实用例子：已知待序的一组记录的初始排列为：21,25,49,25*,16,0821254925*1608012345算法示例012345temp21254925*160825i=1012345temp21254925*160849i=221254925*1608012345i=325*算法示例012345temp21254925*1608i=416012345temp21254925*1608i=50821254925*1608012345完成算法实现voidInsertSort(intr[],intn){//假设关键字为整型，放在向量r[]中

inti,j,temp; for(i=1;i<n;i++){temp=r[i];for(j=i;j>0;j--){//从后向前顺序比较，并依次后移if(temp<r[j-1]) r[j]=r[j-1]; else break;}r[j]=temp;}}算法分析关键字比较次数和记录移动次数与记录关键字的初始排列有关。最好情况下,排序前记录已按关键字从小到大有序,每趟只需与前面有序记录序列的最后一个记录比较1次,移动2次记录,总的关键字比较次数为n-1,记录移动次数为2(n-1)在平均情况下的关键字比较次数和记录移动次数约为n2/4。直接插入排序是一种稳定的排序方法直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法

冒泡排序快速排序直接插入排序希尔排序选择排序小结希尔排序希尔排序又称缩小增量排序是1959年由D.L.Shell提出来的

算法描述首先取一个整数gap<n(待排序记录数)作为间隔,将全部记录分为gap个子序列,所有距离为gap的记录放在同一个子序列中在每一个子序列中分别施行直接插入排序。然后缩小间隔gap,例如取gap=gap/2重复上述的子序列划分和排序工作，直到最后取gap=1,将所有记录放在同一个序列中排序为止。算法示例已知待排序的一组记录的初始排列为：21,25,49,25*,16,080123452108254925*16算法示例t30123452108254925*160123452108254925*16t22108254925*162108254925*16t12108254925*162108254925*16算法分析开始时gap的值较大,子序列中的记录较少,排序速度较快随着排序进展,gap值逐渐变小,子序列中记录个数逐渐变多,由于前面大多数记录已基本有序,所以排序速度仍然很快Gap的取法有多种。shell提出取gap=n/2，gap=gap/2，直到gap=1。冒泡排序快速排序直接插入排序希尔排序选择排序小结排序过程首先通过n-1次比较，从n个数中找出最小的，将它与第一个数交换—第一趟选择排序，结果最小的数被安置在第一个元素位置上再通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换—第二趟选择排序重复上述过程，共经过n-1趟排序后，排序结束排序示例初始：[49386597761327]kji=11349一趟：13[386597764927]i=22738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]kkkkjjjjjjjjjj算法示例212525*16080123452125*i=1492516251608490825*4921i=2i=3081625*2521初始49算法示例25*01234525*2516084925*492108162521最小者

25*无交换最小者

25无交换25211608各趟排序后的结果算法示例01234549160825*49210825*2521i=2时选择排序的过程ikj49250825*1621ikj492525*25162516<25ikj算法示例49250825*1621012345ikj2116k

指示当前序列中最小者算法实现输入n个数给a[1]到a[n]fori=1ton-1forj=i+1tona[j]<a[k]真假k=j输出a[1]到a[n]k=ia[i]a[k]i!=k真假#include<stdio.h>main(){

inta[11],i,j,k,x;printf("Input10numbers:\n");

for(i=1;i<11;i++){scanf("%d",&a[i]);}printf("\n");

for(i=1;i<10;i++)

{

k=i;

for(j=i+1;j<=10;j++){

if(a[j]<a[k])k=j;}

if(i!=k)

{

x=a[i];a[i]=a[k];a[k]=x;

}

}printf("Thesortednumbers:\n");

for(i=1;i<11;i++){ printf("%d",a[i]);}}冒泡排序快速排序直接插入排序希尔排序选择排序小结36基本概念排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕