文档章节

排序算法练习

能东棍
 能东棍
发布于 2017/05/19 17:43
字数 1083
阅读 13
收藏 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);
	}
}

© 著作权归作者所有

共有 人打赏支持
上一篇: 代码片段1
能东棍
粉丝 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
3013第一次面试总结

昨天趁着病假除去面试了一下。 对于面试。整体印象一般 周二收到的通知。没做任何准备。裸面。主要培养一下面试细胞。 一进公司规模一般。百人左右。前台态度一般。身兼多职。一下我的心就凉...

xffforever
2013/01/11
2.9K
39
维基百科上的算法和数据结构链接很强大

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

晨曦之光
2012/03/09
2.3K
1
复杂性思维中文第二版 附录 A、算法分析

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

wizardforcel
04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《阿里铁军》的读书笔记和读后感范文2600字

《阿里铁军》的读书笔记和读后感范文2600字: 在中国互联网,有一个流传很广的说法是,百度强在技术,腾讯强在产品,阿里强在运营。虽然发展到今天,已经不能再用这样简单的视角来看待这三个...

原创小博客
9分钟前
1
0
怎样实际项目中运用责任链模式

1 模式概要 1.1 简介 责任链模式为请求创建一个接收者对象链,每个接收者都包含对另一个接收者的引用,如果一个对象不能处理该请求,那么它会把请求传给下一个接收者,依此类推 责任链模式避...

小刀爱编程
24分钟前
1
0
【宇润日常疯测-004】JS 遍历数组如何快!快!快!

首先,我就是一后端全栈,对前端也只是会用罢了。闲的无聊来测测,不深究,只看表面,不喜勿喷! 遍历数组在写 JS 代码时候一定是经常用的,那么怎么遍历能达到最高效率呢,很多人一定没有测...

宇润
28分钟前
10
1
Linux系统如何定制History输出格式

Linux系统使用History命令来查看系统的运行记录,从而找出一些问题。但是History输出的数据中常常没有时间等信息。本文就来教大家Linux系统如何定制History输出格式。   具体方法如下 以r...

linuxprobe16
30分钟前
1
0
(一) pyhon 基础语法(数值 字符串 元组 列表 字典)

1、python的数据类型: 数值 字符串 列表 元组 字典; 数值类型包括; 整型(int) 长整型(long) 浮点型(float) 复数型 字符串; 可以通过type() 来查看是什么类型的; 注释:len()只支持 字符...

芬野de博客
30分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部