常见排序算法

         阅读(534)  2017-04-17 17:51:52

/*插入排序*/

#include <iostream>
using namespace std;

template <class T>
void SWAP(T &x, T &y)
{
	T t;
	t = x;
	x = y;
	y = t;
}

template <class T>
void Insert(T a[], int n, const T x)
{
	int i;
	for (i = n-1; i >= 0 && x < a[i]; i--)
	{
		a[i+1] = a[i];
	}
	a[i+1] = x;
}

template <class T>
void InsertionSort(T a[], int n)
{
	for (int i = 1; i < n; i++)
	{
		T t = a[i];
		Insert(a, i, t);
	}
}
/*及时终止的冒泡排序*/

#include "stdafx.h"
#include <iostream>
using namespace std;

template <class T>
void SWAP(T &x, T &y)
{
	T t;
	t = x;
	x = y;
	y = t;
}

template <class T>
bool Bubble(T a[], int n)
{
	bool isSwapped = false;

	for (int i = 0; i < n - 1; i++)
	{
		if (a[i] > a[i+1])
		{
			SWAP(a[i], a[i+1]);
			isSwapped = true;
		}
	}
	return isSwapped;
}

template <class T>
void BubbleSort(T a[], int n)
{
	for (int i = n; i > 1 && Bubble(a, i); i--);
}
/*终止不必要的选择排序*/

#include "stdafx.h"
#include <iostream>
using namespace std;

template <class T>
void SWAP(T &x, T &y)
{
	T t;
	t = x;
	x = y;
	y = t;
}

template<class T>
void SelectionSort(T a[], int n)
{
	bool sorted = false;

	for (int size = n; !sorted && (size > 1); size--)
	{
		int pos = 0;
		sorted = true;
		for (int i = 1; i < size; i++)
		{
			if (a[pos] <= a[i])
			{
				pos = i;
			}
			else
			{
				sorted = false;
			}
		}
		SWAP(a[pos], a[size-1]);
	}
}
// 快速排序

template <class T>
void SWAP(T &x, T &y)
{
	T t;
	t = x;
	x = y;
	y = t;
}

template <class T>
int partition(T a[], int lower, int upper)
{
	T pivot = a[lower]; // 注意这里不要写成了a[0]
	while (lower < upper)
	{
		while (lower < upper && a[upper] >= pivot) // 不要忘了加=
		{
			upper--;
		}
		SWAP(a[lower], a[upper]);

		while (lower < upper && a[lower] <= pivot)
		{
			lower++;
		}
		SWAP(a[lower], a[upper]);
	}

	return lower;
}

template <class T>
void quicksort(T a[], int lower, int upper)
{
	int flag;
	if (lower < upper)
	{
		flag = partition(a, lower, upper);
		quicksort(a, lower, flag - 1);
		quicksort(a, flag + 1, upper);
	}
}

2011-08-12

文章评论

Keep it simple,stupid
文章数
284
总访问量
263230
今日访问
143
最近评论

ningto : 请到next.ningto.com里发表评论。
tujiaw : 抱歉csdn code服务关闭了,这个代码我也找不到了
于淞 : 你好,这个文章的源码能分享一下吗,songsong9181@163.com,谢谢了 上面的写错了
于淞 : 你好,这个文章的源码能分享一下吗,838106303@163.com,谢谢了 上面的链接不能用了
tujiaw : 多谢多谢
essaypinglun college-paper.org : 很好的博客,赞赞
Folly : 这个实现有点奇怪,Qt为什么没有统一的比对方法。
过多s : alert("hello, world!")
tujiaw : 还不错哦
回到顶部