#include <iostream>
#include <assert.h>
using namespace std;
const int MAXN = 1020;
/**//**
* @brief 选择排序(不稳定)
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @return true 代表处理成功
*/
bool select_sort(int *nX, int nNum)
{
assert(nX != NULL && nNum >= 1);
int i, j, nMin;
for (i = 0; i < nNum - 1; i++)
{
nMin = i;
for (j = i+1; j < nNum; j++)
{
if (nX[j] < nX[nMin])
{
nMin = j;
}
}
if (nMin != i)
{
swap(nX[nMin], nX[i]);
}
}
return true;
}
/**//**
* @brief 插入排序(稳定)
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @return true 代表处理成功
*/
bool insert_sort(int *nX, int nNum)
{
assert(nX != NULL && nNum >= 1);
int i, j, nTmp;
for (i = 1; i < nNum; i++)
{
nTmp = nX[i];
for (j = i-1; j >= 0 && nTmp < nX[j]; j--)
{
nX[j+1] = nX[j];
}
nX[j+1] = nTmp;
}
return true;
}
/**//**
* @brief 冒泡排序(稳定)
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @return true 代表处理成功
*/
bool bubble_sort(int *nX, int nNum)
{
assert(nX != NULL && nNum >= 1);
int i, j;
for (i = nNum - 1; i >= 0; i--)
{
for (j = 0; j < i; j++)
{
if(nX[j] > nX[j+1])
swap(nX[j], nX[j+1]);
}
}
return true;
}
/**//**
* @brief 希尔排序(不稳定)
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @return true 代表处理成功
*/
bool shell_sort(int *nX, int nNum)
{
assert(nX != NULL && nNum >= 1);
int i, j, nH, nTmp;
for (nH = nNum/2; nH > 0; nH /= 2)
{
//n - nH 趟冒泡
for (i = nH; i < nNum; i++)
{
//一趟冒泡
nTmp = nX[i];
for (j = i-nH; j >= 0 && nTmp < nX[j]; j -= nH)
{
nX[j+nH] = nX[j];
}
nX[j+nH] = nTmp;
}
}
return true;
}
/**//**
* @brief 快速排序(不稳定)
* @param nX 需要排序的数值
* @param nLow 开始元素的下标
* @param nHigh 结束元素的下标
*/
void quick_sort(int *nX, int nLow, int nHigh)
{
assert(nX != NULL);
if (nLow >= nHigh)
{
return ;
}
int nTmp, i = nLow, j = nHigh;
nTmp = nX[nLow];
while (i < j)
{
while (i < j && nX[j] >= nTmp)
{
j--;
}
nX[i] = nX[j];
while (i < j && nX[i] <= nTmp)
{
i++;
}
nX[j] = nX[i];
}
nX[i] = nTmp;
quick_sort(nX, nLow, i-1);
quick_sort(nX, i+1, nHigh);
}
/**//**
* @brief 建最大堆
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @param nStart 从第几个元素开始
* @return true 代表处理成功
*/
void sift(int *nX, int nNum, int nStart)
{
assert(nX != NULL && nNum >= 1);
int nTmp, k, j;
nTmp = nX[nStart];
k = nStart;
j = 2*k + 1;
while (j < nNum)
{
//选择子节点较大的
if (j < nNum -1 && nX[j] < nX[j+1])
{
j++;
}
//向下调整
if (nTmp < nX[j])
{
nX[k] = nX[j];
k = j;
j = 2*k + 1;
}
else
{
break;
}
}
nX[k] = nTmp;
}
/**//**
* @brief 堆排序(不稳定)
* @param nX 需要排序的数值
* @param nNum 数值的长度
* @return true 代表处理成功
*/
bool heap_sort(int *nX, int nNum)
{
assert(nX != NULL && nNum >= 1);
int i, k;
for (i = nNum/2-1; i >= 0; i--)
{
sift(nX, nNum, i);
}
for (k = nNum-1; k >= 1; k--)
{
swap(nX[0], nX[k]);
sift(nX, k, 0);
}
return true;
}
/**//**
* @brief 将nX[]的[nLow, nMiddle]和[nMiddle+1, nHigh]合并，并保存到nB[]中
* @param nX 源数组
* @param nB 目的数组
* @param nLow 开始元素的下标
* @param nMiddle 中间下标
* @param nHigh 结束元素的下标
*/
void merge(int *nX, int *nB, int nLow, int nMiddle, int nHigh)
{
int i = nLow, j = nMiddle + 1, k = nLow;
while ((i <= nMiddle) && (j <= nHigh))
{
if (nX[i] <= nX[j])
{
nB[k++] = nX[i++];
}
else
{
nB[k++] = nX[j++];
}
}
if (i > nMiddle)
{
for (int q = j; q <= nHigh; q++)
{
nB[k++] = nX[q];
}
}
else
{
for (int q = i; q <= nMiddle; q++)
{
nB[k++] = nX[q];
}
}
}
/**//**
* @brief 将nB[]复制到nX[] (从nLow到nHigh)
* @param nX 目的数组
* @param nB 源数组
* @param nLow 开始元素的下标
* @param nHigh 结束元素的下标
*/
void copy(int *nX, int *nB, int nLow, int nHigh)
{
int i = 0;
for (i = nLow; i <= nHigh; i++)
{
nX[i] = nB[i];
}
}
/**//**
* @brief 合并排序(不稳定)
* @param nLow 开始元素的下标
* @param nHigh 结束元素的下标
*/
void merge_sort(int *nX, int nLow, int nHigh)
{
assert(nX != NULL);
if (nLow < nHigh)
{
int i = (nLow + nHigh)/2;
merge_sort(nX, nLow, i);
merge_sort(nX, i+1, nHigh);
int nB[MAXN];
merge(nX, nB, nLow, i, nHigh);
copy(nX, nB, nLow, nHigh);
}
}
posted on 2009-09-27 20:55
longshen 阅读(325)
评论(0) 编辑 收藏 引用 所属分类:
程序员