数据结构 各种排序排列100000个数所需的是时间

数据结构 各种排序排列100000个数所需的是时间

注：本程序由Visual Studio 2015编写，与VC++6.0稍有区别，复制到VC++6.0注释掉“#include “stdafx.h””即可运行，复制到VS可直接运行。
#include “stdafx.h”
#include
#include <stdlib.h>
#include <time.h>
#include<process.h>
#include <Windows.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNDERFLOW -2
#define MAXSIZE 100000 // 待排记录最大个数
#define LIST_INIT_SIZE 10000//顺序表存储空间的初始分配量
typedef int Status;
typedef int keyType;
typedef struct {
keyType key; // 关键字域
}ElemType; // 记录类型
typedef struct {
ElemType elem;
ElemType r[MAXSIZE + 1]; //r[0]闲置，作哨兵或临时单元
int length; // 顺序表长度
}SqList; // 顺序表类型
SqList L1,L2;
//构造一个空的顺序表
Status InitList(SqList &L) {
L.elem = (ElemType)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 100000;
return OK; //OK是1
}
//生成随机数
void CreateList(SqList &L) {
//时间种子，从1900年1月1日到现在的时间秒数，使rand（）产生一个随机数
srand((unsigned)time(NULL));
for (int i = 0; i < 100000; i++)
L.r[i].key = rand();
}
//排序栈
void SortL(SqList &L2,SqList L1) {
for (int i = 0; i < 100000; i++)
L2.r[i].key = L1.r[i].key;
}
//直接插入排序
void InsertionSort(SqList &L) {
// 对顺序表 L 作直接插入排序
int i, j;
for (i = 2; i <= L.length; ++i) //n-1趟
if (L.r[i].key < L.r[i - 1].key) {
L.r[0] = L.r[i]; // 设置哨兵
for (j = i - 1; L.r[0].key < L.r[j].key; --j)
L.r[j + 1] = L.r[j]; // 记录向后顺移
L.r[j + 1] = L.r[0]; // 插入到正确位置
}
}
//折半插入排序
void BiInsertionSort(SqList &L) {
int i, j, m, low, high;
for (i = 2; i <= L.length; ++i) {
L.r[0] = L.r[i]; //设置哨兵
//在 L.r[1…i-1]中折半查找插入位置
low = 1; high = i - 1;
while (low <= high) { //结束时low=high+1
m = (low + high) / 2;
if (L.r[0].key < L.r[m].key)
high = m - 1; // 插入点在左半区
else low = m + 1; // 插入点在右半区
}
for (j = i - 1; j >= low; --j) L.r[j + 1] = L.r[j];
L.r[low] = L.r[0]; // 插入元素
}
}
//一趟希尔排序
void ShellInsert(SqList &L, int d) {
int j, i;
for (i = d + 1; i <= L.length; ++i)
if (L.r[i].key < L.r[i - d].key) {
L.r[0] = L.r[i]; // 暂存在R[0]
for (j = i - d; j > 0 && (L.r[0].key < L.r[j].key); j -= d)
L.r[j + d] = L.r[j]; // 记录后移
L.r[j + d] = L.r[0]; // 插入元素
}
}
//希尔排序
void ShellSort(SqList &L, int dlta[], int t) {
int k;
//希尔排序算法，t个增量存放在dlta[]中
for (k = 0; k < t; ++k)//k趟shell排序
ShellInsert(L, dlta[k]);//调用一趟shell排序算法
}

//冒泡排序
void BubbleSort(SqList &L) { //优化版
int i = L.length,j, jhwz; //第1趟默认交换记录位置为L.length
while (i > 1) {
jhwz = 1;//本趟排序开始，最后一个被交换的记录的位置设为1
for (j = 1; j < i; j++)
if (L.r[j + 1].key < L.r[j].key) {
L.r[j].key += L.r[j + 1].key;
L.r[j + 1].key = L.r[j].key - L.r[j + 1].key;
L.r[j].key -= L.r[j + 1].key;
jhwz = j; //进行交换的记录位置
}
i = jhwz; // 下趟进行比较的最后一个记录位置
}
}
//快速排序一次
int Partition(SqList &L, int low, int high) {
int pivotkey;
L.r[0] = L.r[low]; pivotkey = L.r[0].key; // 枢轴
while (low < high) {//循环结束时lowhigh
//从右向左搜索关键字比枢轴小的记录并控制越界
while (low < high && L.r[high].key >= pivotkey) --high;
if (low < high) L.r[low++] = L.r[high]; //小的到左部
//从左向右搜索关键字比枢轴大的记录并控制越界
while (low < high && L.r[low].key <= pivotkey) ++low;
if (low < high) L.r[high–] = L.r[low]; //大的到右部
}
L.r[low] = L.r[0];
return low; //lowhigh
}
//快速排序
void QSort(SqList &L, int low, int high) {
int pivotloc;
// 对记录序列L.r[low…high]进行快速排序
if (low < high) { // 记录个数大于1
pivotloc = Partition(L, low, high);
// 对 L.r[low…high] 进行一次划分
QSort(L, low, pivotloc - 1); // 对左部进行快速排序
QSort(L, pivotloc + 1, high); // 对右部进行快速排序
}
}
//简单选择排序
void SelectSort(SqList &L) {//简单选择排序
int i, j, min;
for (i = 1; i < L.length; ++i) {
//在L.r[i…L.length]中选择关键字最小的记录
min = i;
for (j = i + 1; j <= L.length; j++)
if (L.r[j].key < L.r[min].key) min = j;
/* 若min不等于i，说明找到最小值，交换 */
if (min != i) {
L.r[min].key += L.r[i].key;
L.r[i].key = L.r[min].key - L.r[i].key;
L.r[min].key = L.r[min].key - L.r[i].key;
}
}
}

int main()
{
clock_t start, end;
//希尔排序步长
int dlta[] = { 50000,25000,12500,6250,3125,1562,781,390,195,97,48,24,12,6,3,1 };
//生成随机数的原始栈
InitList(L1);
//排序栈
InitList(L2);
cout << “tttt*ttttt*”;
cout << endl << “tttt*t计科1512-02210151232-杨少通t*” << endl;
cout << “tttt*****************************************” << endl << endl;
cout << “tttt六种排序” << endl << endl;
//原始栈生成随机数
CreateList(L1);
//将原始栈数据复制到排序栈
SortL(L2, L1);
cout << “直接插入排序时间：”;
start = clock();
InsertionSort(L2);
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
cout << “折半插入排序时间：”;
start = clock();
BiInsertionSort(L2);
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
cout << “希尔排序时间：”;
start = clock();
ShellSort(L2, dlta, 16);//"16"为希尔步长个数
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
start = clock();
cout << “冒泡排序时间：”;
BubbleSort(L2);
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
cout << “快速排序时间：”;
start = clock();
QSort(L2, 1, L2.length);
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
cout << “简单选择排序时间：”;
start = clock();
SelectSort(L2);
end = clock();
cout << end - start << “毫秒” << endl << endl;
SortL(L2, L1);
return 0;
}
代码均为原创，存在不足还请见谅！如有转载请注明来源： www.dreamload/blog/?p=467&preview=true （洋葱先生）