整理以前的學(xué)習(xí)筆記，有以下的代碼片斷：
// 內(nèi)排序常用算法
// 在Microsoft Visual C++ .NET下編譯通過
#include <iostream>
#include <tchar.h>
using namespace System;
//namespace sortProgram
//{
const int MAXSIZE = 20; // 假設(shè)的順序表最大長(zhǎng)度
typedef int KeyType; // 關(guān)鍵字類型 設(shè)定關(guān)鍵字為整型
class RcdType
{
public:
KeyType key; // 關(guān)鍵字項(xiàng)
// 其他項(xiàng)
};
// 順序表類型
class SqList
{
public:
RcdType r[MAXSIZE+1]; // r[0]閑置或作為判別標(biāo)志的"哨兵"單元
int length; // 順序表長(zhǎng)度
};
//}
// *************************
// 直接插入排序
// *************************
void InsertSort(SqList &L)
{
for (int i=2; i<=L.length; i++)
{
if (L.r[i].key < L.r[i-1].key) // 將L.r[i]插入有序表
{
L.r[0] = L.r[i]; //設(shè)哨兵
// 記錄后移
L.r[i] = L.r[i-1];
for (int j=i-2; L.r[0].key < L.r[j].key; j--)
{
L.r[j+1] = L.r[j];
}
// 插入到正確位置
L.r[j+1] = L.r[0];
}
int x = L.r[i].key;
}
}
// *************************
// 折半插入排序
// *************************
void BInsertSort(SqList &L)
{
for (int i=2; i<=L.length; i++)
{
L.r[0] = L.r[i]; //將L.r[i]暫存到r[0]
int low = 1;
int high = i-1;
// 在r[low...high]中折半查找有序插入位置
while (low <= high)
{
int m = (low+high)/2; // 折半
if (L.r[0].key < L.r[m].key) // 插入點(diǎn)在低半?yún)^(qū)
high = m-1;
else //插入點(diǎn)在高半?yún)^(qū)
low = m+1;
}
// 記錄后移
for (int j=i-1; j>=low; j--)
L.r[j+1] = L.r[j];
// 插入
L.r[high+1] = L.r[0];
}
}
// *************************
// 希爾排序
// *************************
// 對(duì)順序表L作一趟增量為dk的希爾排序
void ShellInsert(SqList &L, int dk)
{
for (int i=dk+1; i<=L.length; i++)
{
if (L.r[i].key < L.r[i-dk].key) // 將L.r[i]插入有序子表
{
L.r[0] = L.r[i];
L.r[i] = L.r[i-dk];
for (int j=i-2*dk; j>0 && L.r[0].key<L.r[j].key; j-=dk)
L.r[j+dk] = L.r[j]; //記錄后移
L.r[j+dk] = L.r[0]; // 插入到正確位置
}
}
}
// 按增量序列dlta[0...t-1]對(duì)順序表L作希爾排序
void ShellSort(SqList &L, int dlta[], int t)
{
for (int k=0; k<t; k++)
{
ShellInsert(L, dlta[k]);
}
}
// *************************
// 起泡排序
// *************************
void BubbleSort(SqList &L)
{
for (int i=L.length, bool change = true; i>1 && change; --i)
{
change = false;
for (int j=1; j<i; j++)
{
if (L.r[j].key > L.r[j+1].key)
{
L.r[0] = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = L.r[0];
change = true;
}
}
}
}
// *************************
// 起泡算法的改進(jìn)
// *************************
// 記下最后進(jìn)行交換的記錄的位置
// 在此位置之后的記錄已是有序, 不必進(jìn)行比較
void BubbleSort_(SqList &L)
{
int i = L.length;
while (i > 1) // i>1 表明上一趟曾進(jìn)行過記錄的交換
{
int lastExchangeIndex = 1;
for (int j=1; j<i; j++)
{
if (L.r[j+1].key < L.r[j].key)
{
// 互換記錄
L.r[0] = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = L.r[0];
lastExchangeIndex = j; // 記下進(jìn)行交換的記錄的位置
}
}
i = lastExchangeIndex; // 一趟起泡后仍處于無(wú)序狀態(tài)的最后一個(gè)記錄的位置
}
}
// *************************
// 快速排序
// *************************
// 對(duì)記錄子序列 R[low...high] 進(jìn)行一趟快速排序, 并返回樞軸記錄所在位置
// 使得在它之前的記錄的關(guān)鍵字均不大于它的關(guān)鍵字,
// 而在它之前的記錄的關(guān)鍵字均不小于它的關(guān)鍵字
int Partition(RcdType R[], int low, int high)
{
R[0] = R[low]; // 將樞軸記錄移至數(shù)組的閑置分量
KeyType pivotkey = R[low].key; // 樞軸記錄關(guān)鍵字
// 從表的兩端交替地向中間掃描
while (low<high)
{
while (low<high && R[high].key >=pivotkey)
high--;
if (low != high) R[low++] = R[high]; // 將比樞軸記錄大的記錄移到高端
while (low<high && R[low].key<=pivotkey)
low++;
if (low < high) R[high--] = R[low]; // 將比樞軸記錄大的記錄移到高端
}
R[low] = R[0]; // 樞軸記錄移到正確位置
return low; // 返回樞軸位置
}
// 對(duì)記錄序列 R[s...t] 進(jìn)行快速排序
void QSort(RcdType R[], int s, int t)
{
if (s < t)
{
int pivotloc = Partition(R, s, t); // 對(duì) R[s...t] 進(jìn)行一趟快排, 并返回樞軸位置
QSort(R, s, pivotloc-1); // 對(duì)低子序列遞歸進(jìn)行排序
QSort(R, pivotloc+1, t); // 對(duì)高子序列遞歸進(jìn)行排序
}
}
// 對(duì)順序表 L 進(jìn)行快速排序
void QuickSort(SqList &L)
{
QSort(L.r, 1, L.length);
}
// *************************
// 簡(jiǎn)單選擇排序
// *************************
void SelectSort(SqList &L)
{
// 選擇第 i 小的記錄, 并交換到位
for (int i=1; i<L.length; i++)
{
int j = i;
// 在L.r[i...L.length]中選擇關(guān)鍵字最小的記錄
for (int k=i+1; k<=L.length; k++)
{
if (L.r[k].key < L.r[j].key)
j = k;
if (i!=j) // 與第 i 個(gè)記錄互換
{
L.r[0] = L.r[i];
L.r[i] = L.r[j];
L.r[j] = L.r[0];
}
}
}
}
// *************************
// 堆排序(大頂堆)
// *************************
// 已知H.r[s...m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義,
// 本函數(shù)依據(jù)關(guān)鍵字的大小對(duì)H.r[s]進(jìn)行調(diào)整, 使H.r[s...m]成為一個(gè)大頂堆
void HeapAdjust(SqList &H, int s, int m)
{
H.r[0] = H.r[s]; // 暫存根結(jié)點(diǎn)的記錄
// 沿關(guān)鍵字較大的孩子的結(jié)點(diǎn)向下篩選
for (int j=2*s; j<=m; j*=2)
{
if (j<m && H.r[j].key<H.r[j+1].key)
j++; // j 為關(guān)鍵字較大的孩子記錄的下標(biāo)
if (H.r[0].key >= H.r[j].key) break; // 不需要調(diào)整, 跳出循環(huán)
H.r[s] = H.r[j]; // 將大關(guān)鍵字記錄上調(diào)
s = j;
}
H.r[s] = H.r[0]; // 回移篩選下來(lái)的記錄
}
// 對(duì)順序表H進(jìn)行堆排序
void HeapSort(SqList &H)
{
// 將 H 建成大頂堆
for (int i=H.length/2-1; i>0; i--)
{
HeapAdjust(H, i, H.length);
}
// 互換"堆頂"和"堆底"的記錄
H.r[0] = H.r[1];
H.r[1] = H.r[H.length];
H.r[H.length] = H.r[0];
for (int i=H.length-1; i>1; i--)
{
HeapAdjust(H, 1, i); // 從根開始調(diào)整, 將H.r[1...i]重新調(diào)整為大頂堆
H.r[0] = H.r[1];
H.r[1] = H.r[i];
H.r[i] = H.r[0];
}
}
// *************************
// 2-路歸并排序
// *************************
// 將有序的SR[i...m]和SR[m+1...n]歸并為有序的TR[i...n]
void Merge(RcdType SR[], RcdType TR[], int i, int m, int n)
{
int j, k;
// 將SR中記錄按關(guān)鍵字從小到大地復(fù)制到TR中
for (j=m+1, k=i; i<=m && j<=n; k++)
{
if (SR[i].key <= SR[j].key)
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
// 將剩余的SR[i...m]復(fù)制到TR
while (i<=m)
TR[k++] = SR[i++];
// 將剩余的SR[j...n]復(fù)制到TR
while (j<=n)
TR[k++] = SR[j++];
}
// 對(duì)SR[s...t]進(jìn)行歸并排序, 排序后的記錄存入TR1[s...t]
void MSort(RcdType SR[], RcdType TR1[], int s, int t)
{
if (s == t)
TR1[s] = SR[s];
else
{
int m = (s+t)/2; // 將SR[s...t]平分平SR[s...m] 和 SR[m+1...t]
RcdType *TR2 = new RcdType[MAXSIZE+1];
MSort(SR, TR2, s, m); // 遞歸地將 SR[s...m]歸并為有序的TR2[s...m]
MSort(SR, TR2, m+1, t); // 遞歸地將SR[m+1...m]歸并為有序列的TR2[m+1...t]
Merge(TR2, TR1, s, m, t); // 將TR2[s...m]和TR2[m+1...t]歸并到 TR1[s...t]
delete[] TR2;
}
}
// 對(duì)順序表作2-路歸并排序
void MergeSort(SqList &L)
{
MSort(L.r, L.r, 1, L.length);
}
void _tmain()
{
SqList sqList;
sqList.length = MAXSIZE;
Random* random = new Random;
for (int i=1; i<(MAXSIZE+1); i++)
{
sqList.r[i].key = random->Next(100);
}
//delete random;
std::cout << "排序前的順序表:\n";
for (int i=1; i<(MAXSIZE+1); i++)
{
std::cout << sqList.r[i].key << " ";
}
std::cout << '\n';
//InsertSort(sqList); //直接插入排序
//BInsertSort(sqList); // 折半插入排序
// 希爾排序
//int dlta[] = {9, 5, 3, 2, 1};
//ShellSort(sqList, dlta, 5);
// 起泡排序
//BubbleSort(sqList);
//BubbleSort_(sqList);
// 快速排序
//QuickSort(sqList);
// 簡(jiǎn)單選擇排序
//SelectSort(sqList);
// 堆排序
//HeapSort(sqList);
// 歸并排序
MergeSort(sqList);
std::cout << "排序后的順序表:\n";
for (int i=1; i<(MAXSIZE+1); i++)
{
std::cout << sqList.r[i].key << " ";
}
std::cout << '\n';
int x;
std::cin>>x;
}