第4章-几种常见的排序算法

讲师：朱兴林第4章几种常见的排序算法本章目标本章概述几种常见排序算法。本章目标熟悉常见的查找算法和排序算法重点能够里用函数库提供的API进行查找或排序操作难点快速排序算法本章结构数据结构与算法初步常见的排序算法常见的排序算法冒泡排序快速排序直接插入排序希尔排序选择排序堆排序归并排序冒泡排序冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。冒泡排序是稳定的。算法时间复杂度是O(n^2)。算法描述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>

voidbubbling_sort(int*a,intn);

intmain(){inta[5]={5,4,3,2,1};bubbling_sort(a,5);

inti;for(i=0;i<5;i++){ printf("%d\n",a[i]);}}

voidbubbling_sort(int*a,intn){ inti,j,temp; for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }}}}快速排序算法描述快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。2108254925*16始关键字08254925*162108254925*1608254925*1608254925*1608254925*1621pivotkey一次交换二次交换三次交换high-1完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh算法实例254925*162108254925*162108完成一趟排序分别进行快速排序有序序列08254925*1621算法实例#include<stdio.h>

voidquick_sort(int*a,intstart,intend);

intmain(){ inta[5]={4,2,6,8,1}; quick_sort(a,0,4); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]); }

return0;}voidquick_sort(int*a,intstart,intend){ inti=start,j=end; intkey=a[start];//在起始位置挖坑，等待被填 while(start<end) {while(start<end) { if(a[end]<=key) { a[start]=a[end];//把a[end]挖出来，填到a[start]坑里 start++;

break;}end--;}while(start<end){if(a[start]>key){a[end]=a[start]; end--; break;} start++;}}

intmid=start; a[mid]=key;

if(i<mid-1) quick_sort(a,i,mid-1); if(j>mid+1) quick_sort(a,mid+1,j); }算法实现算法分析：快速排序是一个递归过程;利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况

直接插入排序算法描述插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]≤L[j+1]时为止。#include<stdio.h>voiddirectinsert_sort(int*a,intn);

intmain(){ inta[5]={5,7,3,1,2}; directinsert_sort(a,5); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]); }}voiddirectinsert_sort(int*a,intn){ inti,j,temp;; for(i=1;i<n;i++) { temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) a[j+1]=a[j];//往后挪动

a[j+1]=temp; }}

算法实现选择排序在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环

到倒数第二个数和最后一个数比较为止。算法描述算法实例#include<stdio.h>voidselect_sort(int*a,intn);

intmain(){ intarr[5]={5,7,3,1,2}; select_sort(arr,5);

inti; for(i=0;i<5;i++) { printf("%d\n",arr[i]); }}

voidselect_sort(int*a,intn){ inti,j,min,temp; for(i=0;i<n-1;i++)//循环n-1趟 { min=i; for(j=i+1;j<n;j++)//从i+1开始比较 { if(a[min]>a[j]) min=j; }

if(min!=i) { temp=a[min]; a[min]=a[i]; a[i]=temp; } }}希尔排序希尔排序是插入排序的增强版。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

算法实例运用实例已知待排序的一组记录的初始排列为：21,25,49,25*,16,080123452108254925*16t12108254925*162108254925*16t22108254925*162108254925*16t30123452108254925*160123452108254925*16算法实例#include<stdio.h>

voidshell_sort(int*a,intn);

intmain(){ inta[5]={4,2,5,7,1}; shell_sort(a,5); inti; for(i=0;i<5;i++) { printf("%d\n",a[i]);

}}

voidshell_sort(int*a,intn){inti,j,d,temp;for(d=n/2;d>=1;d/=2)//增量改变一般是数组元素个数累除2{for(i=d;i<n;i++)//注意这里的i++不是i=i+d;temp=a[i];for(j=i-d;j>=0&&temp<a[j];j-=d){a[j+d]=a[j];}a[j+d]=temp;}}}算法分析开始时gap的值较大,子序列中的记录较少,排序速度较快随着排序进展,gap值逐渐变小,子序列中记录个数逐渐变多,由于前面大多数记录已基本有序,所以排序速度仍然很快Gap的取法有多种。shell提出取gap=n/2，gap=gap/2，直到gap=1。下面是几种常见的排序算法的封装封装的冒泡法：voidmybubbling_sort(int*a,intn,intsize,int(*cmp)(void*,void*)){inti,j;void*temp=malloc(size);if(temp==NULL){ printf("cannotmalloc\n"); return;}for(i=0;i<n-1;i++){ for(j=0;j<n-1-i;j++) { if(cmp((char*)a+j*size,(char*)a+(j+1)*size)>0) { memcpy(temp,(char*)a+j*size,size); memcpy((char*)a+j*size,(char*)a+(j+1)*size,size); memcpy((char*)a+(j+1)*size,temp,size); } } } free(temp);}下面是几种常见的排序算法的封装封装的选择排序法voidmyselect_sort(void*a,intnmeb,intsize,int(*cmp)(void*,void*)){ inti,j,min; void*temp=malloc(size); if(temp==NULL) { printf("cannotmalloc\n"); return;} for(i=0;i<nmeb-1;i++) { min=i; for(j=