分享：我自己写的各种排序算法

AAA20090987 2010-03-27 04:55:36
很久没在算法区发过帖子了，就发个帖子，分享一下我自己写的各种排序算法吧，呵呵。
PS：下面的程序都是我自己写的，如果大家发现有BUG的话，请和我说一下，大家共同学习，共同进步。

#include <iostream>

#include <ctime>

const int SIZE = 100;

const int MAX = 1000;

using namespace std;



//交换数据

void Swap(int &a, int &b)

{

	int temp = a;

	a = b;

	b = temp;

}



//冒泡排序

void BubbleSort(int *arr, int size)

{

	int i, j;

	for(i=0;i<size-1;i++)

		for(j=size-1;j>i;j--)

			if(arr[j] < arr[j-1])

				Swap(arr[j], arr[j-1]);

}



//选择排序

void SelectionSort(int *arr, int size)

{

	int i, j, min;

	//找出从a[i]到a[size-1]的最小元素的位置

	for(i=0;i<size-1;i++)

	{

		min = i;

		for(j=i+1;j<size;j++)

			if(arr[min] > arr[j])

				min = j;

		//将a[i]与a[min]的数据交换

		Swap(arr[i], arr[min]);

	}

}



//插入排序

void InsertSort(int *arr, int size)

{

	int fOut, loc, temp;

	for(fOut=1;fOut<size;fOut++)

		if(arr[fOut] < arr[fOut-1])

		{

			temp = arr[fOut];

			loc = fOut;

			do

			{

				arr[loc] = arr[loc-1];

				loc--;

			}while(loc>0 && arr[loc-1]>temp);

			arr[loc] = temp;

		}

}



//快速排序

int Partition(int *arr, int first, int last)

{

	int i, small, x;

	//为了减少最差情况的出现频率而作的一种优化

	swap(arr[first], arr[ (first+last)/2 ]);

	x = arr[first];

	small = first;

	for(i=first+1;i<=last;i++)

		if(arr[i] < x)

		{

			small++;

			swap(arr[small], arr[i]);

		}

		swap(arr[first], arr[small]); 

		return small;

}



void RecQuick(int *arr, int first, int last)

{

	int pivotLoc;

	if(first < last)

	{

		pivotLoc = Partition(arr, first, last);

		RecQuick(arr, first, pivotLoc-1);

		RecQuick(arr, pivotLoc+1, last);

	}

}



void QuickSort(int *arr, int size)

{

	RecQuick(arr, 0, size-1);

}



//计数排序

void CountSort(int *arr, int size)

{

	int temp[MAX] = {0};

	int i, j;

	for(i=0;i<size;i++)

		temp[arr[i]]++;

	j = 0;

	for(i=0;i<MAX;i++)

	{

		while(0 != temp[i])

		{

			arr[j] = i;

			temp[i]--;

			j++;

		}

	}

}



//归并排序

void Merge(int *arr, int start, int mid, int end)

{

	int temp1[SIZE], temp2[SIZE];

	int n1, n2;

	int i, j, k;

	n1 = mid - start + 1;

	n2 = end - mid;

	//拷贝前半部分数组

	for(i=0;i<n1;i++)

		temp1[i] = arr[start + i];

	//拷贝后半部分数组

	for(i=0;i<n2;i++)

		temp2[i] = arr[mid + i + 1];

	//把后面的元素设置的很大

	temp1[n1] = temp2[n2] = INT_MAX;

	i = j = 0;

	// 逐个扫描两部分数组然后放到相应的位置去

	for(k=start;k<=end;k++)

	{

		if(temp1[i] <= temp2[j])

		{

			arr[k] = temp1[i];

			i++;

		}

		else

		{

			arr[k] = temp2[j];

			j++;

		}

	}

}



void RecMerge(int *arr, int start, int end)

{

	int i;

	if(start < end)

	{

		i = (start + end) / 2;

		RecMerge(arr, start, i);

		RecMerge(arr, i+1, end);

		Merge(arr, start, i, end);

	}

}



void MergeSort(int *arr, int size)

{

	RecMerge(arr, 0, size-1);

}



//堆排序

void Heapify(int *arr, int low, int high)

{

	int large;

	int temp = arr[low];

	large = 2 * low + 1;

	while(large <= high)

	{

		if(large<high && arr[large]<arr[large+1])

			large = large + 1;

		if(temp > arr[large])

			break;

		else

		{

			arr[low] = arr[large];

			low = large;

			large = 2 * low + 1;

		}

	}

	arr[low] = temp;

}



void BuildHeap(int *arr, int size)

{

	int i;

	for(i=size/2-1;i>=0;i--)

		Heapify(arr, i, size-1);

}



void HeapSort(int *arr, int size)

{

	int i;		//lastOfOrder

	BuildHeap(arr, size);

	for(i=size-1;i>=0;i--)

	{

		swap(arr[0], arr[i]);

		Heapify(arr, 0, i-1);

	}

}



//希尔排序

void ShellSort(int *arr, int size)

{

	int i, j, k, temp;

	//i为增量

	for(i=size/2;i>0;i/=2)

	{

		for(j=i;j<size;j+=i)

		{

			temp = arr[j];

			k = j;

			while(k-i>=0 && temp<arr[k-i])

			{

				arr[k] = arr[k-i];

				k -= i;

			}

			arr[k] = temp;

		}

	}

}



//输出数组里的数据

void Print(int *arr, int size)

{

	int i;

	for(i=0;i<size;i++)

	{

		printf("%6d ", arr[i]); 

		if(0 == (i+1) % 10)

			cout << endl;

	}

	cout << endl;

}



//主函数

//先随机选择100个整型数据放入数组中，并输出

//然后将其从小到大排序，并输出

int main()

{

	int arr[SIZE], i;

	cout << "The array is: " << endl;

	srand((unsigned)time(0));

	for(i=0;i<SIZE;i++)

		arr[i] = rand() % MAX;

	Print(arr, SIZE);



	//请选择其中一个排序算法，以运行该程序

	//BubbleSort(arr, SIZE);

	//SelectionSort(arr, SIZE);

	//CountSort(arr, SIZE);

	//InsertSort(arr, SIZE);

	//SelectionSort(arr, SIZE);

	//QuickSort(arr, SIZE);

	//MergeSort(arr, SIZE);

	//HeapSort(arr, SIZE);

	ShellSort(arr, SIZE);



	cout << "After sorting, the array is:" << endl;

	Print(arr, SIZE);

	return 0;

}
...全文
4966 109 打赏 收藏 转发到动态 举报
写回复
用AI写文章
109 条回复
切换为时间正序
请发表友善的回复…
发表回复
momotea0820 2010-09-25
  • 打赏
  • 举报
 回复
学习学习，谢谢分享
yzebo 2010-05-19
  • 打赏
  • 举报
 回复
学习了，不错~
email_zixuan 2010-04-06
  • 打赏
  • 举报
 回复
无聊，为啥不写成模板，应该看看STL，有空去贡献一下
invail 2010-04-06
  • 打赏
  • 举报
 回复
mark
qishengone 2010-04-06
  • 打赏
  • 举报
 回复
很好很强大
Sword1002 2010-04-05
  • 打赏
  • 举报
 回复
这些都快忘记了，感谢楼主的教科书般的整理，又回忆了一下。^_^，这些东西为什么在实际工作中用不到呢？看来学的还不够透彻啊，不能学以致用啊！！呵呵
董小尾 2010-04-05
  • 打赏
  • 举报
 回复
必须膜拜一下！！！！！！！！！！！！
两把扇子 2010-04-05
  • 打赏
  • 举报
 回复
看来是刚开始学习吧，加油！不错
路上企鹅 2010-04-05
  • 打赏
  • 举报
 回复
哈哈　　好　　　　知识
icePhone 2010-04-05
  • 打赏
  • 举报
 回复
[Quote=引用 20 楼 huxianzhuan 的回复:]

引用 18 楼 wxy824701942 的回复:
能让大家有所收获就行！


对，能有所收获就行，不过，Lz有没有想过去优化代码啊！
例如 你写的冒泡排序，好像就可以优化比较次数！
你写的应该是 每次冒泡都是把最小的，往上冒！
那如果你给的数是1 2 3 4 5 6 7 8 9（已经排好序的），那不是浪费了很多时间
我觉得可以这样
void BubbleSort(int……
[/Quote]

这就是算法适用性问题了，对于有序的，冒泡是最不合适的。算法很多，做项目的时候要酌情使用。
icePhone 2010-04-05
  • 打赏
  • 举报
 回复
很好~~
king870215 2010-04-05
  • 打赏
  • 举报
 回复
新手进来学习一下
angelsinklow 2010-04-04
  • 打赏
  • 举报
 回复
又有排序算法现世，速度来围观
baiyixiaoyaozl 2010-04-04
  • 打赏
  • 举报
 回复
一个个的都太强了，有谁能帮我写个生成直线的算法，计算机图形课程需要的，多写了！全球qq406992490
wwmcfly 2010-04-04
  • 打赏
  • 举报
 回复
初学者 前来学习
黄振龙 2010-04-04
  • 打赏
  • 举报
 回复
围观了
gaoan000 2010-04-03
  • 打赏
  • 举报
 回复
都是N人额
值得学习～
AAA20090987 2010-04-03
  • 打赏
  • 举报
 回复
[Quote=引用 84 楼 knate 的回复:]
哦,还以为楼主已经弃楼了.
这个是以前写的,大约估计和STL的sort差不多.可能要慢5%不到.
以现在的眼光来看,感觉大约能在大量随机数据情况下优化减少10%-25%左右的
但由于
一:使用模板
二:接口和STL不一样.
三:风格也不是很好
不值得在此基础上继续优化.

PS:不想吵架,如果不喜欢本人发言的,请自动忽略本人发言.
[/Quote]

谢谢knate的分享，你的水平比我高多了
我发这个帖子的目的在前面已经说了，不是为了引起争论的，而是让大家共同学习，共同进步的，呵呵。
knate 2010-04-03
  • 打赏
  • 举报
 回复 


// 随机排序.cpp : 定义控制台应用程序的入口点。

//选择排序随便写的.

//大约测试了一下,约10W数据为分界点.小量数据慢于STL sort

//实际应用会更细致些,分界点大约降到几十到几百左右,速度比这个快一些.

//但这些已经是几种排序的应用,和快速排序算法没什么关系了.

//测试数据 随机.

#include "stdafx.h"

#include <iostream>

#include <vector>

//#include <windows.h>

#include <ctime>

#include <algorithm>



using namespace std;



typedef int*  pVT;



typedef int	VT;

typedef unsigned int SIZE_T;

//typedef unsigned int SIZE_T;



inline void _swap_kn(VT & a,VT & b){

	VT _t;

	_t = a;

	a = b;

	b = _t;

}



inline void select_sort_kn(pVT  pSource,SIZE_T iOrg_Beg,SIZE_T iOrg_Nd){

	//sort(pSource + iOrg_Beg,pSource + iOrg_Nd);

	//return ;

	//	cout<<"原来"<<endl;

	//	for(SIZE_T x = iOrg_Beg;x < iOrg_Nd;++x)

	//		cout<<*(pSource + x)<<" ";

	//	cout<<endl;

	SIZE_T iBeg(iOrg_Beg),iNd(iOrg_Nd);

	for(;iBeg + 1 < iNd;){

		if(iNd <iBeg + 2)//只有1个元素

			return ;

		else{

			if(*(pSource + iNd - 1) < *(pSource + iBeg))//处理外层边界

				_swap_kn(*(pSource + iBeg),*(pSource + iNd - 1));



			for(SIZE_T iTemp_Beg(iBeg + 1),iTemp_Nd(iNd - 1);;){//iBeg,iTemp_Beg,iTemp_Nd - 1,iNd - 1

				if(iTemp_Nd  < iTemp_Beg + 1)//内存没有元素了

					break;

				else{

					if(*(pSource + iTemp_Nd - 1) < *(pSource + iTemp_Beg))

						_swap_kn(*(pSource + iTemp_Beg),*(pSource + iTemp_Nd - 1));

					if(*(pSource + iTemp_Beg) < *(pSource + iBeg))

						_swap_kn(*(pSource + iBeg),*(pSource + iTemp_Beg));

					if(*(pSource + iNd - 1) < *(pSource + iTemp_Nd - 1))

						_swap_kn(*(pSource + iTemp_Nd - 1),*(pSource + iNd - 1));

					++ iTemp_Beg;

					-- iTemp_Nd;

				}

			}

		}

		++ iBeg;

		-- iNd;

	}

	//	for(SIZE_T x = iOrg_Beg;x < iOrg_Nd;++x)

	//		cout<<*(pSource + x)<<" ";

	//	cout<<endl;

}



inline SIZE_T _divide_min(pVT  pSource,SIZE_T  iBeg,SIZE_T  iNd,VT iVal){

	for(;;){

		while(iBeg < iNd && *(pSource + iBeg) < iVal) ++ iBeg;

		while(iBeg < iNd && !(*(pSource + iNd - 1) < iVal)) -- iNd;

		if(iBeg + 1 < iNd){

			_swap_kn(*(pSource + iBeg ++),*(pSource + iNd -- - 1));

		}

		else

			break;

	}

return iBeg;

}

inline SIZE_T _divide_equal(pVT  pSource,SIZE_T  iBeg,SIZE_T  iNd,VT iVal){

	for(;;){

		while(iBeg < iNd && !(iVal < *(pSource + iBeg))) ++ iBeg;

		while(iBeg < iNd && iVal < *(pSource + iNd - 1)) -- iNd;

		if(iBeg + 1 < iNd){

			_swap_kn(*(pSource + iBeg ++ ),*(pSource + iNd -- - 1));

		}

		else

			break;

	}

return iBeg;

}



inline void sort_kn(pVT  pSource,SIZE_T iOrg_Beg,SIZE_T iOrg_Nd){

	//if(iOrg_Nd < iOrg_Beg + 2)

	//	return ;//无效数据,返回

	if(iOrg_Nd <iOrg_Beg + 32){//看资料,

			select_sort_kn(pSource,iOrg_Beg,iOrg_Nd);

			return ;

		}

	VT iFirst_Val = *(pSource + iOrg_Beg + rand() %(iOrg_Nd - iOrg_Beg));

//	cout<<"原来"<<endl;

//	for(SIZE_T x = iOrg_Beg;x < iOrg_Nd;++x)

//		cout<<*(pSource + x)<<" ";

//	cout<<endl;

	SIZE_T iMin_Nd =_divide_min(pSource,iOrg_Beg,iOrg_Nd,iFirst_Val);	

	//cout<<"iFirst_Val "<<iFirst_Val<<endl;

	//for(SIZE_T x = iOrg_Beg;x < iOrg_Nd;++x)

	//	cout<<*(pSource + x)<<" ";

	//cout<<endl;



	VT iSecond_Val = *(pSource+ iMin_Nd + rand() %(iOrg_Nd - iMin_Nd));

	SIZE_T iMax_Beg;



	if(iFirst_Val == iSecond_Val){

		iMax_Beg = _divide_equal(pSource,iMin_Nd,iOrg_Nd,iSecond_Val);	

	}

	else

		iMax_Beg = _divide_min(pSource,iMin_Nd,iOrg_Nd,iSecond_Val);	



	//cout<<"iSecond_Val "<<iSecond_Val<<endl;

	//for(SIZE_T x = iOrg_Beg;x < iOrg_Nd;++x)

	//	cout<<*(pSource + x)<<" ";

//	cout<<endl;

	if(iFirst_Val != iSecond_Val)

		sort_kn(pSource,iMin_Nd,iMax_Beg);

	sort_kn(pSource,iOrg_Beg,iMin_Nd);

	sort_kn(pSource,iMax_Beg,iOrg_Nd);

}



void sort_kn(pVT  pSource,SIZE_T n){

	srand((unsigned int) time(NULL));

	sort_kn(pSource,0,n);

}

void sort_kn(pVT  pSource,pVT pNd){

	srand((unsigned int) time(NULL));

	sort_kn(pSource,0,pNd - pSource);

}

int _tmain(int argc, _TCHAR* argv[])

{



	//Sleep(10);

	srand((unsigned int) time(NULL));

	const unsigned int n = 1000000;

	const unsigned int N = 100000000;



	//cin >>n;

	vector<int> a;

	a.resize(n);



	int *b = new int[n];

	int *c = new int[n];

	//int *d = new int[n];



	for(unsigned int x = 0;x < n;++x)

		a[x] = rand();

	for(unsigned int x = 0;x < n;++x){

		b[x] = a[x];

		c[x] = a[x];

//		d[x] = a[x];

	}

	time_t t;

	t = clock();	

	for(unsigned int x = 0; x < N / n;++x){

		for(unsigned int i = 0; i < n;++i)

			b[i] = a[i];

	sort(b,b + n );

	}

	//sort(b.begin(),b.end());

	cout<<"STL sort花费时间"<<clock() - t<<endl;



	t = clock();

	//for(unsigned int x = 0;x < 100;++x)

	//sort(b,b+n);	

for(unsigned int x = 0; x < N / n;++x){

	for(unsigned int i = 0; i < n;++i)

		c[i] = a[i];

	sort_kn(c,c + n);

}

	cout<<"sort_kn花费时间"<<clock() - t<<endl;



	for(unsigned int x = 0;x < n;++x)

		if(b[x] !=c[x]){

			cout<<"算法不正确"<<endl;

			cout<<"STL sort"<<endl;

			for(unsigned int x = 0;x < n;++x)

				cout<<b[x]<<" ";

			cout<<endl;

			cout<<"测试程序"<<endl;

			for(unsigned int x = 0;x < n;++x)

				cout<<c[x]<<" ";

			cout<<endl;

			break;

		}

		delete [] b;

		delete [] c;

	//	delete [] d;

		return 0;

}
zhangyong20081204 2010-04-03
  • 打赏
  • 举报
 回复
只要能理解这些,自己能写出.也是很厉害的.
加载更多回复（89）
面试之排序算法
排序算法是我们面试被问到最多的基础算法，本课程详细介绍了七种排序算法，包括插入排序、选择排序、冒泡排序、谢尔排序、快速排序、堆积排序和二路并归排序。每种算法都详细介绍了核心思想、详细步骤、时间复杂度和...
排序算法：快速排序
概述 手写排序算法几乎是程序员面试必问的题目，大多数人都会选择写冒泡排序，如果此时你写的是其他改进过的排序算法，相信会让面试官眼前一亮。本文将介绍常见的排序算法中的“快速排序”。 基本思想 快速排序（QuickSort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是： 从要排序的数据中取一个数为“基准数”。 通过一趟排序将要排序的数据...
排序算法：插入排序（直接插入排序、希尔排序）
直接插入排序和希尔排序的详细实现过程以及图解和时间复杂度和各种排序算法的效率的测试，简单易上手，你也快来试试吧！
C语言排序算法（一）：冒泡排序
分享一下我对C语言中冒泡排序算法的学习和理解（裂开了，足足写了一天，自闭中…） 冒泡排序 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们的位置交换过来。走访数列重复地进行直到排序完成。因为越大（小）的元素经过交换会慢慢"浮"到数列的顶端（尾端），就如同碳酸饮料中的气泡一样，故名“冒泡排序”。 算法原理 以从大到小降序排列为例。 第一轮走访开始 ----> 比较相邻的元素- —> 如果第一个元素比第二个元素
php编写冒泡排序算法_PHP排序算法之冒泡排序(Bubble Sort)实现方法详解
本文实例讲述了PHP排序算法之冒泡排序(Bubble Sort)实现方法。分享给大家供大家参考，具体如下：基本思想：冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。最简单排序实现：我们先来看看在没有学习各种排序方法前经常使用的排序方法(至少我是这样。。。。)：//这里使用了类型提示(type hint) array，不熟悉或者不习惯的同学大...
数据结构与算法

33,007

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章