基于模板类的排序算法（基数排序，堆排序）

2016-12-06
#Algorithm

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

基数排序

  • 算法的基本思想：

    基数排序的基本思想就是把每个待排序的数按照个位数，放入对应的“桶”中，然后把“桶”中的数依次取出按十位数放入“桶”中，然后按照百位…;知道最大位数排完序结束。

  • 算法原理：

  1. 找出待排序中的最大数确定需要排多少趟。
  2. 创建10个“桶”来装每个关键字的元素
  3. 将每隔待排元素按照个位依次放入对应的“桶”中。然后十位，百位，直到最大数的最高位排完为止。

  • 时间复杂度：

    最坏时间复杂度为O(d(r + n)),最好时间复杂度为O(d(n + rd))，平均复杂度为O(d(r + n ))。r表示关键字的基数，d表示长度，n表示关键字的个数

  • 稳定性：

    基数排序是稳定排序

算法实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template<class T>
void Algorithm<T>::radixSort(T *array, int nLength)
{
	if(0 == *array) return ;
	
	//先找出待排序中的最大元素来确定需要多少次排序
	T max = 0;	
	for(int nLoop = 0; nLoop < nLength; nLoop ++)
	{
		if(array[nLoop] > max)
		{
			max = array[nLoop];	
		}
	}	
	
	//获取最大值的位数
	int count = 0;
	while(true)
	{
		if(max == 0) break;
			
		max /= 10;
		count ++;
	}
	
	//创建10个桶分别来存放各个数字,因为每个数都是0-9组成的
	std::deque<T> tempDeque[10];
	
	for(int nLoop = 0; nLoop < count; nLoop ++)
	{
		for(int index = 0; index < nLength; index ++)
		{
			//将位数分别放到对应的桶中
			int nIndex = (array[index] / (int)pow(10, nLoop)) % 10;
			tempDeque[nIndex].push_back(array[index]);
		}
		//把此趟排好序的数据放回到原来数组中
		int nCount = 0;
		for(int index = 0; index < 10; index ++)
		{
			while(!tempDeque[index].empty())
			{
				array[nCount ++] = tempDeque[index].front();
				tempDeque[index].pop_front();
			}
		}
	}
}

堆排序

  • 算法的基本思想：

    堆排序的基本思想是先将一个无序的集合整理为一个大根堆或小根堆的完全二叉树，然后交换根节点和最后一个叶子节点元素，然后重新整理n-1个节点为大根堆或小根堆，重复此操作直到n为0结束。

  • 算法原理：

  1. 建堆，从nLength/2开是调整，一直到第一个节点。
  2. 调整堆，比较父节点和叶子节点的大小，若都小于叶子节点的大小则此结点无需调整，若不是则交换与该节点的左右叶子节点较小的一个元素
  3. 堆排序，交换根节点和nLength节点，按照上面步骤调整nLength - 1个节点，nLength – 直到nLength为0为止。

  • 时间复杂度：

    平均时间复杂度O(nlogn)

  • 稳定性：

    堆排序算法是不稳定的排序算法

  • 为了更好的演示堆排序的过程，下面给出图像演示

  • 原始堆

  • 建堆过程

  • 堆排序第一趟结果

  • 堆排序第二趟结果

  • 堆排序第三趟结果

  • 堆排序第四趟结果

  • 堆排序第五趟结果

  • 堆排序第六趟结果

  • 堆排序第七趟结果

  • 堆排序第八趟结果

  • 堆排序第九趟结果

  • 算法实现：

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    template<class T>
    void Algorithm<T>::heapSort(T *array, int nLength, int (*fCompare)(const T*, const T*))
    {
    	for(int nLoop = (nLength - 1) / 2 ; nLoop >= 0; nLoop --)
    	{
    		//只有左子树并小于父节点
    		int lChild = nLoop * 2 + 1;//左节点
    	  int rChild = lChild + 1;//右节点
    		if(lChild == nLength - 1 && fCompare(&array[lChild], &array[nLoop]) <= 0)
    		{
    			swap(array[lChild], array[nLoop]);	
    		}
    		//从子树开始整理
    		adjustHeap(array, nLength - 1, nLoop, fCompare);	
    	}
    	while(nLength > 0)
    	{
    		swap(array[nLength - 1], array[0]);		
    		nLength --;
    		adjustHeap(array, nLength, 0, fCompare);	
    	}
    }
    template<class T>
    void Algorithm<T>::adjustHeap(T *array, int nLength, T element, int (*fCompare)(const T*, const T*))
    {
    	int lChild = element * 2 + 1;//左节点
    	int rChild = lChild + 1;//右节点
    	
    	while(rChild < nLength)
    	{
    		//如果父节点小于它的左右孩子节点则改节点不需要整理
    		if(fCompare(&array[element], &array[lChild]) < 0 && fCompare(&array[element], &array[rChild]) < 0) return;	
    		//比较左右子树确定哪个子树最小
    		if(fCompare(&array[lChild], &array[rChild]) <= 0)
    		{
    			swap(array[element], array[lChild]);
    			element = lChild;
    		}
    		else
    		{
    			swap(array[element], array[rChild]);
    			element = rChild;	
    		}
    		lChild = element * 2 + 1;
    		rChild = lChild + 1;
    	}
    }

项目文件地址：https://github.com/Gavinxyj/Algorithm

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

上一篇：FTP网络协议C++实现）
下一篇：设计模式（简单工厂模型）