/*
转自:
http://www.cppblog.com/chenjt3533/archive/2013/03/25/198815.html
*/
#include "stdafx.h"
/*
--- 冒泡排序 ---
自下而上的两两比较，小泡排在大泡前，一趟冒出一个最小泡。
*/
void BubbleSort(int nArray[], int nLength)
{
int i = nLength - 1;
int j = 0;
int temp = 0;
for (i = nLength - 1; i > 0; --i)
{
for (j = i - 1; j >= 0; --j)
{
if (nArray[j] > nArray[j + 1])
{
temp = nArray[j + 1];
nArray[j + 1] = nArray[j];
nArray[j] = temp;
}
}
}
}
/*
--- 选择排序 ---
自下而上的两两比较，记录最小数的下标，将最上面的数与最小数交换。
*/
void SelectSort(int nArray[], int nLength)
{
int tempIndex = 0;
int tempValue = 0;
for (int i = 0; i < nLength; ++i)
{
tempIndex = i;
for (int j = i + 1; j < nLength; ++j)
{
if (nArray[tempIndex] > nArray[j])
{
tempIndex = j;
}
}
tempValue = nArray[i];
nArray[i] = nArray[tempIndex];
nArray[tempIndex] = tempValue;
}
}
/*
--- 插入排序 ---
将数据插入到已排序的序列中，边找合适的位置，边移动数据，找到合适位置插入数据。
*/
void InsertSort(int nArray[], int nLength)
{
for (int i = 1; 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．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边;
3．再对左右区间重复第二步，直到各区间只有一个数.
分区过程可以形象的描述为“挖坑填数”：
1．将基准数nBase挖出形成第一个坑nArray[nLow];
2．nHigh--由后向前找比nBase小的数，找到后挖出此数填前一个坑nArray[nLow]中;
3．nLow++由前向后找比nBase大的数，找到后也挖出此数填到前一个坑nArray[nHigh]中;
4．再重复执行2，3二步，直到nLow==nHigh，将基准数nBase填入nArray[nLow]中.
*/
int AdjustArray(int nArray[], int nLow, int nHigh)
{
int nBase = nArray[nLow];
while(nLow < nHigh)
{
while(nLow < nHigh && nBase <= nArray[nHigh])
--nHigh;
if (nLow < nHigh)
{
nArray[nLow++] = nArray[nHigh];
}
while(nLow < nHigh && nBase > nArray[nLow])
++nLow;
if (nLow < nHigh)
{
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;
}
}
void BuildHeap(int nArray[], int nLength)
{
for (int i = nLength / 2 - 1; i >= 0; --i)
{
AdjustHeap(nArray, nLength, i);
}
}
void HeapSort(int nArray[], int nLength)
{
BuildHeap(nArray, nLength);
while(nLength > 1)
{
int temp = nArray[0];
nArray[0] = nArray[nLength - 1];
nArray[nLength - 1] = temp;
AdjustHeap(nArray, --nLength, 0);
}
}
void Test_Sort()
{
int nArray[5] = {1,3,2,5,4};
BubbleSort(nArray, 5);
//SelectSort(nArray, 5);
//InsertSort(nArray, 5);
//QuickSort(nArray, 0, 4);
//ShellSort(nArray, 5);
//MergeSort(nArray, 0, 4);
//HeapSort(nArray, 5);
for (int n = 0; n < 5; ++n)
{
std::cout << nArray[n] << " ";
}
std::cout << std::endl;
}
int main()
{
Test_Sort();
system("pause");
return 0;
}