1 class Sort {
  2 public:
  3     //  冒泡排序
  4     int* bubbleSort(int* A, int n) {
  5         // write code here
  6         int i,j;
  7         for(i = n - 1; i >= 0; i--){
  8             for(j = 0; j < i; j++)
  9                 if(A[j] > A[j + 1])
 10                     swap(A[j],A[j + 1]);
 11         }
 12         return A;
 13     }
 14 public:
 15     //  选择排序
 16     int* selectionSort(int* A, int n) {
 17         // write code here
 18         int i,j,temp;
 19         for(i = 0; i < n; i++){
 20             temp = i;
 21             for(j = i + 1; j < n; j++)
 22                 if(A[j] < A[temp])
 23                     temp = j;
 24             swap(A[i],A[temp]);
 25         }
 26         return A;
 27     }
 28 public:
 29     //  插入排序
 30     int* insertionSort(int* A, int n) {
 31         // write code here
 32         int i,j,temp;
 33         for(i = 1; i < n; i++){
 34             temp = A[i];
 35             for(j = i; j > 0 && temp < A[j - 1]; j--)
 36                 A[j] = A[j - 1];
 37             A[j] = temp;
 38         }
 39         return A;
 40     }
 41 public:
 42     //  归并排序
 43     int* mergeSort(int* A, int n) {
 44         // write code here
 45         if(n <= 0 || A == NULL)
 46             return A;
 47         Msort(A,0,n-1);
 48         return A;
 49     }
 50     void Msort(int *A,int left,int right){
 51         if(left == right)
 52             return ;
 53         else{
 54             int mid = (left + right) / 2;
 55             Msort(A,left,mid);
 56             Msort(A,mid + 1,right);
 57             Merge(A,left,mid,right);
 58         }
 59     }
 60     void Merge(int *A,int left,int mid,int right){
 61         int leftStart = left,leftEnd = mid,rightStart = mid + 1,rightEnd = right;
 62         int i = 0;
 63         int *tempA = new int[right - left + 1];
 64         while(leftStart <= leftEnd && rightStart <= rightEnd){
 65             if(A[leftStart] <= A[rightStart])
 66                 tempA[i++] = A[leftStart++];
 67             else
 68                 tempA[i++] = A[rightStart++];
 69         }
 70         while(leftStart <= leftEnd)
 71             tempA[i++] = A[leftStart++];
 72         while(rightStart <= rightEnd)
 73             tempA[i++] = A[rightStart++];
 74         for(int j = left,i = 0; j <= right; i++) //注意把tempA中元素拷贝到A中，下标从left到right
 75             A[j++] = tempA[i];
 76         delete []tempA;
 77         tempA = NULL; //释放空间后将指针置空，防止产生野指针     
 78     }
 79 public:
 80     //  快速排序
 81     int* quickSort(int* A, int n) {
 82         // write code here
 83         if(A == NULL || n <= 0)
 84             return A;
 85         else
 86             Q_sort(A,0,n - 1);
 87         return A;
 88     }
 89     void Q_sort(int *A,int left,int right){
 90         if(left >= right)
 91             return;
 92         int mid = (left + right) / 2;
 93         int i,last = left;
 94         swap(A[left],A[mid]);
 95         for(i = left + 1; i <= right; i++){
 96             if(A[i] < A[left])
 97                 swap(A[i],A[++last]);
 98         }
 99         swap(A[left],A[last]);
100         Q_sort(A,left,last - 1);
101         Q_sort(A,last + 1,right);
102     }
103 public:
104     //  堆排序
105     int* heapSort(int* A, int n) {
106         // write code here
107         int i;
108         for(i = n / 2 - 1; i >= 0; i--)
109             PercDown(A,i,n);
110         for(i = n - 1; i > 0; i--){
111             swap(A[0],A[i]);
112             PercDown(A,0,i);
113         }
114         return A;
115     }
116     void PercDown(int *A,int p,int n){
117         int parent,child,temp = A[p];
118         for(parent = p; parent * 2 + 1 < n; parent = child){
119             child = parent * 2 + 1;
120             if(child + 1 != n && A[child] < A[child + 1])
121                 child++;
122             if(A[child] < temp)  //注意是建立大顶堆
123                 break;
124             else
125                 A[parent] = A[child];
126         }
127         A[parent] = temp;    
128     }
129 public:
130     //  希尔排序
131     int* shellSort(int* A, int n) {
132         // write code here
133         if(A == NULL || n <= 0)
134             return A;
135         int step,i,j,temp;
136         for(step = n / 2; step > 0; step /= 2){
137             for(i = step; i < n; i++){
138                 temp = A[i];
139                 for(j = i; j >= step && temp < A[j - step]; j -= step)
140                     A[j] = A[j - step];
141                 A[j] = temp;
142             }
143         }
144         return A;
145     }
146 public:
147     //  计数排序
148     int* countingSort(int* A, int n) {
149         // write code here
150         if(A == NULL || n <= 0)
151             return A;
152         int max = 0;
153         int min = A[0];
154         for(int i = 0; i < n; i++){  //求大值，代表桶的最大数目
155             if(A[i] > max)
156                 max = A[i];
157             if(A[i] < min)
158                 min = A[i];
159         }
160         int *tempA = new int[max + 1]();  //new申请内存空间，并初始化为0
161         for(int i = 0; i < n; i++)
162             tempA[A[i]]++;
163         int index = 0;
164         for(int i =min,j; i <= max; i++){
165             for(j = 0; j < tempA[i]; j++)
166                 A[index++] = i;
167         }
168         delete []tempA;
169         tempA = NULL;
170         return A;        
171     }
172 public:
173     //  基数排序
174     int* radixSort(int* A, int n) {
175         // write code here
176         if(A== NULL || n <= 1)
177             return A;
178         vector<vector<int>> res(10); //创建10个桶
179         int max = 0;
180         for(int i = 0; i < n; i++)
181             if(A[i] > max)
182                 max = A[i];
183         int count = 0;
184         while(max){
185             count++;
186             max /= 10;
187         }
188         
189         for(int i = 0; i < count; i++){
190             for(int j = 0; j < n; j++){
191                 int num = A[j] % (int)pow(10,i + 1) / (int)pow(10,i);  //num代表个、十、百、千位上的数字
192                 res[num].push_back(A[j]);
193             }
194             int index = 0;
195             for(auto iter1 = res.begin(); iter1 != res.end(); iter1++){
196                 for(auto iter2 = iter1->begin(); iter2 != iter1->end(); iter2++)
197                     A[index++] = *iter2;
198             }
199             for(int i = 0; i < 10; i++)
200                 res[i].clear();
201         }
202         return A;
203     }
204 };