文档章节

排序算法练习

能东棍
 能东棍
发布于 2017/05/19 17:43
字数 1083
阅读 12
收藏 0
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cassert>


std::vector<int> generateIntList(int size = 10)
{
	std::vector<int> result_list;
	std::generate_n(
		std::back_insert_iterator<std::vector<int>>(result_list),
		size,
		[]() { return std::rand() % 10; }
	);
	return std::move(result_list);
}

void showIntList(const std::vector<int>& ll)
{
	//std::cout << "list: ";
	std::copy(ll.begin(), ll.end(), std::ostream_iterator<int>(std::cout, " "));
	std::cout << "\n";
}


//插入排序
//每次遍历保证p位置的元素,比p左边的元素小
void insertSort(std::vector<int>& ll)
{
	for (decltype(ll.size()) p = 1; p < ll.size(); ++p)
	{
		auto tmp = ll[p];
		auto j = p;
		for (; j > 0 && tmp < ll[j - 1]; --j)
		{
			ll[j] = ll[j - 1];
		}
		ll[j] = tmp;
	}
}


void insertSort(std::vector<int>& ll, int left, int right)
{
	for (decltype(ll.size()) p = left + 1; p <= right; ++p)
	{
		auto tmp = ll[p];
		auto j = p;
		for (; j > left && tmp < ll[j - 1]; --j)
		{
			ll[j] = ll[j - 1];
		}
		ll[j] = tmp;
	}
}


//谢尔排序
//带增量的插入排序。。。
void shellSort(std::vector<int>& ll)
{
	for (auto gap = ll.size() / 2; gap > 0; gap /= 2)
	{
		for (auto p = gap; p < ll.size(); p++)
		{
			auto tmp = ll[p];
			auto j = p;
			for (; j >= gap && tmp < ll[j - gap]; j -= gap)
			{
				ll[j] = ll[j - gap];
			}
			ll[j] = tmp;
		}
	}
}


//堆排序
//先建立二叉大顶堆,交换堆顶元素和最后一个元素
//二叉堆的性质:位置在i的元素,左儿子在2i,右儿子在2i+1


//将位置i的元素下滤到指定的层数, 每次都是与左右两个儿子中的较大值进行交换, 大于两个儿子时停止下滤
void percDown(std::vector<int>& ll, int i, int n)
{
	auto leftChild = [](const int i) -> int {return 2 * i + 1; };

	int child;
	auto tmp = ll[i];
	for (; leftChild(i) < n; i = child)
	{
		child = leftChild(i);
		if (child != n - 1 && ll[child] < ll[child + 1])
		{
			++child;
		}

		if (tmp < ll[child])
		{
			ll[i] = ll[child];
		}
		else
		{
			break;
		}
	}
	ll[i] = tmp;
}

void heapSort(std::vector<int>& ll)
{
	//从下往上进行下滤操作,建立一个大顶堆
	for (int i = ll.size() / 2; i >= 0; --i)
	{
		percDown(ll, i, ll.size());
	}

	for (int j = ll.size() - 1; j > 0; --j)
	{
		std::swap(ll[0], ll[j]);//交换堆顶元素和最后一个元素
		percDown(ll, 0, j);//对堆顶进行下滤操作
	}
}


//归并排序
void merg(std::vector<int>& ll, std::vector<int>& tmpArray, int leftPos, int rightPos, int rightEnd)
{
	auto leftEnd = rightPos - 1;
	auto tmpPos = leftPos;
	auto numElements = rightEnd - leftPos + 1;

	while (leftPos <= leftEnd && rightPos <= rightEnd)
	{
		if (ll[leftPos] <= ll[rightPos])
		{
			tmpArray[tmpPos++] = ll[leftPos++];
		}
		else
		{
			tmpArray[tmpPos++] = ll[rightPos++];
		}
	}

	while (leftPos <= leftEnd)
	{
		tmpArray[tmpPos++] = ll[leftPos++];
	}

	while (rightPos <= rightEnd)
	{
		tmpArray[tmpPos++] = ll[rightPos++];
	}

	for (auto i = 0; i < numElements; i++, rightEnd--)
	{
		ll[rightEnd] = tmpArray[rightEnd];
	}
}

//分治策略, 数组切成两半,然后对两个数组进行排序之后, 然后再合并
void mergSortDriver(std::vector<int>& ll, std::vector<int>& tmpArray, int left, int right)
{
	if (left < right)
	{
		auto center = (left + right) / 2;
		mergSortDriver(ll, tmpArray, left, center);
		mergSortDriver(ll, tmpArray, center + 1, right);
		merg(ll, tmpArray, left, center + 1, right);
	}
}


void mergSort(std::vector<int>& ll)
{
	std::vector<int> tmpArray(ll.size());
	mergSortDriver(ll, tmpArray, 0, ll.size() - 1);
}



//快速排序
//选择一个枢纽元, 然后确保左边的元素小于枢纽元, 右边的元素大于枢纽元, 然后分别对左右两边分别进行快排
int median3(std::vector<int>& a, int left, int right)
{
	auto center = (left + right) / 2;
	if (a[center] < a[left])
	{
		std::swap(a[left], a[center]);
	}
	if (a[right] < a[left])
	{
		std::swap(a[left], a[right]);
	}
	if (a[right]<a[center])
	{
		std::swap(a[center], a[right]);
	}

	std::swap(a[center], a[right - 1]);
	return a[right - 1];
}

void quickSort(std::vector<int>& ll, int left, int right)
{
	if (left + 10 <= right)
	{
		auto pivot = median3(ll, left, right);

		auto i = left, j = right - 1;
		while (true)
		{
			while (ll[++i] < pivot) {}
			while (pivot < ll[--j]) {}
			if (i<j)
			{
				std::swap(ll[i], ll[j]);
			}
			else
			{
				break;
			}
		}

		std::swap(ll[i], ll[right - 1]);
		quickSort(ll, left, i - 1);
		quickSort(ll, i + 1, right);
	}
	else
	{
		insertSort(ll, left, right);
	}

}


void sort_test()
{
	if (true)
	{
		auto l1 = generateIntList();
		auto l2 = l1;
		std::cout << "insertSort>>>>" << '\n';
		std::cout << "before: ";
		showIntList(l1);

		insertSort(l1);
		std::cout << "l1: ";
		showIntList(l1);

		std::sort(l2.begin(), l2.end());
		std::cout << "l2: ";
		showIntList(l2);

		//用标准库的sort函数的结果来进行测试验证
		assert(l1 == l2);
	}

	if (true)
	{
		auto l1 = generateIntList();
		auto l2 = l1;
		std::cout << "shellSort>>>>" << '\n';
		std::cout << "before: ";
		showIntList(l1);

		shellSort(l1);
		std::cout << "l1: ";
		showIntList(l1);

		std::sort(l2.begin(), l2.end());
		std::cout << "l2: ";
		showIntList(l2);

		//用标准库的sort函数的结果来进行测试验证
		assert(l1 == l2);
	}

	if (true)
	{
		auto l1 = generateIntList();
		auto l2 = l1;
		std::cout << "heapSort>>>>" << '\n';
		std::cout << "before: ";
		showIntList(l1);

		heapSort(l1);
		std::cout << "l1: ";
		showIntList(l1);

		std::sort(l2.begin(), l2.end());
		std::cout << "l2: ";
		showIntList(l2);

		//用标准库的sort函数的结果来进行测试验证
		assert(l1 == l2);
	}


	if (true)
	{
		auto l1 = generateIntList();
		auto l2 = l1;
		std::cout << "mergSort>>>>" << '\n';
		std::cout << "before: ";
		showIntList(l1);

		mergSort(l1);
		std::cout << "l1: ";
		showIntList(l1);

		std::sort(l2.begin(), l2.end());
		std::cout << "l2: ";
		showIntList(l2);

		//用标准库的sort函数的结果来进行测试验证
		assert(l1 == l2);
	}

	if (true)
	{
		auto l1 = generateIntList(30);
		auto l2 = l1;
		std::cout << "quickSort>>>>" << '\n';
		std::cout << "before: ";
		showIntList(l1);

		quickSort(l1, 0, l1.size() - 1);
		std::cout << "l1: ";
		showIntList(l1);

		std::sort(l2.begin(), l2.end());
		std::cout << "l2: ";
		showIntList(l2);

		//用标准库的sort函数的结果来进行测试验证
		assert(l1 == l2);
	}
}

© 著作权归作者所有

共有 人打赏支持
能东棍
粉丝 7
博文 34
码字总数 25265
作品 0
南京
程序员
笨办法学 Python · 续 练习 16:冒泡、快速和归并排序

练习 16:冒泡、快速和归并排序 原文:Exercise 16: Bubble, Quick, and Merge Sort 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 你现在将尝试为你的数据结构实现排序算法。对于这...

apachecn_飞龙
2017/08/07
0
0
Python大牛的必学成长之路(20个经典学习资料)

想要成为Python大师,首先要从最基础知识开始学起,了解掌握Python最基础的知识点,编程意识从无都有,才能在Python 的道路上走得更远。 第一章 python基础 3课时 1小时5分钟 1、python 入门...

让往事随风
2015/12/23
26
0
复杂性思维中文第二版 附录 A、算法分析

附录 A、算法分析 原文:Appendix A Analysis of algorithms 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 部分参考了《Think Python 2e 中译本 第二十一章:算法分析》 算法分析 ...

wizardforcel
04/13
0
0
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
刚收到了Facebook的Offer,我是这样为面试做准备的?

作者|Andyy Hope 译者|郝鹏程 编辑|moomoo 我刚刚在硅谷的科技公司完成了7次现场面试,我收到了来自Facebook的软件工程师的职位Offer。下面分享一下我是怎么为面试做准备的,以及我在这个...

micf435p6d221ssdld2
2017/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

谷歌 Fuchsia 上手体验,将取代Android/win10

在手机市场领域,Google表现很抢眼,毫无疑问,Android 至今在移动操作系统的市场份额占据绝对领先地位,但是 Android 仍然存在不少问题,碎片化问题严重,在平板以及大屏幕设备上表现糟糕,...

linux-tao
21分钟前
1
0
List、Array与ArrayList

数组在内存中是连续存储的,所以它的索引速度很快,而且赋值和修改元素也非常快,比如: string[] s=new string[3];//赋值 s[0]="a"; s[1]="b"; s[2]="c";//修改 s[1]="b1"; 但是数组...

shimmerkaiye
24分钟前
0
0
Linux 的Lnmp环境下为mysql添加环境变量

一.问题 在Linux 安装完Lnmp 环境后 , 连接Mysql 告诉没有这条命令 mysql -uroot -p 命令失效 因为是源码安装的,所以会出现这样的的原因 。集成环境是不会出现的。 其实很简单,只需要给m...

15834278076
26分钟前
3
0
apolloxlua include函数

include函数不是单独使用的函数, 他并不是标准库的一部分, 你可以使用include函数将某个后缀为 .aop的文档包含到你的文档流中。 因为include是单独处理流, 所以不会在主处理流程中有所表示...

钟元OSS
29分钟前
0
0
【转载分享】做一名较真的工程师

近些年与我共事过的同事,一定知道我至今仍有一个较真的性格。我会:指出同事所写代码的不当命名问题(并帮助改进);指出同事所写文档中的逻辑混乱问题(并辅以修订);指出同事所写PPT中乱...

HellerZhang
31分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部