排序方法C++实现

#include<iostream>
#include<string>
#include<cstdlib>
#include<ctime>
#include<math.h>
#include"head.h"
#define randon(x) rand()%(x)
using namespace std;


void ShowSql(SqList& q)
{
	for (int i = 1; i <= q.length; i++)
	{
		cout << q.r[i].key << ' ';
	}
	cout << endl;
}


SqList Initial(SqList& q)
{
	srand((int)time(0));  // Use system time to creat a random seed.
	q.length = 0;
	q.r[0].key = 0;
	for (int i = 1; i < 80; i++)
	{
		q.r[i].key = randon(100);
		q.length++;
	}
	//cout << "Generating a random table: ";
	//ShowSql(q);
	return q;
}


void InsertSort(SqList q)
{
	int i = 0, j = 0;
	for (i = 2; i <= q.length; ++i)
	{
		if (q.r[i].key < q.r[i - 1].key)
		{
			q.r[0] = q.r[i];
			for (j = i - 1; q.r[0].key < q.r[j].key; --j)
			{
				q.r[j + 1] = q.r[j];
			}
			q.r[j + 1] = q.r[0];
		}
		else { continue; }
	}
	//cout << "Method->Directly Insert Sort: ";
	//ShowSql(q);
}


void BinsertSort(SqList q)
{
	int low = 0, high = 0, mid = 0, j = 0;
	for (int i = 2; i <= q.length; ++i)
	{
		q.r[0] = q.r[i];
		low = 1;
		high = i - 1;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (q.r[0].key < q.r[mid].key) 
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		for (j = i - 1; j >= high + 1; --j)
		{
			q.r[j + 1] = q.r[j];
		}
		q.r[high + 1] = q.r[0];
	}
	//cout << "Method->Binary Insert Sort: ";
	//ShowSql(q);
}


void ShellSort(SqList q)
{
	SqList sq = q; // Try using q directly.
	int dk[5] = {31, 15, 7, 3, 1};
	//for (int i = 0; i <= 4; i++)  // Initialize dk with value 9, 7, 5, 3, 1.
	//{
	//	dk[i] = 16 - pow(2, i);
	//}
	for (int k = 0; k <= 4; k++)
	{
		ShellInsert(sq, dk[k]);
	}
	//cout << "Method->Shell Sort: ";
	//ShowSql(sq);
}


void ShellInsert(SqList& q, int dk)
{
	int i = 0, j = 0;
	for (i = dk + 1; i <= q.length; ++i)
	{
		if (q.r[i].key < q.r[i - dk].key)
		{
			q.r[0] = q.r[i];
			for (j = i - dk; j > 0 && (q.r[0].key < q.r[j].key); j -= dk)
			{
				q.r[j + dk] = q.r[j];
			}
			q.r[j + dk] = q.r[0];
		}
	}
}


void bubble_sort(SqList q)
{
	int m, j, flag = 1;
	RecType x;
	for (m = 1; (m <= q.length - 1) && (flag == 1); m++)
	{
		for (j = 1; j <= q.length - m; j++)
		{
			if (q.r[j].key > q.r[j + 1].key)
			{
				x = q.r[j];
				q.r[j] = q.r[j + 1];
				q.r[j + 1] = x;
			}
		}
	}
	//cout << "Method->Bubble Sort: ";
	//ShowSql(q);
}


void QuickSort(SqList q, int low, int high)
{
	SqList sq = q;
	Qsort(sq, low, high);
	//cout << "Method->Quick Sort: ";
	//ShowSql(sq);
}


void Qsort(SqList& q, int low, int high)
{
	int pivotloc;
	if (low < high)
	{
		pivotloc = Partition(q, low, high);
		Qsort(q, low, pivotloc - 1);
		Qsort(q, pivotloc + 1, high);
	}
}


int Partition(SqList& q, int low, int high)
{
	q.r[0] = q.r[low];
	int pivotkey = q.r[low].key;
	while (low < high)
	{
		while (low < high && q.r[high].key >= pivotkey)
		{
			--high;
		}
		q.r[low] = q.r[high];
		while (low < high && q.r[low].key <= pivotkey)
		{
			++low;
		}
		q.r[high] = q.r[low];
	}
	q.r[low] = q.r[0];
	return low;
}


void SelectSort(SqList q)
{
	RecType x;
	int k = 0, i = 1, j = 0;
	for (i = 1; i < q.length; ++i)
	{
		k = i;
		for (j = i + 1; j <= q.length; j++)
		{
			if (q.r[j].key < q.r[k].key)
			{
				k = j;
			}
		}
		if (k != i)
		{
			x = q.r[i];
			q.r[i] = q.r[k];
			q.r[k] = x;
		}
	}
	//cout << "Method->Select Sort: ";
	//ShowSql(q);
}


void HeapAdjust(SqList& q, int s, int m)
{
	int rc = q.r[s].key;
	int j = 0;
	for (j = 2 * s; j <= m; j *= 2)
	{
		if (j < m && (q.r[j].key < q.r[j + 1].key))
		{
			j++;
		}
		if (rc >= q.r[j].key) { break; }
		q.r[s] = q.r[j];
		s = j;
	}
	q.r[s].key = rc;
}


void HeapSort(SqList q)
{
	SqList qs = q;
	int n = qs.length;
	int i = 0;
	for (i = n / 2; i >= 1; i--)
	{
		HeapAdjust(qs, i, n);
	}
	for (i = n; i > 1; i--)
	{
		swap(&(qs.r[1].key), &(qs.r[i].key));
		HeapAdjust(qs, 1, i - 1);
	}
	//cout << "Method->Heap Sort: ";
	//ShowSql(qs);
}


void swap(int* a, int* b)
{
	int x;
	x = *b;
	*b = *a;
	*a = x;
}


int main()
{
	SqList* sql = new SqList;
	clock_t start, end, rst;
	clock_t sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0, sum5 = 0, sum6 = 0, sum7 = 0;
	for (int i = 0; i <=10; i++)
	{
		*sql = Initial(*sql);
		/*1*/
		start = clock();
		InsertSort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum1 += rst;
		/*2*/
		start = clock();
		BinsertSort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum2 += rst;
		/*3*/
		start = clock();
		ShellSort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum3 += rst;
		/*4*/
		start = clock();
		bubble_sort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum4 += rst;
		/*5*/
		start = clock();
		QuickSort(*sql, 1, sql->length);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum5 += rst;
		/*6*/
		start = clock();
		SelectSort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum6 += rst;
		/*7*/
		start = clock();
		HeapSort(*sql);
		end = clock();
		rst = (end - start);
		//cout << "Total time:" << rst << "ms" << endl;
		sum7 += rst;
	}
	cout << "InsertSort: " << sum1 << "ms" << endl;
	cout << "BinsertSort: " << sum2 << "ms" << endl;
	cout << "ShellSort: " << sum3 << "ms" << endl;
	cout << "bubble_sort: " << sum4 << "ms" << endl;
	cout << "QuickSort: " << sum5 << "ms" << endl;
	cout << "SelectSort: " << sum6 << "ms" << endl;
	cout << "HeaptSort: " << sum7 << "ms" << endl;
	delete sql;
	system("pause");
	return 0;
}

#pragma once
#define MAXSIZE 80
typedef int keytype;


typedef struct {
	keytype key;
	int otherinfo;
}RecType;


typedef struct {
	RecType r[MAXSIZE];
	int length;
}SqList;


SqList Initial(SqList& q);
void InsertSort(SqList q);
void ShowSql(SqList& q);
void BinsertSort(SqList q);
void ShellInsert(SqList& sq, int dk);
void ShellSort(SqList q);
void bubble_sort(SqList q);
int Partition(SqList& q, int low, int high);
void Qsort(SqList& q, int low, int high);
void QuickSort(SqList q, int low, int high);
void HeapAdjust(SqList& q, int s, int m);
void HeapSort(SqList q);
void swap(int* a, int* b);