#include <iostream>
#include <stdio.h>
using namespace std;
#define LEN 8
class SortAlgo
{
public:
int *arr;
int size;
SortAlgo(int a[], int len)
{
this->arr = new int[len];
this->size = 0;
for (int i = 0; i < len; ++i)
{
arr[i] = a[i];
++size;
}
}
~SortAlgo() { delete arr; }
void QuickSort(int *arr, int i, int j);
void mergeSort(int *arr, int low, int high);
void merge(int *arr, int begin, int middle, int end);
int getSize();
void show();
void swap(int i, int j);
};
int SortAlgo::getSize()
{
return this->size;
}
void SortAlgo::show()
{
for (int i = 0; i < getSize(); ++i)
{
cout << arr[i] << " ";
}
}
void SortAlgo::swap(int i, int j)
{
arr[i] = arr[i] xor arr[j];
arr[j] = arr[i] xor arr[j];
arr[i] = arr[i] xor arr[j];
}
void SortAlgo::QuickSort(int *arr, int i, int j)
{
if (i >= j)
return;
//基准数
int base = arr[i];
int end = j;
while (i < j)
{
//scan from right to left
while (arr[j] > base && j < i)
--j;
if (j > i)
swap(i, j);
//scan from left to right
while (arr[i] < base && i < j)
++i;
if (j > i)
swap(i, j);
--j;
}
QuickSort(arr, 0, i);
QuickSort(arr, i + 1, end);
}
void SortAlgo::mergeSort(int *arr, int low, int high)
{
if (low < high)
{
int mid = (low + high) >> 1;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
void SortAlgo::merge(int *arr, int low, int mid, int high)
{
// cout << low << " " << mid << " " << high << endl;
//归病排序
int temp[high - low + 1] = {0};
//arr1 from low to mid
//arr2 from mid+1 to high
int index = 0;
int i = low;
int j = mid + 1;
while (i <= mid || j <= high)
{
if (i > mid)
{
temp[index++] = arr[j++];
}
if (j > high)
{
temp[index++] = arr[i++];
}
while (i <= mid && arr[i] <= arr[j])
{
temp[index++] = arr[i++];
}
while (j <= high && arr[j] <= arr[i])
{
temp[index++] = arr[j++];
}
}
index = 0;
for (int i = low; i <= high; ++i, index++)
{
arr[i] = temp[index];
}
}
int main()
{
register int a[LEN] = {20, 15, 14, 0, 5, 4, 15, 16};
SortAlgo Qs(a, LEN);
Qs.show();
cout << "sorting......" << endl;
//Qs.QuickSort(Qs.arr,0,LEN-1);
//Qs.show();
Qs.mergeSort(a, 0, LEN - 1);
Qs.show();
return 0;
}
查看29道真题和解析