评论各种排序算法示例
/*! @Sort.cpp
********************************************************************************
文件实现功能 : 各种常见的排序算法
作者 : e4lich
版本 : 2.0
--------------------------------------------------------------------------------
备注 : 无
--------------------------------------------------------------------------------
include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define BUFFER_SIZE 10

/*! @class Sort
********************************************************************************
类名 : Sort
功能 : 实现各种常见的排序算法
参数 : 无
返回值 : 无
抛出异常 : 无
--------------------------------------------------------------------------------
典型用法 :
: Sort sort; //定义一个类对象
: Sort.Display(); //排序前显示内容
: Sort::QuickSort(); //调用快速排序方法
: Sort.Display(); //排序后内容显示
--------------------------------------------------------------------------------
*******************************************************************************/
class Sort
{
public:
Sort(int nSize = BUFFER_SIZE); //构造函数
virtual ~Sort(); //析构函数

void InitRandBuffer(); //用随机数填充数组
void BubbleSort(); //冒泡排序算法
void SelectSort(); //选择排序算法
void InsertSort(); //插入排序算法
void QuickSort(); //快速排序算法
void ShellSort(); //希尔排序算法
void Display(); //显示数组内容
private:
void _QuickSort(const int left, const int right);
int Partition(const int left, const int right);
int *m_pBuffer; //数组缓冲区地址
int m_nSize; //数组大小
};

//构造函数
Sort::Sort(int nSize) : m_nSize(nSize)
{
if(nSize <= 0)
{
m_nSize = BUFFER_SIZE;
}
m_pBuffer = new int[m_nSize];
}

//析构函数
Sort::~Sort()
{
if(m_pBuffer)
{
delete [] m_pBuffer;
m_pBuffer = NULL;
}
}

//用随机数填充数组
void Sort::InitRandBuffer()
{
srand((unsigned int)time(NULL));
for(int i = 0; i < m_nSize; i++)
{
m_pBuffer[i] = rand() % 100;
}
}

//数组内容显示
void Sort::Display()
{
printf("The content of buffer is: ");
for(int i = 0; i < m_nSize; i++)
printf("%d ", m_pBuffer[i]);

putchar('\n');
}

//冒泡排序
void Sort::BubbleSort()
{
for(int i = 0; i < m_nSize; i++)
{
for(int j = i; j < m_nSize; j++)
{
if(m_pBuffer[i] > m_pBuffer[j])
{
m_pBuffer[i] ^= m_pBuffer[j];
m_pBuffer[j] ^= m_pBuffer[i];
m_pBuffer[i] ^= m_pBuffer[j];
}
}
}
}

//选择排序
void Sort::SelectSort()
{
int nMinIndex(0);
for(int i = 0; i < m_nSize - 1; i++)
{
nMinIndex = i;
for(int j = i + 1; j < m_nSize; j++)
{
if(m_pBuffer[nMinIndex] > m_pBuffer[j])
{
nMinIndex = j;
}
}

if(i != nMinIndex)
{
m_pBuffer[i] ^= m_pBuffer[nMinIndex];
m_pBuffer[nMinIndex] ^= m_pBuffer[i];
m_pBuffer[i] ^= m_pBuffer[nMinIndex];
}
}
}

//插入排序
void Sort::InsertSort()
{
int Temp(0);
for(int i = 1; i < m_nSize; i++)
{
Temp = m_pBuffer[i];
for(int j = i; j > 0; j--)
{
if(m_pBuffer[j-1] > Temp)
{
m_pBuffer[j] = m_pBuffer[j-1];
}
else
{
break;
}
}

if(j != i)
{
m_pBuffer[j] = Temp;
}
}
}

//快速排序
void Sort::QuickSort()
{
_QuickSort(0, m_nSize - 1);
}

void Sort::_QuickSort(const int left, const int right)
{
if(left < right)
{
int i = Partition(left, right);
_QuickSort(left, i - 1);
_QuickSort(i + 1, right);
}
}

int Sort::Partition(const int left, const int right)
{
int prvotPos = left;
int prvot = m_pBuffer[align=left];

for(int i = left + 1; i <= right; i++)
{
if((m_pBuffer[i] < prvot) && (++prvotPos != i))
{
m_pBuffer[i] ^= m_pBuffer[prvotPos];
m_pBuffer[prvotPos] ^= m_pBuffer[i];
m_pBuffer[i] ^= m_pBuffer[prvotPos];
}
}

if(left != prvotPos)
{
m_pBuffer[align=left] ^= m_pBuffer[prvotPos];
m_pBuffer[prvotPos] ^= m_pBuffer[align=left];
m_pBuffer[align=left] ^= m_pBuffer[prvotPos];
}

return prvotPos;
}

//希尔排序
void Sort::ShellSort()
{
int gap = m_nSize, Temp;
while((gap /= 2) >= 1)
{
for(int i = 0; i < gap; i++)
{
for(int j = i + gap; j < m_nSize; j += gap)
{
Temp = m_pBuffer[j];

for(int k = j; k >= gap; k -= gap)
{
if(m_pBuffer[k - gap] > Temp)
m_pBuffer[k] = m_pBuffer[k - gap];
else
break;
}

if(k != j)
m_pBuffer[k] = Temp;
}
}
}
}

//主函数
int main(int argc, char* argv[])
{
int choice = -1;
Sort sort;

while(choice != 0)
{
sort.InitRandBuffer();

system("cls");
printf("This is a demo of sort algorithm\n");
printf("1. Bubble sort\n");
printf("2. Select sort\n");
printf("3. Insert sort\n");
printf("4. Quick sort\n");
printf("5. Shell sort\n");
printf("0. Exit\n");
printf("Please enter your choice: ");

flushall();
scanf("%d", &choice);

switch(choice)
{
case 1 :
printf("Before Bubble sort: \n");
sort.Display();
sort.BubbleSort();
printf("After Bubble sort: \n");
sort.Display();
system("pause");
break;
case 2 :
printf("Before Select sort: \n");
sort.Display();
sort.SelectSort();
printf("After Select sort: \n");
sort.Display();
system("pause");
break;
case 3 :
printf("Before Insert sort: \n");
sort.Display();
sort.InsertSort();
printf("After Insert sort: \n");
sort.Display();
system("pause");
break;
case 4 :
printf("Before Quick sort: \n");
sort.Display();
sort.QuickSort();
printf("After Quick sort: \n");
sort.Display();
system("pause");
break;
case 5 :
printf("Before Shell sort: \n");
sort.Display();
sort.ShellSort();
printf("After Shell sort: \n");
sort.Display();
system("pause");
break;
default:
break;
}
}

return 0;
}