基于模板类的排序算法（冒泡排序，选择排序）

2016-11-15
#Algorithm

版权声明:本文为作者原创文章，可以随意转载，但必须在明确位置表明出处！！！

最近想整理一些基本的排序算法，此次整理排序算法会用模板类的方式提供，以便方便处理各种数据类型的排序，包括对象数组排序，结构体数组排序等。项目创建在git上，地址：https://github.com/Gavinxyj/Algorithm,欢迎随时交流。

今天整理一下最基本的两个排序算法，冒泡排序，选择排序

冒泡排序

故名思意就是水中的泡越大，上到水面的速度越慢，所以最大的水泡最后上来，这样就形成了一个有序序列了。

  • 算法原理：

  1. 比较相邻两个数的大小，并交换位置，如果是按升序排序那么第一趟排序的结果是最大的数已排在系列末尾了。
  2. 针对所有的相邻元素重复以上操作，除了最后一个元素（因为每趟排序完最大的元素都排到末尾了）。
  3. 对剩余未排好序的数据重复以上操作，知道没有任何一对数据需要处理为止

  • 稳定性：

    冒泡排序算法是稳定的排序算法，因为每一次比较都是相邻的两个数比较，如果两个数相当显然它们不会交换位子。

  • 时间复杂度：

  1. 最好的情况是给定的序列已经是有序的了，两两比较的时候不再需要交换位置所以它的最好时间复杂度是O(n)。
  2. 最坏的情况是给定的序列是反序的，那么两两比较的时候每次都需要交换位置所以他的最坏时间复杂度是O(n^2)

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class T>
void Algorihm<T>::bubbleSort(T *array, std::size_t nLen, int (*Compare)(const T *, const T *))
{
		if(0 == *array || 0 == nLen) return;
		
		bool bFlag = true; //这里考虑如果待排序列是有序的则直接退出循环
		for(int nLoop = 0; nLoop < nLen -1; nLoop ++)
		{		
			
			for(int index = 0; index < nLen - 1 - nLoop; index ++)
			{
					if(Compare(&array[index], &array[index + 1]) > 0)
					{
						T temp = array[index];
						array[index] = array[index + 1];
						array[index + 1]  = temp;	
						bFlag = false;
					}
			}	
		
			if(bFlag) break;
		}	
}

选择排序

  • 算法原理：

    每一次从待排序的数据中选出最大或最小的元素存放到序列的起始位置，知道全部数据元素排完

  • 稳定性

    选择排序算法是不稳定的排序算法，比如如下序列：9，9，6，第一次排序的结果就是9和6交换了，第一个位置的9变成了第三个位置了，当再次去排序的时候第二个9和第三个9不会再交换位置了，它们两个数的位置已经发生了改变，所以它是不稳定排序算法

  • 时间复杂度

    最好最坏的情况执行n(n-1)/2次比较，所以它的时间复杂度为O(n^2)

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class T>
void Algorihm<T>::selectionSort(T *array, std::size_t length, int (*Compare)(const T *, const T *))
{
		if(0 == *array || 0 == length) return;
		
		for(int nLoop = 0; nLoop < length - 1; nLoop ++)
		{
				int minKey = nLoop;
				
				for(int index = nLoop + 1; index < length; index ++)
				{
					  if(Compare(&array[minKey], &array[index]) > 0)
						{
							minKey = index;
						}
				}
				
				if(minKey != nLoop)
				{
					T temp = array[minKey];
					array[minKey] = array[nLoop];
					array[nLoop]	= temp;
				}
		}
}

调用方式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int compare(const int* a, const int *b)
{
	return *a - *b;
}
int main()
{
	int a[10] = {1,2,3,4,5,6,7,8,9,10};
	Algorihm<int>algorihm;
	
	algorihm.bubbleSort(a, 10, compare);
	
	for(int index =0; index < 10; index ++)
	{
			std::cout << a[index] << "\t";
	}
	std::cout << "\n";
	return 0;
}

如需要完整的文件，可以访问我上面的项目地址

推荐我的微信公众号：爱做饭的老谢

上一篇：如何编写一个漂亮的makefile
下一篇：基于模板类的排序算法（快速排序，插入排序）