1 // ALLKindsOfSorts.cpp : 定义控制台应用程序的入口点。  2 //  3   4 #include "stdafx.h"  5 #include
     
        6 #include
      
         7 #include
       
          8   9 using namespace std; 10  11 ////所有的排序总结 12  13 //1、冒泡排序(O(n*n)) 14  void MaopaoSort(int *a,int len) 15  { 16      //这里要明白 17     for(int i=0;i
        
         a[j+1])//相邻元素比较 24             { 25                 //交换 26                 int temp=a[j]; 27                 a[j]=a[j+1]; 28                 a[j+1]=temp; 29                 IsChange=true;//如果一次扫描完之后都没发生任何的交换，则表明已经排好序了 30             } 31         } 32         if(!IsChange) 33         { 34             cout<<"提前结束排序"<
         
          a[i])//跟已排序好的数进行比较，找出合适的位置 48         {         49             int temp= a[i];//将需要插入的无序数保存起来，并将所有都大于该需要插入的无序数的数后移 50             int j=i-1; 51             while(j>=0&&a[j]>temp)//从后往前扫描（j>=0是边界条件），判断已排序的数是否大于需要插入的无序数 52             { 53                 a[j+1]=a[j];//如果不是合适的位置就往后移动，腾出位置出来 54                 j--; 55             } 56             a[j+1]=temp;//找到了合适的位置，执行插入 57         } 58     } 59  60  } 61  62 //3、归并排序O(nlog(n))
         
        
       
      
     

struct Node{int v;Node* next}Node* merge_sort(Node* p){    if(p==NULL||p->next==NULL){        return NULL;	    }    Node* head1=p;    Node* mid=getmid(p);    Node* head2=mid->next;    mid->next=NULL;    head1=merge_sort(head1);    head2=merge_sort(head2);    return merge(head1,head2)}Node* getmid(Node* p){    if(p==NULL||p->next==NULL){    return NULL;	    }    Node* fast=p;    Node* slow=p;    while(fast->next!=NULL){        fast=fast->next;        if(fast->next!=NULL){        fast=fast->next;        slow=slow->next;        }    }    return slow}Node* merge(Node* p1,Node* p2){    if(p1==NULL) return p2;    if(p2=NULL) return p1;    Node* head1=p1;    Node* head2=p2;    Node* newhead=NULL;    if(head1->val<=head2->val){        newhead=head1;        head1=head1->next;    }else{        newhead=head2;        head2=head2->next;    }    Node* ptemp=newhead;    while(head1&&head2){        if(head1->val<=head2->val){        ptemp->next=head1;        ptemp=head1;        head1=head1->next;        }else{        ptemp->next=head2;        ptemp->head2;        head2=head2->next;        }    }    ptemp->next=head1?head1:head2;    return newhead;}

　　

102 //4、桶排序O(n)103  //桶排序用到插入排序(O(n*n))104 void InsertSort(vector
     
      &a,const int len)105  {106 107     for(int i=1;i
      
       a[i])//跟已排序好的数进行比较，找出合适的位置111         {        112             int temp= a[i];//将需要插入的无序数保存起来，并将所有都大于该需要插入的无序数的数后移113             int j=i-1;114             while(j>=0&&a[j]>temp)//从后往前扫描（j>=0是边界条件），判断已排序的数是否大于需要插入的无序数115             {116                 a[j+1]=a[j];//如果不是合适的位置就往后移动，腾出位置出来117                 j--;118             }119             a[j+1]=temp;//找到了合适的位置，执行插入120         }121     }122 123  }124 125 //由于桶排序需要将数据分成n等份的范围，每个范围的个数不一样，因此每个桶里面装的数的个数不相同，126 //因此选用容器作为桶的数据结构127 void BucketSort(vector
       
         &result,int *Data,int len)128 {129     if(Data==NULL||len<=0)130         return ;131     //求原始数据的最大值与最小值132     int max_value=Data[0];133     int min_value=Data[0];134     for (int i=0;i
        
         max_value)137             max_value=Data[i];138         if(Data[i]
         

Bucket[10];144 //将数据分别装入相应的桶中145 for (int i=0;i