/*
轉(zhuǎn)自:
http://m.shnenglu.com/chenjt3533/archive/2013/03/25/198815.html
*/
#include "stdafx.h"
/*
--- 冒泡排序 ---
自下而上的兩兩比較，小泡排在大泡前，一趟冒出一個(gè)最小泡。
*/
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;
}
}
}
}
/*
--- 選擇排序 ---
自下而上的兩兩比較，記錄最小數(shù)的下標(biāo)，將最上面的數(shù)與最小數(shù)交換。
*/
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;
}
}
/*
--- 插入排序 ---
將數(shù)據(jù)插入到已排序的序列中，邊找合適的位置，邊移動(dòng)數(shù)據(jù)，找到合適位置插入數(shù)據(jù)。
*/
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;
}
}
/*
--- 快速排序 ---
是對冒泡排序的改進(jìn)。
1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù);
2．分區(qū)過程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊;
3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù).
分區(qū)過程可以形象的描述為“挖坑填數(shù)”：
1．將基準(zhǔn)數(shù)nBase挖出形成第一個(gè)坑nArray[nLow];
2．nHigh--由后向前找比nBase小的數(shù)，找到后挖出此數(shù)填前一個(gè)坑nArray[nLow]中;
3．nLow++由前向后找比nBase大的數(shù)，找到后也挖出此數(shù)填到前一個(gè)坑nArray[nHigh]中;
4．再重復(fù)執(zhí)行2，3二步，直到nLow==nHigh，將基準(zhǔn)數(shù)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);
}
}
/*
--- 希爾排序 ---
是對直接插入排序算法的改進(jìn)，又稱縮小增量排序。
1、將數(shù)組進(jìn)行分組，下標(biāo)相差d的為一組；
2、對每組中全部元素進(jìn)行排序；
3、然后再用一個(gè)較小的增量d, 重復(fù)1、2，直到d為1時(shí)，排序完成。
一般增量取值為上一次的一半，d = 1/2 d，第一次取值為數(shù)組長度的一半。
*/
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;
}
}
}
/*
--- 歸并排序 ---
是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)有序序列。
1、待排序序列分為兩個(gè)子序列;
2、每個(gè)子序列重復(fù)步驟1，直到每個(gè)子序列只有一個(gè)元素;
3、按大小順序合并兩個(gè)子序列;
4、重復(fù)步驟3，直到合并為一個(gè)整體有序序列，排序完成。
*/
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、先將數(shù)組轉(zhuǎn)換為完全二叉樹；
2、調(diào)整二叉樹形如大頂堆；
3、將根結(jié)點(diǎn)與最后一個(gè)葉子結(jié)點(diǎn)互換，即將最大元素放在數(shù)組的末尾，數(shù)組的長度減一；
4、再重復(fù)2、3，直到數(shù)組長度為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;
}