《大话数据结构》C++实现七大排序算法详细代码

如下图所示的代码，是《大话数据结构》第9章节中的七大排序算法汇总，本人写了一个main主函数来进行算法排序的测试，只要把代码运行起来后在终端中输入10个数字然后回车就能把所有排序算法的结果打印出来，如果需要输入其他数目的数字，只需要修改代码中最前面定义的MAXSIZE函数就行。

#include<iostream>

using namespace std;

constexpr auto MAXSIZE = 10;

typedef int status;

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

void swap(SqList* L, int i, int j);

//简单比较排序
void BubbleSort0(SqList* L);

//冒泡排序函数声明
void BubbleSort(SqList* L);

//插入排序函数声明
void InsertSort(SqList* L);

//希尔排序函数声明
void ShellSort(SqList *L);

//堆排序用到的函数声明
void HeapSort(SqList *L);
void HeapAdjust(SqList *L,int s,int m);

//归并排序用到的函数声明
void MergeSort(SqList *L);
void MSort(int SR[],int TR1[],int s,int t);
void Merge(int SR[],int TR[],int i,int m,int n);

//快速排序用到的函数声明
void QuickSort(SqList* L);
void QSort(SqList *L,int low,int high);
int Partition(SqList *L,int low,int high);

/*交换L中数组r的下标为i和j的值*/
void swap(SqList* L, int i, int j)
{
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}

//一、直接简单比较来排序
void BubbleSort0(SqList* L)
{
	for (int i = 1; i < L->length; i++)
	{
		for (int j = i + 1; j <= L->length; j++)
		{
			if (L->r[i] > L->r[j])
			{
				swap(L, i, j);
			}
		}
	}
}

//二、冒泡排序
void BubbleSort(SqList* L)
{
	for (int i = 1; i < L->length; i++)
	{
		for (int j = L->length - 1; j >= i; j--)
		{
			if (L->r[j] > L->r[j + 1])
			{
				swap(L, j, j + 1);
			}
		}
	}
}


//三、直接插入排序
void InsertSort(SqList* L)
{
	int i, j;
	for (i = 2; i <= L->length; i++)
	{
		if (L->r[i] < L->r[i - 1])
		{
			L->r[0] = L->r[i];
			for (j = i - 1; L->r[j] > L->r[0]; j--)
			{
				L->r[j + 1] = L->r[j];
			}
			L->r[j + 1] = L->r[0];
		}
	}
}

//四、希尔排序
void ShellSort(SqList* L)
{
	int i, j;
	int increment = L->length;
	do
	{
		increment = increment / 3 + 1;
		for ( i = 1+increment; i <= L->length; i++)
		{
			if (L->r[i]<L->r[i-increment])
			{
				L->r[0] = L->r[i];
				for ( j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment)
				{
					L->r[j + increment] = L->r[j];
				}
				L->r[j + increment] = L->r[0];
			}
		}
	} while (increment>1);
}

//五、堆排序
void HeapSort(SqList* L)
{
	//把L中的顺序表r构建成大顶堆的数字排列
	int i;
	for ( i = L->length; i > 0; i--) 
	{
		HeapAdjust(L,i,L->length);
	}

	//开始不断循环进行堆排序（截取根节点）和不断进行堆调整
	for ( i = L->length; i > 1; i--)
	{
		swap(L,1,i);
		HeapAdjust(L,1,i-1);
	}
}

//大顶堆构建函数
void HeapAdjust(SqList* L, int s, int m)
{
	int temp, j;
	temp = L->r[s];
	for ( j = 2*s; j <= m; j*=2)
	{
		if (j<m && L->r[j]<L->r[j+1])
		{
			++j;
		}

		if (temp>=L->r[j])
		{
			break;
		}

		L->r[s] = L->r[j];
		s = j;
	}
	L->r[s] = temp;
}



//六、归并排序
void MergeSort(SqList* L)
{
	MSort(L->r,L->r,1,L->length);
}

void MSort(int SR[], int TR1[], int s, int t)
{
	int m;
	int TR2[MAXSIZE+1];
	if (s==t)
	{
		TR1[s] = SR[s];
	}
	else
	{
		m = (s + t) / 2;
		MSort(SR, TR2, s, m);
		MSort(SR, TR2,m+1, t);
		Merge(TR2,TR1,s,m,t);
	}
}

void Merge(int SR[], int TR[], int i, int m, int n)
{
	int j, k, l;
	for ( j = m+1,k=i;i<=m && j<=n; k++)
	{
		if (SR[i]<SR[j])
		{
			TR[k] = SR[i];
			i++;
		}
		else
		{
			TR[k] = SR[j];
			j++;
		}
	}

	if (i<=m)
	{
		for ( l = 0; l <= m-i; l++)
		{
			TR[k + l] = SR[i + l];
		}
	}
	if (j<=n)
	{
		for (l = 0; l <= n - j; l++)
		{
			TR[k + l] = SR[j + l];
		}
	}
}

//七、快速排序
void QuickSort(SqList* L)
{
	QSort(L,1,L->length);
}

void QSort(SqList* L, int low, int high)
{
	int pivot;
	if (low<high)
	{
		pivot = Partition(L,low,high);

		QSort(L,low,pivot-1);
		QSort(L,pivot+1,high);
	}
}

int Partition(SqList* L, int low, int high)
{
	int pivotkey;
	pivotkey = L->r[low];
	while (low<high)
	{
		while (low<high && L->r[high]>=pivotkey)
		{
			high--;
		}
		swap(L,low,high);
		while (low<high && L->r[low]<=pivotkey)
		{
			low++;
		}
		swap(L,low,high);
	}
	return low;
}

int main()
{
	cout << "请输入" << MAXSIZE << "个数字：" << endl;
	int num;
	SqList L;
	L.length = MAXSIZE;

	for (int i = 1; i <= MAXSIZE; i++)
	{
		cin >> L.r[i];
	}

	//简单排序并输出排序结果
	BubbleSort0(&L);
	cout << "简单排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//冒泡排序并输出排序结果
	BubbleSort(&L);
	cout << "冒泡排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//直接插入排序并输出排序结果
	InsertSort(&L);
	cout << "直接插入排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//希尔排序并输出排序结果
	ShellSort(&L);
	cout << "希尔排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//堆排序并输出排序结果
	HeapSort(&L);
	cout << "堆排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//归并排序并输出排序结果
	MergeSort(&L);
	cout << "归并排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;

	//快速排序并输出排序结果
	QuickSort(&L);
	cout << "快速排序后输出的结果是：" << endl;
	for (int i = 1; i <= MAXSIZE; i++)
	{
		cout << L.r[i] << " ";
	}
	cout << endl;
	return 0;
}