排序算法（C++实现）

  1 #include <vector>
  2 using std::vector;
  3 
  4 template<typename T>
  5 void swap(vector<T> &a, int i, int j)
  6 {
  7     T tmp = a[i];
  8     a[i] = a[j];
  9     a[j] = tmp;
 10 }
 11 
 12 //简单插入排序
 13 template<typename T>
 14 void insertionSort(vector<T> &a)
 15 {
 16     for(int p=1; p!=a.size(); ++p)
 17     {
 18         int tmp = a[p], j;
 19         for(j = p; j>0&&a[j-1]>tmp; --j)
 20             a[j] = a[j-1];
 21         a[j] = tmp;
 22     }
 23 }
 24 
 25 //堆排序
 26 //把将要进行排序的元素依次入堆，再逐个弹出，便得到排好序的元素序列。
 27 //堆的C++实现：http://www.cnblogs.com/pczhou/p/4648146.html
 28 
 29 //归并排序
 30 template<typename T>
 31 void mergeSort(vector<T> &a)
 32 {
 33     vector<T> tmpA(a.size());
 34     mergeSort(a, tmpA, 0, a.size()-1);
 35 }
 36 template<typename T>
 37 void mergeSort(vector<T> &a, vector<T> &tmpA, int left, int right)
 38 {
 39     if(left<right)
 40     {
 41         int mid = (left+right)/2;
 42         mergeSort(a, tmpA, left, mid);
 43         mergeSort(a, tmpA, mid+1, right);
 44         merge(a, tmpA, left, mid+1, right);
 45     }
 46 }
 47 template<typename T>
 48 void merge(vector<T> &a, vector<T> &tmpA, int leftPos, int rightPos, int rightEnd)
 49 {
 50     int leftEnd = rightPos-1, tmpPos = leftPos;
 51     int numElements = rightEnd-leftPos+1;
 52 
 53     while(leftPos<=leftEnd&&rightPos<=rightEnd)
 54     {
 55         if(a[leftPos]<a[rightPos])
 56             tmpA[tmpPos++] = a[leftPos++];
 57         else
 58             tmpA[tmpPos++] = a[rightPos++];
 59     }
 60     while(leftPos<=leftEnd)
 61         tmpA[tmpPos++] = a[leftPos++];
 62     while(rightPos<=rightEnd)
 63         tmpA[tmpPos++] = a[rightPos++];
 64     for(; numElements; --numElements, --rightEnd)
 65         a[rightEnd] = tmpA[rightEnd];
 66 }
 67 
 68 //快速排序
 69 //（采用三数中值分割法确定枢纽元）
 70 template<typename T>
 71 void quickSort(vector<T> &a)
 72 {
 73     quickSort(a, 0, a.size()-1);
 74 }
 75 template<typename T>
 76 const T& median3(vector<T> &a, int left, int right)
 77 {
 78     int mid = (left+right)/2;
 79     if(a[left]<a[mid]&&a[mid]<a[right]||a[right]<a[mid]&&a[mid]<a[left])
 80         swap(a, mid, right);
 81     else if(a[mid]<a[left]&&a[left]<a[right]||a[right]<a[left]&&a[left]<a[mid])
 82         swap(a, left, right);
 83     return a[right];
 84 }
 85 template<typename T>
 86 void quickSort(vector<T> &a, int left, int right)
 87 {
 88     if(left<right)
 89     {
 90         T pivot = median3(a, left, right);
 91         int i=left-1, j=left;
 92         for(; j<right; ++j)
 93         {
 94             if(a[j]<pivot)
 95             {
 96                 ++i;
 97                 swap(a, i, j);
 98             }
 99         }
100         swap(a, i+1, right);
101 
102         quickSort(a, left, i);
103         quickSort(a, i+2, right);
104     }
105 }
106 
107 //桶排序
108 //假设：所有输入数据均为非负，且不超过M
109 const int M = 100;
110 void bucketSort(vector<int> &a)
111 {
112     vector<int> count(M+1);
113     for(int i=0; i!=count.size(); ++i) count[i] = 0;
114     for(int i=0; i!=a.size(); ++i) ++count[a[i]];
115     int k = 0;
116     for(int i=0; i!=count.size(); ++i)
117         for(int j=0; j<count[i]; ++j)   a[k++] = i;
118 }

测试代码:

 1     vector<int> a1, a2, a3, a4;
 2     for(int i=0; i<10; ++i)
 3     {
 4         int tmp;
 5         cout<<"please input: ";
 6         cin>>tmp;
 7         a1.push_back(tmp);
 8         a2.push_back(tmp);
 9         a3.push_back(tmp);
10         a4.push_back(tmp);
11     }
12     insertionSort(a1);
13     mergeSort(a2);
14     quickSort(a3);
15     bucketSort(a4);
16     cout<<"insertion sort:"<<endl;
17     for(int i=0; i!=a1.size(); ++i)
18         cout<<" "<<a1[i];
19     cout<<endl;
20     cout<<"merge sort:"<<endl;
21     for(int i=0; i!=a2.size(); ++i)
22         cout<<" "<<a2[i];
23     cout<<endl;
24     cout<<"quick sort:"<<endl;
25     for(int i=0; i!=a3.size(); ++i)
26         cout<<" "<<a3[i];
27     cout<<endl;
28     cout<<"bucket sort:"<<endl;
29     for(int i=0; i!=a4.size(); ++i)
30         cout<<" "<<a4[i];
31     cout<<endl;

测试结果：