////////////////////////////////////冒泡排åº
class BubbleSort {
public:
int* bubbleSort(int* A, int n) {
// write code here
int i,j;
for(i = n - 1; i >= 0; i--){
for(j = 0; j < i; j++)
if(A[j] > A[j + 1])
swap(A[j],A[j + 1]);
}
return A;
}
};
////////////////////////////////////选择排åº
class SelectionSort {
public:
int* selectionSort(int* A, int n) {
// write code here
int i,j,temp;
for(i = 0; i < n; i++){
temp = i;
for(j = i + 1; j < n; j++)
if(A[j] < A[temp])
temp = j;
swap(A[i],A[temp]);
}
return A;
}
};
////////////////////////////////////æ’入排åº
class InsertionSort {
public:
int* insertionSort(int* A, int n) {
// write code here
int i,j,temp;
for(i = 1; i < n; i++){
temp = A[i];
for(j = i; j > 0 && temp < A[j - 1]; j--)
A[j] = A[j - 1];
A[j] = temp;
}
return A;
}
};
////////////////////////////////////归并排åº
class MergeSort {
public:
int* mergeSort(int* A, int n) {
// write code here
if(n <= 0 || A == NULL)
return A;
Msort(A,0,n-1);
return A;
}
void Msort(int *A,int left,int right){
if(left == right)
return ;
else{
int mid = (left + right) / 2;
Msort(A,left,mid);
Msort(A,mid + 1,right);
Merge(A,left,mid,right);
}
}
void Merge(int *A,int left,int mid,int right){
int leftStart = left,leftEnd = mid,rightStart = mid + 1,rightEnd = right;
int i = 0;
int *tempA = new int[right - left + 1];
while(leftStart <= leftEnd && rightStart <= rightEnd){
if(A[leftStart] <= A[rightStart])
tempA[i++] = A[leftStart++];
else
tempA[i++] = A[rightStart++];
}
while(leftStart <= leftEnd)
tempA[i++] = A[leftStart++];
while(rightStart <= rightEnd)
tempA[i++] = A[rightStart++];
for(int j = left,i = 0; j <= right; i++) //注æ„把tempAä¸å…ƒç´ æ‹·è´åˆ°Aä¸ï¼Œä¸‹æ ‡ä»Žleft到right
A[j++] = tempA[i];
delete []tempA;
tempA = NULL; //释放空间åŽå°†æŒ‡é’ˆç½®ç©ºï¼Œé˜²æ¢äº§ç”Ÿé‡ŽæŒ‡é’ˆ
}
};
////////////////////////////////////快速排åº
class QuickSort {
public:
int* quickSort(int* A, int n) {
// write code here
if(A == NULL || n <= 0)
return A;
else
Q_sort(A,0,n - 1);
return A;
}
void Q_sort(int *A,int left,int right){
if(left >= right)
return;
int mid = (left + right) / 2;
int i,last = left;
swap(A[left],A[mid]);
for(i = left + 1; i <= right; i++){
if(A[i] < A[left])
swap(A[i],A[++last]);
}
swap(A[left],A[last]);
Q_sort(A,left,last - 1);
Q_sort(A,last + 1,right);
}
};
////////////////////////////////////å †æŽ’åº
class HeapSort {
public:
int* heapSort(int* A, int n) {
// write code here
int i;
for(i = n / 2 - 1; i >= 0; i--)
PercDown(A,i,n);
for(i = n - 1; i > 0; i--){
swap(A[0],A[i]);
PercDown(A,0,i);
}
return A;
}
void PercDown(int *A,int p,int n){
int parent,child,temp = A[p];
for(parent = p; parent * 2 + 1 < n; parent = child){
child = parent * 2 + 1;
if(child + 1 != n && A[child] < A[child + 1])
child++;
if(A[child] <= temp) //注æ„æ˜¯å»ºç«‹å¤§é¡¶å †
break;
else
A[parent] = A[child];
}
A[parent] = temp;
}
};
//////////////////////////////////// 希尔排åº
class ShellSort {
public:
int* shellSort(int* A, int n) {
// write code here
if(A == NULL || n <= 0)
return A;
int step,i,j,temp;
for(step = n / 2; step > 0; step /= 2){
for(i = step; i < n; i++){
temp = A[i];
for(j = i; j >= step && temp < A[j - step]; j -= step)
A[j] = A[j - step];
A[j] = temp;
}
}
return A;
}
};
////////////////////////////////////计数排åº
class CountingSort {
public:
int* countingSort(int* A, int n) {
// write code here
if(A == NULL || n <= 0)
return A;
int max = 0;
int min = A[0];
for(int i = 0; i < n; i++){ //求大值，代表桶的最大数目
if(A[i] > max)
max = A[i];
if(A[i] < min)
min = A[i];
}
int *tempA = new int[max + 1](); //new申请内å˜ç©ºé—´ï¼Œå¹¶åˆå§‹åŒ–为0
for(int i = 0; i < n; i++)
tempA[A[i]]++;
int index = 0;
for(int i =min,j; i <= max; i++){
for(j = 0; j < tempA[i]; j++)
A[index++] = i;
}
delete []tempA;
tempA = NULL;
return A;
}
};
////////////////////////////////////基数排åº
class RadixSort {
public:
int* radixSort(int* A, int n) {
// write code here
if(A== NULL || n <= 1)
return A;
vector