文档章节

排序算法练习

能东棍
 能东棍
发布于 2017/05/19 17:43
字数 1083
阅读 12
收藏 0
点赞 0
评论 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
博文 33
码字总数 24258
作品 0
南京
程序员
笨办法学 Python · 续 练习 16:冒泡、快速和归并排序

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

apachecn_飞龙 ⋅ 2017/08/07 ⋅ 0

Python大牛的必学成长之路(20个经典学习资料)

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

让往事随风 ⋅ 2015/12/23 ⋅ 0

复杂性思维中文第二版 附录 A、算法分析

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

wizardforcel ⋅ 04/13 ⋅ 0

维基百科上的算法和数据结构链接很强大

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

晨曦之光 ⋅ 2012/03/09 ⋅ 1

Rxjs实践-各种排序算法排序过程的可视化展示

这几天学习下《算法》的排序章节,具体见对排序的总结,想着做点东西,能将各种排序算法的排序过程使用Rxjs通过可视化的方式展示出来,正好练系一下Rxjs的使用 本文不会太多介绍Rxjs的基本概念...

xiyuyizhi ⋅ 2017/10/27 ⋅ 0

刚收到了Facebook的Offer,我是这样为面试做准备的?

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

micf435p6d221ssdld2 ⋅ 2017/12/06 ⋅ 0

刚收到了Facebook的Offer,我是这样为面试做准备的

原文出处:Andyy Hope 译文出处:36kr 我刚刚在硅谷的科技公司完成了 7 次现场面试,我收到了来自 Facebook 的软件工程师的职位 Offer。下面分享一下我是怎么为面试做准备的,以及我在这个过...

Andyy Hope ⋅ 2017/11/27 ⋅ 0

经典排序之 冒泡排序

Author: bakari Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为冒泡排序。 冒泡排序是最古老的排序,我们最早...

chambai ⋅ 2012/08/11 ⋅ 0

字符串排序----排序算法的选择

对字符串的排序可以使用前面的通用排序算法,但有些专用的字符串排序算法将比通用排序算法效率更高,它们突破了NlogN的时间下界。 算法 是否稳定 原地排序 运行时间 额外空间 优势领域 低位优...

Superheros ⋅ 01/24 ⋅ 0

排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien ⋅ 2016/06/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Linux中的端口大全

1 被LANA定义的端口 端口 名称 描述 1 tcpmux TCP 端口服务多路复用 5 rje 远程作业入口 7 echo Echo 服务 9 discard 用于连接测试的空服务 11 systat 用于列举连接了的端口的系统状态 13 d...

寰宇01 ⋅ 21分钟前 ⋅ 0

Confluence 6 如何备份存储文件和页面信息

备份的 ZIP 文件包含有 entities.xml,这个 XML 文件包含有 Confluence 的所有页面内容和存储附件的目录。 备份 Zip 文件结构 页面的附件是存储在附件存储目录中的,通过页面和附件 ID 进行识...

honeymose ⋅ 24分钟前 ⋅ 0

【每天一个JQuery特效】根据状态确定是否滑入或滑出被选元素

主要效果: 本文主要采用slideToggle()方法实现以一行代码同时实现以展开或收缩的方式显示或隐藏被选元素。 主要代码如下: <!DOCTYPE html><html><head><meta charset="UTF-8">...

Rhymo-Wu ⋅ 28分钟前 ⋅ 0

度量.net framework 迁移到.net core的工作量

把现有的.net framework程序迁移到.net core上,是一个非常复杂的工作,特别是一些API在两个平台上还不能同时支持。两个类库的差异性,通过人工很难识别全。好在微软的工程师们考虑到了我们顾...

李朝强 ⋅ 33分钟前 ⋅ 0

请不要在“微服务”的狂热中迷失自我!

微服务在过去几年一直是一个非常热门的话题(附录1)。何为“微服务的疯狂”,举个例子: 众所周知,Netflix在DevOps上的表现非常棒。Netfix可以做微服务。因此:如果我做微服务,我也将非常...

harries ⋅ 35分钟前 ⋅ 0

oAuth2 升级Spring Cloud Finchley.RELEASE踩坑分享

背景 6.19号,spring团队发布了期待已久的 Spring Cloud Finchley.RELEASE 版本。 重要变化: 基于Spring Boot 2.0.X 不兼容 Spring Boot 1.5.X 期间踩过几个坑,分享出来给大伙,主要是关于...

冷冷gg ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 理发师小姐姐的魔法

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @冰冰棒- :分享田馥甄的单曲《My Love》 《My Love》- 田馥甄 手机党少年们想听歌,请使劲儿戳(这里) @Li-Wang :哎,头发又长了。。。又要...

小小编辑 ⋅ 今天 ⋅ 9

Kafka1.0.X_消费者API详解2

偏移量由消费者管理 kafka Consumer Api还提供了自己存储offset的功能,将offset和data做到原子性,可以让消费具有Exactly Once 的语义,比kafka默认的At-least Once更强大 消费者从指定分区...

特拉仔 ⋅ 今天 ⋅ 0

NEO智能合约之发布和升级(二)

接NEO智能合约之发布和升级(一),我们接下来说说智能合约的升级功能。 一 准备工作 合约的升级需要在合约内预先设置好升级接口,以方便在升级时调用。接下来我们对NEO智能合约之发布和升级...

红烧飞鱼 ⋅ 今天 ⋅ 0

个人博客的运营模式能否学习TMALL天猫质量为上?

心情随笔|个人博客的运营模式能否学习TMALL天猫质量为上? 中国的互联网已经发展了很多年了,记得在十年前,个人博客十分流行,大量的人都在写博客,而且质量还不错,很多高质量的文章都是在...

原创小博客 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部