nArray[nHigh--] = nArray[nLow];
}
}
nArray[nLow] = nBase;
return nLow;
}
void QuickSort(int nArray[], int nLow, int nHigh)
{
if (nLow < nHigh)
{
int nMid = AdjustArray(nArray, nLow, nHigh);
QuickSort(nArray, 0, nMid - 1);
QuickSort(nArray, nMid + 1, nHigh);
}
}
/**//*
--- 希尔排序 ---
是对直接插入排序算法的改进，又称缩小增量排序。
1、将数组进行分组，下标相差d的为一组；
2、对每组中全部元素进行排序；
3、然后再用一个较小的增量d, 重复1、2，直到d为1时，排序完成。
一般增量取值为上一次的一半，d = 1/2 d，第一次取值为数组长度的一半。
*/
void ShellSort(int nArray[], int nLength)
{
for (int nDifference = nLength / 2; nDifference > 0; nDifference = nDifference / 2)
{
for (int i = nDifference; i < nLength; ++i)
{
int temp = nArray[i];
int j = i;
for (; j > 0 && nArray[j - 1] > temp; --j)
{
nArray[j] = nArray[j - 1];
}
nArray[j] = temp;
}
}
}
/**//*
--- 归并排序 ---
是将两个已经排序的序列合并成一个有序序列。
1、待排序序列分为两个子序列;
2、每个子序列重复步骤1，直到每个子序列只有一个元素;
3、按大小顺序合并两个子序列;
4、重复步骤3，直到合并为一个整体有序序列，排序完成。
*/
void Merge(int nArray[], int nLow, int nHigh)
{
int nFirst = nLow;
int nMid = (nLow + nHigh) / 2;
int nSecond = nMid + 1;
int* p = (int*)malloc(sizeof(int) * (nHigh - nLow + 1));
int nIndex = 0;
while(nFirst <= nMid && nSecond <= nHigh)
{
if (nArray[nFirst] > nArray[nSecond])
{
p[nIndex] = nArray[nSecond++];
}
else
{
p[nIndex] = nArray[nFirst++];
}
++nIndex;
}
while (nFirst <= nMid)
{
p[nIndex++] = nArray[nFirst++];
}
while (nSecond <= nHigh)
{
p[nIndex++] = nArray[nSecond++];
}
for (int i = 0; i <= nIndex && nLow <= nHigh;)
{
nArray[nLow++] = p[i++];
}
free(p);
}
void MergeSort(int nArray[], int nLow, int nHigh)
{
if (nLow < nHigh)
{
int nMid = (nLow + nHigh) / 2;
MergeSort(nArray, nLow, nMid);
MergeSort(nArray, nMid+1, nHigh);
Merge(nArray, nLow, nHigh);
}
}
/**//*
--- 堆排序 ---
1、先将数组转换为完全二叉树；
2、调整二叉树形如大顶堆；
3、将根结点与最后一个叶子结点互换，即将最大元素放在数组的末尾，数组的长度减一；
4、再重复2、3，直到数组长度为1，排序完成。
*/
void AdjustHeap(int nArray[], int nLength, int nIndex)
{
int nLeft = nIndex * 2 + 1;
int nRight = nIndex * 2 + 2;
int nParent = nIndex;
while(nLeft < nLength && nRight < nLength)
{
int nBigIndex = (nArray[nLeft] > nArray[nRight] nLeft : nRight);
if (nArray[nParent] < nArray[nBigIndex])
{
int temp = nArray[nParent];
nArray[nParent] = nArray[nBigIndex];
nArray[nBigIndex] = temp;
nLeft = nBigIndex * 2 + 1;
nRight = nBigIndex * 2 + 2;
}
break;
}
}