搜索
排序计算机程序设计八排序将一组数据按由小到大或者由大到小的顺序进行排列。选择排序(SelectionSort)冒泡排序(BubbleSort)插入排序(InsertionSort)希尔排序(ShellSort)快速排序(QuickSort)堆排序(HeapSort)归并排序(MergeSort)基数排序(xxxSort)选择排序将29188756327按由小到大排序29188756327291887563273298756182718298756327329875618273298756182731887562927第1趟31887562927第2趟31856872927318298756273182787562931827875629第3趟318275687293182729875631827298756第4趟31827295687第5趟选择排序的基本思想是：对待排序的n个数据进行n-1遍的处理，第1遍处理是将a[2..n]中最小者与a[1]交换位置，第2遍处理是将a[3..n]中最小者与a[2]交换位置，......，第i遍处理是将a[i+1..n]中最小者与a[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。inta[1001];inti,j,temp;…输入n个数字到a中…//选择排序for(i=1;i=n-1;i++)//以i号数为基准for(j=i+1;j=n;j++)//与i后每个数比较if(a[i]a[j])//发现反序则交换{temp=a[i];a[i]=a[j];a[j]=temp;}…输出排序结果…选择排序特点分析时间复杂度：稳定性：时间复杂度简单的说就是程序循环执行的总的次数。排序算法的稳定性是指值相同的数字在排序前后其相对位置是否要发生改变，若要改变就是不稳定，否则就是稳定的。总共比较n(n-1)/2次时间复杂度为O(n2)不稳定练习：排序（isort.cpp）输入n（n=80000）个整数，排序后，按由小到大的顺序输出。输入格式(输入文件indata.in)：第一行一个整数n第二行n个由空格间隔的整数输出格式(输出文件outdata.out)：只有一行：n个由小到大排列的整数，用空格间隔样例输入：81672389912035-2样例输出：-27816233599120文件输入输出打开输入文件：freopen(d:/indata.txt,r,stdin);作用是：打开d盘已存在的indata.txt文件，从该文件中读入数据。打开输出文件：freopen(d:/outdata.txt,w,stdout);作用是：在d盘新建立一个名为outdata.txt的文件，将数据写入该文件fclose(stdin);//关闭输入文件fclose(stdout);//关闭输出文件freopen(输入文件名,r,stdin);freopen(输出文件名,w,stdout);#includeiostreamusingnamespacestd;intmain(){freopen(d:/testdata.in,r,stdin);freopen(d:/testdata.out,w,stdout);inta[500001],n,i,j,temp;scanf(%d,&n)for(i=1;i=n;i++)scanf(%d,&a[i]);for(i=1;i=n-1;i++)for(j=i+1;j=n;j++)if(a[i]a[j]){temp=a[i];a[i]=a[j];a[j]=temp;}for(i=1;i=n;i++)printf(%d,&a[i]);fclose(stdin);fclose(stdout);return0;}冒泡排序将29188756327按由小到大排序2918875632729188756327182987563271829875632718295687327182956873271829563872718295638727182956327871829563278718295632787第1趟18293562787182935627871829327568718293275687第2趟1829327568718329275687183292756871832729568718327295687第3趟18327295687318272956873182729568731827295687第4趟31827295687第5趟冒泡排序基本思想是:对待排序的数字进行两两比较,如发现两个数字是反序的,则进行交换,直到无反序的记录为止。//总共比较n-1趟for(i=1;i=n-1;i++)//j为要比较两个的相邻两数的第1个数的下标for(j=1;j=n-i;j++)//若发现相邻两数反序，则交换if(a[j]a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}冒泡排序将29188756327按由小到大排序冒泡排序特点分析时间复杂度：稳定性：总共比较n(n-1)/2次时间复杂度为O(n2)稳定①(29)(188756327)②(1829)(8756327)③(182987)(56327)④(18295687)(327)⑤(318295687)(27)⑥(31827295687)插入排序将29188756327按由小到大排序算法实现在数组中增加元素a[0]作为临时空间,把待插入的数放到里面。第i趟排序，即a[i]的插入过程为：①保存a[0]=a[i]②j=i-1③如果a[j]=a[0]（即待排序的a[i]），则a[j+1]=a[0]，完成插入；否则，将a[j]后移一个位置：A[j+1]=A[j]；继续执行③程序代码for(i=2;i=n;i++){a[0]=a[i];j=i-1;while(a[j]a[0]){a[j+1]=a[j];j--;}a[j+1]=a[0];}（1）稳定性：稳定（2）时间复杂度：O(n2)①初始数据正序，总比较次数：n-1②初始数据逆序，总比较次数：(n2+n-1)/2=O(n2)③初始数据无序，第i趟平均比较次数(i+1)/2，总次数为：(n2+3n)/4=O(n2)④可见，原始数据越趋向正序，比较次数和移动次数越少。)(22222nOnnini课堂练习：学生成绩(student.cpp)某年级有n(n=5000)个学生，学号1到n，现给出这n个学生的语文和数学成绩，请按数学成绩的由高到低对这n个学生进行排序。数学成绩相同的学生，按语文成绩由高到低排序。输入格式(输入文件student.in)：第一行，一个整数n，表示n个学生第二行，n个空格间隔的整数，表示学号1到n的学生的数学成绩第三行，n个空格间隔的整数，表示学号1到n的学生的语文成绩输出格式(输出文件student.out)：排序后输出n行，每行代表一个学生。每行两个数字，分为该生的数学和语文成绩。样例输入：6678891889988809269708577样例输出998591698892887788706780intmain(){freopen(d:/student10.in,r,stdin);freopen(d:/student10.out,w,stdout);intyu[5001],shu[5001],n,i,j,temp;scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&shu[i]);for(i=1;i=n;i++)scanf(%d,&yu[i]);for(i=1;i=n-1;i++)for(j=1;j=n-i;j++)if((shu[j]shu[j+1])||((shu[j]==shu[j+1])&&(yu[j]yu[j+1]))){temp=shu[j];shu[j]=shu[j+1];shu[j+1]=temp;temp=yu[j];yu[j]=yu[j+1];yu[j+1]=temp;}for(i=1;i=n;i++)printf(%d%d\n,shu[i],yu[i]);fclose(stdin);fclose(stdout);return0;}程序代码for(i=2;i=n;i++){shu[0]=shu[i];yu[0]=yu[j];j=i-1;while((shu[j]shu[0])||(shu[j]==shu[0])&&(yu[j]yu[0])){shu[j+1]=shu[j];yu[j+1]=yu[j];j--;}shu[j+1]=shu[0];yu[j+1]=yu[0];}1839329快速排序将299618563563977按由小到大排序思想：每次找一个数位基准，把小于等于它的放到这个数的左边，把大于等于它的放到它的右边29961856377563939392996xa12345678下标9656356y18567756395656185612345xy293183918963929563929voidqsort(intl,intr){intx,y,mid,temp;x=l;y=r;mid=a[l];do{while(a[x]mid)x++;while(a[y]mid)y--;if(x=y){temp=a[x];a[x]=a[y];a[y]=temp;x++;y--;}while(x=y);if(ly)qsort(l,y);if(xr)qsort(x,r);}每排完一趟，小于等于基准值的，在y的左侧。大于等于基准值的在x的右侧。8,12,56,99,18#includeiostreamusingnamespacestd;inta[30001];inti,n;voidqsort(intl,intr){intx,y,mid,temp;x=l;y=r;mid=a[l];do{while(a[x]mid)x++;while(a[y]mid)y--;if(x=y){temp=a[x];a[x]=a[y];a[y]=temp;x++;y--;}}while(x=y);if(ly)qsort(l,y);if(xr)qsort(x,r);}intmain(){scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&a[i]);qsort(1,n);for(i=1;i=n;i++)printf(%d,a[i]);return0;}稳定性：不稳定平均时间复杂度：O(nlog2n)为什么不能是=和=?while(a[x]=mid)doinc(x);while(a[y]=mid)dodec(y);反例：93333mid