C++-八种排序算法总结及实现

八种排序算法总结之C++版本五种简单排序算法一、冒泡排序【稳定的】voidBubbleSort(int*a,intCount)//实现从小到大的最终结果{inttemp;for(inti=1;iCount;i++)//外层每循环一次，将最小的一个移动到最前面for(intj=Count-1;j=i;j--)if(a[j]a[j-1]){temp=a[j];a[j]=a[j-1];a[j-1]=temp;}}现在注意，我们给出O方法的定义：若存在一常量K和起点n0，使当n=n0时，有f(n)=K*g(n),则f(n)=O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。二、交换排序【稳定的】voidExchangeSort(int*a,intCount){inttemp;for(inti=0;iCount-1;i++)for(intj=i+1;jCount;j++)if(a[j]a[i]){temp=a[j];a[j]=a[i];a[i]=temp;}}时间复杂度为O(n*n)。三、选择法【不稳定的】voidSelectSort(int*a,intCount){inttemp;//一个存储值intpos;//一个存储下标for(inti=0;iCount;i++){temp=a[i];pos=i;for(intj=i+1;jCount;j++)if(a[j]temp)//选择排序法就是用第一个元素与最小的元素交换{temp=a[j];pos=j;//下标的交换赋值，记录当前最小元素的下标位置}a[pos]=a[i];a[i]=temp;}}遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)=n所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。四、插入法【稳定的】voidInsertSort(int*a,intCount){inttemp;//一个存储值intpos;//一个存储下标for(inti=1;iCount;i++)//最多做n-1趟插入{temp=a[i];//当前要插入的元素pos=i-1;while(pos=0&&tempa[pos]){a[pos+1]=a[pos];//将前一个元素后移一位pos--;}a[pos+1]=temp;}}其复杂度仍为O(n*n)。最终，我个人认为，在简单排序算法中，直接插入排序是最好的。五、希尔排序法【不稳定的】/**希尔排序，n为数组的个数*/voidShellSort(intarr[],intn){inttemp,pos;intd=n;//增量初值do{d=d/3+1;for(inti=d;in;i++){temp=arr[i];pos=i-d;while(pos=0&&temparr[pos]){//实现增量为d的插入排序arr[pos+d]=arr[pos];pos-=d;}arr[pos+d]=temp;}}while(d1);}三种高级排序算法一、快速排序辅助空间复杂度为O（1）【不稳定的】voidQuickSort(int*a,intleft,intright){inti,j,middle,temp;i=left;j=right;middle=a[(left+right)/2];do{while(a[i]middle&&iright)//从左扫描大于中值的数i++;while(a[j]middle&&jleft)//从右扫描小于中值的数j--;if(i=j)//找到了一对值{temp=a[i];a[i]=a[j];a[j]=temp;i++;j--;}}while(ij);//如果两边的下标交错，就停止(完成一次)//当左半边有值（leftj）,递归左半边if(leftj)QuickSort(a,left,j);//当右半边有值（righti）,递归右半边if(iright)QuickSort(a,i,right);}这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)=n+n+n+...+n=k*n=log2(n)*n所以算法复杂度为O(log2(n)*n)其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟），但是糟糕的情况只会持续一个流程，到下一个流程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。二、归并排序（两种实现方法均要掌握）【稳定的】归并排序是一种极好的内部排序方法，即针对数据保存在磁盘上而不是高速内存中的问题。//以下程序参考数据结构课本P286页的模板,为使用指针链表实现的#includeiostreamusingnamespacestd;structnode{//链表的节点数据intvalue;node*next;};node*divide_from(node*head){node*position,*midpoint,*second_half;if((midpoint=head)==NULL)//ListisemptyreturnNULL;position=midpoint-next;while(position!=NULL)//Movepositiontwiceformidpoint'sonemove{position=position-next;if(position!=NULL){midpoint=midpoint-next;position=position-next;}}second_half=midpoint-next;midpoint-next=NULL;//在这里将原链拆断，分为两段returnsecond_half;}node*merge(node*first,node*second){node*last_sorted;//当前已经链接好的有序链中的最后一个节点nodecombined;//哑节点last_sorted=&combined;while(first!=NULL&&second!=NULL){if(first-valuesecond-value){last_sorted-next=first;last_sorted=first;first=first-next;}else{last_sorted-next=second;last_sorted=second;second=second-next;}}if(first==NULL)last_sorted-next=second;elselast_sorted-next=first;returncombined.next;//返回哑节点的后继指针，即为合并后的链表的头指针}//这里的参数必须是引用调用，需要这个指引去允许函数修改调用自变量voidMergeSort(node*&head){if(head!=NULL&&head-next!=NULL)//如果只有一个元素，则不需排序{node*second_half=divide_from(head);MergeSort(head);MergeSort(second_half);head=merge(head,second_half);}}intmain(){nodea,b,c,d;node*p1,*p2,*p3,*p4,*head;p1=&a;p2=&b;p3=&c;p4=&d;a.value=2;b.value=4;c.value=3;d.value=1;a.next=p2;b.next=p3;c.next=p4;d.next=NULL;//调用归并排序前的结果head=p1;while(head!=NULL){couthead-value;head=head-next;}coutendl;MergeSort(p1);//调用归并排序后的结果head=p1;while(head!=NULL){couthead-value;head=head-next;}coutendl;}//以下程序为使用数组实现的归并排序,辅助空间复杂度为O（n）#includeiostreamusingnamespacestd;voidMerge(intdata[],intleft,intmid,intright){intn1,n2,k,i,j;n1=mid-left+1;n2=right-mid;int*L=newint[n1];//两个指针指向两个动态数组的首地址int*R=newint[n2];for(i=0,k=left;in1;i++,k++)L[i]=data[k];for(i=0,k=mid+1;in2;i++,k++)R[i]=data[k];for(k=left,i=0,j=0;in1&&jn2;k++){if(L[i]R[j]){//取小者放前面data[k]=L[i];i++;}else{data[k]=R[j];j++;}}if(in1)//左边的数组尚未取尽for(j=i;jn1;j++,k++)data[k]=L[j];else//if(jn2)//右边的数组尚未取尽,这句话可要可不要for(i=j;in2;i++,k++)data[k]=R[i];delete[]L;//回收内存delete[]R;}/**left:数组的开始下标，一般为0；right：数组的结束下标，一般为（n-1）*/voidMergeSort(intdata[],intleft,intright){if(leftright){intmid=left+(right-left)/2;//mid=(right+left)/2，防止溢出MergeSort(data,left,mid);MergeSort(data,mid+1,right);Merge(data,left,mid,right);}}intmain(){intdata[]={9,8,7,2,5,6,3,55,1};//排序前的输出for(inti=0;i9;i++)coutdata[i];coutendl;MergeSort(data,0,8);//排序后的输出for(inti=0;i9;i++)coutdata[i];coutendl;}三、堆排序【不稳定的】/**向堆中插入current元素的函数*/voidinsert_heap(intdata[],constint¤t,intlow,inthigh){intlarge;//元素data[low]左右儿子中，大者的位置large=2*low+1;while(large=high){if(largehigh&&data[large]data[large+1])large++;if