本文主要是介绍温故而知新 -＞ 数据结构 -＞排序 -＞程序实现2_利用C++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

温故而知新 -＞ 数据结构 -＞排序 ->程序实现2_利用C++

本篇博客是基于 温故而知新 -＞ 数据结构 -＞排序 中部分 排序 的理论知识进行程序实现！

其中实现了 交换排序中的三种快速排序、递归与非递归的归并排序、非比较排序等！并附带了相关实例以及对应的运行结果！

由于上述的程序实现中使用了顺序表和队列，即还需实现顺序表与队列这两个内容，如此会导致程序代码量大幅增多。而在程序中，为了清晰展示各部分的实现代码，所以加上各自的头文件共有 5 个文件，即 Queue.h 、SeqList.h 、queue.cpp 、seqList.cpp 和 main.cpp 。

其中 Queue.h 和queue.cpp 的内容与 温故而知新-＞数据结构-＞队列-＞程序实现2_利用类 博客中的 queue.h 和 main.cpp 对应且相同，但为方便本次程序的运行，需将上述博客的 main.cpp 中的 test() 与 main() 两个函数进行删除或注释；
而 SeqList.h 和 seqList.cpp 的内容与 温故而知新-＞数据结构-＞顺序表-＞程序实现2_利用类 博客中的 seqList.h 和 main.cpp 对应且相同，也为方便本次程序的运行，需将上述博客的 main.cpp 中的 test() 与 main() 两个函数进行删除或注释。

在下述内容中将附上本次程序的 main.cpp 文件内容，其他文件内容可根据上述指引自行查看！

注意：下述代码多多少少有点冗余，且未考虑性能最优，读者有兴趣可进一步精简！

具体内容如下：

（1）main.cpp

#include"Queue.h"
#include"SeqList.h"
#include<string>

void swap(int *arr, int a, int b)
{
	int t = arr[a];
	arr[a] = arr[b];
	arr[b] = t;
}

// 交换排序 之 冒泡排序  从小到大
void BubbleSort(int *arr, int n)
{
	int m = n;
	while (m > 1)
	{
		int flag = 0;
		for (int i = 1; i < n; i++)
		{
			if (arr[i - 1] > arr[i])
			{
				swap(arr, i - 1, i);
				flag = 1;
			}
		}
		if (!flag)
			break;
		m--;
	}
}

//快速排序中设定基准值
int getMid(int *arr, int begin, int end)
{
	int mid = begin + (end - begin) / 2;
	if (arr[begin] > arr[end])
	{
		if (arr[mid] <= arr[end])//arr[begin] > arr[end] > arr[mid]
			return end;
		else if (arr[begin] <= arr[mid])// arr[mid] > arr[begin] > arr[end] 
			return begin;
		else//arr[begin] > arr[mid] > arr[end]
			return mid;
	}
	else //arr[begin] <= arr[end]
	{
		if (arr[mid] <= arr[begin]) // arr[mid] < arr[begin] < arr[end]
			return begin;
		else if (arr[mid] >= arr[end])//  arr[begin] < arr[end] < arr[mid] 
			return end;
		else// arr[begin] <= arr[mid] <= arr[end] 
			return mid;
	}
}
// 交换排序 之 快速排序 之 hoare法
// 返回划分后基准值所在的位置
int partion(int *arr, int begin, int end)
{
	int mid = getMid(arr, begin, end);
	//将基准值放到起始位置
	swap(arr, begin, mid);
	int key = arr[begin];
	int start = begin;
	while (begin < end)
	{
		//从后向前先找小于基准值的位置
		while (begin < end && arr[end] >= key)
			--end;
		//从前往后找大于基准值的位置
		while (begin < end && arr[begin] <= key)
			++begin;
		swap(arr, begin, end);
	}
	//交换基准值与相遇位置的数据
	swap(arr, start, begin);
	return begin;
}
// 交换排序 之 快速排序 之 挖坑法
int partion2(int *arr, int begin, int end)
{
	int mid = getMid(arr, begin, end);
	swap(arr, begin, mid);
	// 第一个值作为基准值，第一个位置为初始的坑的位置
	int key = arr[begin];
	while (begin < end)
	{
		while (begin < end && arr[end] >= key)
			--end;
		arr[begin] = arr[end];
		while (begin < end && arr[begin] <= key)
			++begin;
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	return begin;
}
// 交换排序 之 快速排序 之 前后指针法
int partion3(int *arr, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int key = arr[begin];
	while (cur <= end)
	{
		if (arr[cur] < key && ++prev != cur)//小于基准值且不连续时进行交换
		{
			swap(arr, prev, cur);
		}
		++cur;
	}
	swap(arr, begin, prev);
	return prev;
}
// 交换排序 之 递归快排
void quickSort(int *arr, int begin, int end)//hoare的实现
{
	if (begin >= end)
		return;
	int div = partion3(arr, begin, end);
	//对左右两部分进行快速排序
	quickSort(arr, begin, div - 1);
	quickSort(arr, div + 1, end);
}
// 非递归快排 用顺序表
void quickSortNor(int *arr, int n)
{
	//创建顺序表
	SeqList sq;
	sq.PushBack(n - 1);
	sq.PushBack(0);
	while (!sq.Empty())
	{
		int left = sq.ListBack();
		sq.PopBack();
		int right = sq.ListBack();
		sq.PopBack();

		int div = partion(arr, left, right);

		if (left < div - 1)
		{
			sq.PushBack(div - 1);
			sq.PushBack(left);
		}
		if (div + 1 < right)
		{
			sq.PushBack(right);
			sq.PushBack(div + 1);
		}
	}
}
// 非递归快排 用队列  先进先出
void quickSortNor2(int *arr, int n)
{
	Queue q;
	q.QueuePush(0);
	q.QueuePush(n - 1);

	while (!q.QueueEmpty())
	{
		int left = q.QueueFront();
		q.QueuePop();
		int right = q.QueueFront();
		q.QueuePop();

		int div = partion(arr, left, right);
		if (left < div - 1)
		{
			q.QueuePush(left);
			q.QueuePush(div - 1);
		}
		if (div + 1 < right)
		{
			q.QueuePush(div + 1);
			q.QueuePush(right);
		}
	}
}

//归并排序
//相邻子序列合并
void merge(int *arr, int begin, int mid, int end, int *tmp)
{
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;

	//辅助空间的起始位置
	int idx = begin;

	//合并有序序列
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
			tmp[idx++] = arr[begin1++];
		else
			tmp[idx++] = arr[begin2++];
	}

	//判断是否有未合并的元素,下面语句实现的功能是将原数组中的[begin,end]中的数据拷贝到
	//合并后之后的位置上了，防止一些数据没有合并到
	if (begin1 <= end1)
		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
	if (begin2 <= end2)
		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));

	//合并之后的序列拷贝到原始数据的对应区间
	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void _mergeSort(int *arr, int begin, int end, int *tmp)
{
	if (begin >= end)
		return;
	int mid = begin + (end - begin) / 2;
	_mergeSort(arr, begin, mid, tmp);
	_mergeSort(arr, mid + 1, end, tmp);
	merge(arr, begin, mid, end, tmp);
}
void mergeSort(int *arr, int n)//递归
{
	int *tmp = (int*)malloc(sizeof(int)*n);
	_mergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

//归并非递归
void mergeSortNor(int *arr, int n)
{
	int *tmp = (int*)malloc(sizeof(int)*n);
	int step = 1;
	while (step < n)
	{
		for (int idx = 0; idx < n; idx += 2 * step)
		{
			int begin = idx;
			int mid = idx + step - 1;
			if (mid >= n - 1)//判断是否存在第二个子序列，不存在直接跳过
				continue;
			int end = idx + 2 * step - 1;
			if (end >= n)
				end = n - 1;
			merge(arr, begin, mid, end, tmp);
		}
		step *= 2;
	}
	//free(tmp);
}

//非比较排序
void countSort(int *arr, int n)
{
	int max, min;
	min = max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (min > arr[i])
			min = arr[i];
		if (max < arr[i])
			max = arr[i];
	}
	int range = max - min + 1;
	int *tmp = (int*)calloc(range, sizeof(int));
	//计数  计算arr中相同数字的个数
	for (int i = 0; i < n; i++)
	{
		tmp[arr[i] - min]++;
	}
	//遍历计数数组tmp，进行排序
	int idx = 0;
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			arr[idx++] = i + min;
		}
	}
}

//打印数组
void printArr(int *arr, int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}

void test()
{
	int arr1[] = { 6, 3, 1, 8, 7, 2, 4 };
	int n = sizeof(arr1) / sizeof(arr1[0]);
	int *arr2 = (int*)malloc(sizeof(int)*n);
	memcpy(arr2, arr1, sizeof(arr1));
	cout << "排序前内容："<< endl;
	printArr(arr1, n); cout << endl;

	cout << "冒泡排序后内容：" << endl;
	BubbleSort(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "递归快排后内容：" << endl;
	quickSort(arr2, 0, n - 1);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "非递归快排(利用顺序表)后内容：" << endl;
	quickSortNor(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "非递归快排(利用队列 )后内容：" << endl;
	quickSortNor(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "递归归并后内容：" << endl;
	mergeSort(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "非递归归并后内容：" << endl;
	mergeSortNor(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));

	cout << "非比较排序后内容：" << endl;
	countSort(arr2, n);
	printArr(arr2, n); cout << endl;
	memcpy(arr2, arr1, sizeof(arr1));
}

int main()
{
	test();
	system("pause");
	return 0;
}

（2）运行结果

侵权删~

这篇关于温故而知新 -＞ 数据结构 -＞排序 -＞程序实现2_利用C++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！