文档章节

排序算法练习

能东棍
 能东棍
发布于 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
【程序猿必备】数据结构与算法精选面试题

有很多计算机科学技术专业的毕业生和程序员申请在Uber和Netflix这样的初创公司、谷歌和阿里巴巴这样的大公司以及Infosys或Luxsoft等以服务为基础的公司从事编程、编码和软件开发工作,但他们...

【方向】
10/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

WinDbg

参考来自:http://www.cnit.net.cn/?id=225 SRV*C:\Symbols*http://msdl.microsoft.com/download/symbols ctrl + d to open dump_file Microsoft (R) Windows Debugger Version 6.12.0002.633......

xueyuse0012
今天
2
0
OSChina 周五乱弹 —— 想不想把92年的萝莉退货

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @罗马的王:分享松澤由美的单曲《地球ぎ》 很久没看圣斗士星矢了 《地球ぎ》- 松澤由美 手机党少年们想听歌,请使劲儿戳(这里) @开源中国首...

小小编辑
今天
12
1
springBoot条件配置

本篇介绍下,如何通过springboot的条件配置,控制Bean的创建 介绍下开发环境 JDK版本1.8 springboot版本是1.5.2 开发工具为 intellij idea(2018.2) 开发环境为 15款MacBook Pro 前言 很多时候,...

贺小五
今天
1
0
javascript source map 的使用

之前发现VS.NET会为压缩的js文添加一个与文件名同名的.map文件,一直没有搞懂他是用来做什么的,直接删除掉运行时浏览器又会报错,后来google了一直才真正搞懂了这个小小的map文件背后的巨大...

粒子数反转
昨天
1
0
谈谈如何学Linux和它在如今社会的影响

昨天,还在农耕脑力社会,今天已经人工智能技术、大数据、信息技术的科技社会了,高速开展并迅速浸透到当今科技社会的各个方面,Linux日益成为人们信息时代的到来,更加考验我们对信息的处理程...

linux-tao
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部