排序算法C++

#include <iostream>
#include <string>
using namespace std;

#define MAXSIZE 30
typedef struct {
int key;
string name;
}RedType;

typedef struct SqList {
RedType r [MAXSIZE+1];
int length;
}SqList;

//插入排序
///////////////////////////////////////////////////////////////////
//直接插入排序 时间复杂度O（n2）
//r[0]处设为哨兵

void insertSort(SqList &L) {
for (int i=2; i<=L.length; i++) {
if (L.r[i].key < L.r[i-1].key) {
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];
}
}
}
//////////////////////////////////////////////////////////////////
void insertS(SqList &L) {
for (int i=2; i<=L.length;i++) {
if (L.r[i].key<L.r[i-1].key) {
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];
}
}

}
///////////////////////////////////////////////////////////////////
//折半插入排序
void BinsertSort(SqList &L) {
for (int i=2; i<=L.length; ++i) {
L.r[0] = L.r[i];
int low = 1, high = i-1;
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>=high+1; --j) {  //记录后移
L.r[j+1] = L.r[j];
}
L.r[high+1] = L.r[0];  //插入r[0]
}

}
//////////////////////////////////////////////////////
//希尔排序
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[0] = L.r[i];
for (int j=i-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];
}
}
}
void ShellSort(SqList &L,int dt[], int t) {
for (int k=0; k<t; ++k){
ShellInsert(L,dt[k]);
}
}
//交换排序
///////////////////////////////////////////////////////
//冒泡排序 时间复杂度O(n2)
void BubbleSort(SqList &L) {
int m= L.length-1;
bool flag = true;
while(m>0&&flag) {
flag =false;
for (int j=1; j<m; j++) {
if (L.r[j].key > L.r[j+1].key) {
flag = true;
RedType temp;
temp = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = temp;
}
}
--m;
}

}
//////////////////////////////////////////////////////////
void bubbleSort(SqList &L) {

for (int i=0; i<L.length;i++) {
for (int j=i; j<L.length-1-i; i++) {
if (L.r[j].key>L.r[j+1].key) {
RedType temp;
temp = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = temp;
}
}
}

}
//快速排序 O(nlog2n)
//////////////////////////////////////////////////////
int Partition(SqList &L, int low, int high) {
L.r[0] = L.r[low];
int pivotkey = L.r[low].key;

while (low < high) {
while (low <high&&L.r[high].key >= pivotkey) --high;
L.r[low] = L.r[high]; //比枢轴记录小的移动到低端
while (low<high&&L.r[low].key <= pivotkey) ++low;
L.r[high] = L.r[low];  //比枢轴记录大的移动到低端

}
L.r[low] = L.r[0];   //枢轴记录到位
return low;
}

void QSort(SqList &L, int low, int high) {
if (low < high) {
int pivotloc = Partition(L, low, high);  //找到第一次的枢轴位置
QSort(L, low, pivotloc-1);
QSort(L, pivotloc+1, high);
}

}
//调用 Qsort(L, 1, L.length);

//////////////////////////////////////////////////////
//选择排序 时间复杂度 O(n2)
void SelectSort(SqList &L) {
for (int i=1; i<L.length; i++) {
int k = i;
for (int j=i+1; j<=L.length; ++j) { //选择挂件子最小的记录
if(L.r[j].key<L.r[k].key) {
k = j;
}
}
if (k!=i) {
RedType temp;
temp = L.r[i];
L.r[i] = L.r[k];
L.r[k] = temp;
}
}
}
//////////////////////////////////////////////////////