C++ Class 宣告
class Sort{
private:
void Merge(int *arr, int front, int mid, int end);
int Partition(int *arr, int front, int end);
public:
void BubblesSort(int *arr, int size);
void InsertSort(int *arr, int size);
void MergeSort(int *arr, int front, int end);
void QuickSort(int *arr, int front, int end);
};排序法實現
int Sort::Partition(int *arr, int front, int end){
int pivot = arr[end];
int i = front;
for(int j = front; j < end; j++){
if(arr[j] < pivot){
swap(arr[j], arr[i]);
i++;
}
}
swap(arr[i], arr[end]);
return i;
}
void Sort::QuickSort(int *arr, int front, int end){
if(front < end){
int pivot = Partition(arr, front, end);
QuickSort(arr, front, pivot - );
QuickSort(arr, pivot + , end);
}
}
void Sort::BubblesSort(int *arr, int size){
int len = size;
for(int i = ; i < len; i++){
for(int j = i + ; j < len; j++){
if(arr[j] < arr[i])
swap(arr[i], arr[j]);
}
}
}
void Sort::InsertSort(int *arr, int size)
{
int len = size;
int insert = ;
for(int i = ; i < len; i++){
insert = arr[i];
for(int j = i - ; j >= ; j--){
if(insert < arr[j])
arr[j + ] = arr[j];
else
break;
}
}
}
void Sort::Merge(int *arr, int front, int mid, int end){
int i, j, k;
int n1 = mid - front + ;
int n2 = end - mid;
int LeftSub[n1];
int RightSub[n2];
/* copy array */
for(i = ; i < n1; i++)
LeftSub[i] = arr[front + i];
for(i = ; i < n2; i++)
RightSub[i] = arr[mid + i + ];
i = ; j = ; k = front;
while(i < n1 && j < n2){
if(LeftSub[i] <= RightSub[j]){
arr[k] = LeftSub[i];
i++;
}else{
arr[k] = RightSub[j];
j++;
}
k++;
}
while(i < n1){
arr[k] = LeftSub[i];
i++; k++;
}
while(j < n2){
arr[k] = RightSub[j];
j++; k++;
}
}
void Sort::MergeSort(int *arr, int front, int end){
if(front < end){
int mid = (front + end) / ;
MergeSort(arr, front, mid);
MergeSort(arr, mid + , end);
Merge(arr, front, mid, end);
}
}
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}