#include "stdafx.h"
#include
using namespace std;
/*************
*排序算法实现
*************/
template
class CSort
{
private:
// the following three functions are for HeapSort():
int LeftChild(const int i);
void PercDown(T x[], int i, const int n);
void Swap(T *l, T *r);
// the following two functions are for MergeSort():
void MSort(T x[], T tmp[], int left, int right);
void Merge(T x[], T tmp[], int lpos, int rpos, int rightend);
// for QuickSort():
T Median3(T x[], const int left, const int right);
public:
void SelectSort(T x[],const int n);
void InsertSort(T x[], const int n);
void ShellSort(T x[], const int n);
void BubbleSort(T x[],const int n);
void HeapSort(T x[], const int n);
void MergeSort(T x[], int n);
void QuickSort(T x[], int left, int right);
};
/*
(1)选择排序
步骤: a.找出最小元素的位置
b.将这个最小元素移到未排序表的起始位置
*/
template
void CSort::SelectSort (T x[],const int n)
{
int i,j,k;
int temp;
for(i=0;i {
for(k=i,j=i+1;j if(x[j] k=j; //k记录目前找到的最小关键字所在的位置
if(k!=i) //交换x[i]和x[k]
{
temp=x[i];
x[i]=x[k];
x[k]=temp;
}
}
}
template
inline void CSort::InsertSort(T x[], const int n)
{
int i;
int j;
T tmp;
for (i = 0; i < n; ++i)
{
tmp = x[i]; // copy it first
for (j = i; j > 0; --j) // unsorted region; (0 ~ (i - 1)) is sorted
if (x[j - 1] > tmp)
x[j] = x[j - 1];// move back elements to empty a right position
else
break; // we got it! x[j] is the right position
x[j] = tmp; // place it to the right position
}
}
template
inline void CSort::ShellSort(T x[], const int n)
{
int i;
int j;
int nIncrement;
T tmp;
for (nIncrement = n / 2; nIncrement > 0; nIncrement /= 2)
{
for (i = nIncrement; i < n; ++i)
{
tmp = x[i];
for (j = i; j >= nIncrement; j -= nIncrement)
{
if (tmp < x[j - nIncrement])
x[j] = x[j - nIncrement];
else
break;
}
x[j] = tmp;
}
}
}
template
void CSort::BubbleSort (T x[],const int n)
{
int i,j;
T tmp;
for(i=0;i for(j=n-1;j>i;j--)
if(x[j] {
tmp=x[j];
x[j]=x[j-1];
x[j-1]=tmp;
}
}
template
inline int CSort::LeftChild(const int i)
{
return (2 * i + 1);
}
template
inline void CSort::PercDown(T x[], int i, const int n)
{
int nChild;
T tmp;
for (tmp = x[i]; LeftChild(i) < n; i = nChild)
{
nChild = LeftChild(i);
if ((nChild != n - 1) && (x[nChild + 1] > x[nChild]))
++nChild;
if (tmp < x[nChild])
x[i] = x[nChild];
else
break;
}
x[i] = tmp;
}
template
inline void CSort::Swap(T *l, T *r)
{
T tmp = *l;
*l = *r;
*r = tmp;
}
template
inline void CSort::HeapSort(T x[], const int n)
{
int i;
for (i = n / 2; i >= 0; --i) // build heap
PercDown(x, i, n);
for (i = n - 1; i > 0; --i)
{
Swap(&x[0], &x[i]); // delete max
PercDown(x, 0, i);
}
}
template
inline void CSort::Merge(T x[], T tmp[], int lpos, int rpos, int rightend)
{
int i;
int leftend;
int numelements;
int tmppos;
leftend = rpos - 1;
tmppos = lpos;
numelements = rightend - lpos + 1;
// main loop
while ((lpos <= leftend) && (rpos <= rightend))
{
if (x[lpos] <= x[rpos])
tmp[tmppos++] = x[lpos++];
else
tmp[tmppos++] = x[rpos++];
}
while (lpos <= leftend) // copy rest of first half
tmp[tmppos++] = x[lpos++];
while (rpos <= rightend) // copy rest of second half
tmp[tmppos++] = x[rpos++];
// copy tmp back
for (i = 0; i < numelements; ++i, --rightend)
x[rightend] = tmp[rightend];
}
template
inline void CSort::MSort(T x[], T tmp[], int left, int right)
{
int center;
if (left < right)
{ center = (left + right) / 2;
MSort(x, tmp, left, center);
MSort(x, tmp, center + 1, right);
Merge(x, tmp, left, center + 1, right);
}
}
template
inline void CSort::MergeSort(T x[], int n)
{
T *tmp;
tmp = new (T[n * sizeof(T)]);
if (NULL != tmp)
{
MSort(x, tmp, 0, n - 1);
delete tmp;
}
}
template
inline T CSort::Median3(T x[], const int left, const int right)
{
int center = (left + right) / 2;
if (x[left] > x[center])
Swap(&x[left], &x[center]);
if (x[left] > x[right])
Swap(&x[left], &x[right]);
if (x[center] > x[right])
Swap(&x[center], &x[right]);
// invariant: x[left] <= x[center] <= x[right]
Swap(&x[center], &x[right - 1]); // hide pivot
return x[right - 1]; // return pivot
}
template
inline void CSort::QuickSort(T x[], int left, int right)
{
int i;
int j;
int cutoff = 3;
T pivot;
if (left + cutoff <= right)
{
pivot = Median3(x, left, right);
i = left;
j = right - 1;
for (;;)
{
while (x[++i] < pivot) {}
while (x[--j] > pivot) {}
if (i < j)
Swap(&x[i], &x[j]);
else
break;
}
Swap(&x[i], &x[right - 1]); // restore pivot
QuickSort(x, left, i - 1);
QuickSort(x, i + 1, right);
}
else // do an insertion sort on the subarray
InsertSort(x + left, right - left + 1);
}
template
void print(T x[],const int n)
{
for(int i=0;i cout< cout<}
int main()
{
int x[] = {2, 9, 1, 6, 4, 8, 10, 7, 3, 5};
CSort sort;
//sort.SelectSort(x,10);
//sort.InsertSort (x,10);
//sort.ShellSort (x,10);
//sort.BubbleSort (x,10);
//sort.QuickSort (x,0,9);
//sort.MergeSort (x,10);
sort.HeapSort (x,10);
print(x,10);
return 0;
}
