排序总结归纳

 1 class BubbleSort {
 2 public:
 3     int* bubbleSort(int* A, int n) {
 4         for(int i=0;i<n;i++){
 5             for(int j=i;j<n;j++){
 6                 int tmp;
 7                 if(A[i]>A[j]){
 8                     tmp = A[i];
 9                     A[i]= A[j];
10                     A[j]= tmp;
11                 }
12             }
13         }
14         return A; 
15     }
16 };

 1 class MergeSort {
 2 public:
 3     
 4     int* mergeSort(int* A, int n) {
 5         int* tmp = new int[n];
 6         mergeSort1(A,0,n-1,tmp);
 7         delete []tmp;
 8         return A;
 9     }
10     void mergeSort1(int* A,const int first,const int last,int* tmp){
11         if(first < last){
12             int mid = (first + last) / 2;
13             mergeSort1(A,first,mid,tmp);
14             mergeSort1(A,mid+1,last,tmp);
15             merge(A,first,mid,last,tmp);
16         }
17     }
18     
19     void merge(int* A,const int first,const int mid,const int last,int* tmp){
20         int i=0,j=0,k=0;
21         for(i=first,j=mid+1;i<=mid && j<= last;){
22             if(A[i]<A[j]) 
23                 tmp[k++] = A[i++];
24             else
25                 tmp[k++] = A[j++];
26         }
27         while(i<=mid) tmp[k++] = A[i++];
28         while(j<=last) tmp[k++] = A[j++];
29         for(i=0;i<k;i++){
30             A[first+i] = tmp[i];
31         }
32         
33     }
34 };

 1 class QuickSort {
 2 public:
 3     int* quickSort(int* A, int n) {
 4         quickSort1(A,0,n-1);
 5         return A;
 6     }
 7     void quickSort1(int* A,const int first,const int last){
 8         if(first<last){
 9             int mid = Sort(A,first,last);
10             quickSort1(A,first,mid);
11             quickSort1(A,mid+1,last);
12         }
13     }
14     int Sort(int* A,const int first,const int last){
15         int i=first;
16         int j=last;
17         int key = A[first];
18         if(first < last){
19             while(i<j){
20                 while(i<j && key<=A[j])
21                     j--;
22                 if(i<j)
23                     A[i++] = A[j];
24                 while(i<j && key>=A[i])
25                     i++;
26                 if(i<j)
27                     A[j--] = A[i];
28             }
29             A[i] = key;
30         }
31         return i;
32     }
33 };