编程基本算法(1)编程基本算法(2)编程基本算法(3)选择排序使用条件：大小可比的集合。算法思想：每次pass从待排序的数据元素中选择最小（或最大）的元素，将其放在已排序序列的末尾，直到穷尽所有待排序的数据元素。编程示例：intb[10]={77,1,65,13,??81,93,10,5,23,17}//简单选择排序voidSimpleSelect(intb[10]){inttemp;inti;for(i=0;i<9;i++){for(intj=i+1;j<9;j++){if(b[i]>b[j]){temp=b[i];b[i]=b[j];b[j]=temp;}}}cout<<"thesortis:";for(inti=0;i<10;i++){cout<=0;i--){HeapAdjuest(b,i,9);}//取出堆顶数据，从新堆开始排序for(i=9;i>0;i--){Sawp(&b[i],&b[0]);HeapAdjuest(b,0,i-1);}}//堆调整(bigtopheap)//min数据需要调整数组中的起始位置//maxdata需要调整数据中的结束位置voidHeapAdjuest(intb[10],intmin,intmax){if(max<=min)return;inttemp;temp=b[min];intj;//扩展其子节点循环for(j=2*min;j<=max;j*=2){//选择它的大孩子if(jb[j]){break;}//用小数替换大数b[min]=b[j];min=j;}b[min]=temp;}//交换函数voidSawp(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}性能分析：时间复杂度时间复杂度O(nlogn)合并算法也叫2-waymergealgorithm使用条件：可比较大小的集合。算法思想：假设初始序列包含n条记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两合并得到[n/2]个长度为2或1的（这里的长度为1，可能这里的序列长度是奇数，那么最后一个序列是单数，所以长度为1）；两两合并，重复，直到得到一个长度为n的有序序列。编程示例：intb[10]={77,1,65,13,??81,93,10,5,23,17}//归并排序voidMergeSort(intb[10],intd[10],intmin,intmax){//使用并存储中间子区域得到的序列intc[10]；voidMerge(intc[10],intd[10],intmin,intmid,intmax);if(min==max)d[min]=b[min];else{//等分为两个区域intmid=(min+max)/2;//合并排序这个区域MergeSort(b,c,min,mid);//合并排序这个区域MergeSort(b,c,mid+1,max);//合并两个区域Merge(c,d,min,mid,max);}}//将有序序列d[min-mid]和d[mid+1-max]合并为有序序列c[min-max]voidMerge(intc[10],intd[10],intmin,intmid,intmax){inti,j,k;for(i=j=min,k=mid+1;j<=mid&&k<=max;i++){if(c[j]>c[k]){d[i]=c[k];k++;}else{d[i]=c[j];j++;}}if(j<=mid){for(;j<=mid;j++,i++){d[i]=c[j];}}if(k<=max){for(;k<=max;k++,i++){d[i]=c[k];}}}性能分析：时间复杂度O(nlogn)总结这么多排序算法，什么时候用哪个算法？？由于不同的排序方法适用于不同的应用和需求，因此在选择合适的排序方法时应考虑以下因素：待排序的记录数n需要存储结构时间和辅助空间复杂度来保证其稳定性(1)如果n是小的（比如n<=50），可以使用直接插入排序或者简单选择排序。(2)如果序列初始状态基本有序，可以选择直接插入排序和冒泡排序。(3)如果n比较昂贵，可以采用时间复杂度为O(nlogn)的算法：快速排序、堆排序、归并排序。快速排序目前被认为是基于比较的内部排序中最好的方法。当排序键随机分布时，平均快速排序时间最短。不稳定的堆排序比快速排序需要更少的辅助空间，并且不会出现快速排序可能出现的最坏情况。但还是比较不稳定。归并排序比较稳定，但是一般不推荐使用归并排序，实用性很差，占用的辅助空间可能比较大。
