文档介绍：内部排序算法:●冒泡排序●插入排序●二路插入排序●希尔排序●快速排序●选择排序●归并排序●堆排序算法的#include<iostream>usingnamespacestd;//交换两个数的值voidswap(int&a,int&b){inttmp;tmp=a;a=b;b=tmp;}//屏幕输出数组voiddisplay(intarray[],intlen){cout<<"theresultis:"<<endl;for(inti=0;i<len;i++){cout<<array[i]<<"";}cout<<endl;}●冒泡排序算法思想:将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。●时间复杂度o(n^2)●空间复杂度o(1)●比较次数n(n+1)/2voidbubble_sort(intarray[],intlen){for(inti=len-1;i>=0;i--){for(intj=0;j<i;j++)if(array[j]>array[j+1])swap(array[j],array[j+1]);}}●直接插入排序算法思想:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。●时间复杂度o(n^2)●空间复杂度o(1)●比较次数n(n+1)/2voidinsert_sort(intarray[],intlen){inttmp,i,j;for(i=1;i<len;i++){if(array[i]<array[i-1]){tmp=array[i];array[i]=array[i-1];//插入到相应位置for(j=i-2;j>=0;j--){//往后移if(array[j]>tmp)array[j+1]=array[j];else{array[j+1]=tmp;break;}}if(j==-1)array[j+1]=tmp;}}}●2-路插入排序算法思想:增加一个辅助空间d,把r[1]赋值给d[1],并将d[1]看成是排好序后处于中间位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。●时间复杂度o(n^2)●空间复杂度o(1)●比较次数n(n+1)/2voidbi_insert_sort(intarray[],intlen){int*arr_d=(int*)malloc(sizeof(int)*len);arr_d[0]=array[0];inthead=0,tail=0;for(inti=1;i<len;i++){if(array[i]>arr_d[0]){intj;for(j=tail;j>0;j--){if(array[i]<arr_d[j])arr_d[j+1]=arr_d[j];elsebreak;}arr_d[j+1]=array[i];tail+=1;}else{if(head==0){arr_d[len-1]=array[i];head=len-1;}else{intj;for(j=head;j<=len-1;j++){if(array[i]>arr_d[j])arr_d[j-1]=arr_d[j];elsebreak;}arr_d[j-1]=array[i];head-=1;}}}for(inti=0;i<len;i++){intpos=(i+head);if(pos>=len)pos-=len;array[i]=arr_d[pos];}free(arr_d);}●希尔排序算法思想:先将整个待排序记录分割成若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序●时间复杂度o(n^2)●空间复杂度o(1)●比较次数?voidshell_insert(intarray[],intd,intlen){inttmp,j;for(inti=d;i<len;i++){if(array[i]<array[i-d]){tmp=array[i];j=i-d;do{array[j+d]=array[j];j=j-d;}while(j>=0&&tmp<array[j]);array[j+d]=tmp;}}}voidshell_sort(intarray[],intlen){intinc=len;do{inc=inc/2;shell_insert(array,inc,len);}while(