整理以前的学习笔记，有以下的代码片断：
// 内排序常用算法
// 在Microsoft Visual C++ .NET下编译通过
#include <iostream>
#include <tchar.h>
using namespace System;
//namespace sortProgram
//{
const int MAXSIZE = 20; // 假设的顺序表最大长度
typedef int KeyType; // 关键字类型 设定关键字为整型
class RcdType
{
public:
KeyType key; // 关键字项
// 其他项
};
// 顺序表类型
class SqList
{
public:
RcdType r[MAXSIZE+1]; // r[0]闲置或作为判别标志的"哨兵"单元
int length; // 顺序表长度
};
//}
// *************************
// 直接插入排序
// *************************
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]; //设哨兵
// 记录后移
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) // 插入点在低半区
high = m-1;
else //插入点在高半区
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];
}
}
// *************************
// 希尔排序
// *************************
// 对顺序表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]对顺序表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;
}
}
}
}
// *************************
// 起泡算法的改进
// *************************
// 记下最后进行交换的记录的位置
// 在此位置之后的记录已是有序, 不必进行比较
void BubbleSort_(SqList &L)
{
int i = L.length;
while (i > 1) // i>1 表明上一趟曾进行过记录的交换
{
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; // 记下进行交换的记录的位置
}
}
i = lastExchangeIndex; // 一趟起泡后仍处于无序状态的最后一个记录的位置
}
}
// *************************
// 快速排序
// *************************
// 对记录子序列 R[low...high] 进行一趟快速排序, 并返回枢轴记录所在位置
// 使得在它之前的记录的关键字均不大于它的关键字,
// 而在它之前的记录的关键字均不小于它的关键字
int Partition(RcdType R[], int low, int high)
{
R[0] = R[low]; // 将枢轴记录移至数组的闲置分量
KeyType pivotkey = R[low].key; // 枢轴记录关键字
// 从表的两端交替地向中间扫描
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; // 返回枢轴位置
}
// 对记录序列 R[s...t] 进行快速排序
void QSort(RcdType R[], int s, int t)
{
if (s < t)
{
int pivotloc = Partition(R, s, t); // 对 R[s...t] 进行一趟快排, 并返回枢轴位置
QSort(R, s, pivotloc-1); // 对低子序列递归进行排序
QSort(R, pivotloc+1, t); // 对高子序列递归进行排序
}
}
// 对顺序表 L 进行快速排序
void QuickSort(SqList &L)
{
QSort(L.r, 1, L.length);
}
// *************************
// 简单选择排序
// *************************
void SelectSort(SqList &L)
{
// 选择第 i 小的记录, 并交换到位
for (int i=1; i<L.length; i++)
{
int j = i;
// 在L.r[i...L.length]中选择关键字最小的记录
for (int k=i+1; k<=L.length; k++)
{
if (L.r[k].key < L.r[j].key)
j = k;
if (i!=j) // 与第 i 个记录互换
{
L.r[0] = L.r[i];
L.r[i] = L.r[j];
L.r[j] = L.r[0];
}
}
}
}
// *************************
// 堆排序(大顶堆)
// *************************
// 已知H.r[s...m]中记录的关键字除H.r[s].key之外均满足堆的定义,
// 本函数依据关键字的大小对H.r[s]进行调整, 使H.r[s...m]成为一个大顶堆
void HeapAdjust(SqList &H, int s, int m)
{
H.r[0] = H.r[s]; // 暂存根结点的记录
// 沿关键字较大的孩子的结点向下筛选
for (int j=2*s; j<=m; j*=2)
{
if (j<m && H.r[j].key<H.r[j+1].key)
j++; // j 为关键字较大的孩子记录的下标
if (H.r[0].key >= H.r[j].key) break; // 不需要调整, 跳出循环
H.r[s] = H.r[j]; // 将大关键字记录上调
s = j;
}
H.r[s] = H.r[0]; // 回移筛选下来的记录
}
// 对顺序表H进行堆排序
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); // 从根开始调整, 将H.r[1...i]重新调整为大顶堆
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中记录按关键字从小到大地复制到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]复制到TR
while (i<=m)
TR[k++] = SR[i++];
// 将剩余的SR[j...n]复制到TR
while (j<=n)
TR[k++] = SR[j++];
}
// 对SR[s...t]进行归并排序, 排序后的记录存入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;
}
}
// 对顺序表作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);
// 简单选择排序
//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;
}