排序算法 之 桶排序

原文地址http://www.cnblogs.com/liukemng/p/3724051.html

桶排序是一种效率很高的排序算法，它的时间复杂度为O(n)，但桶排序有一定的限制，只有当待排序序列的元素为0到某一确定取值范围的整数时才适用，典型的例子比如成绩的排序等。

算法思想：

设待排序序列的元素取值范围为0到m，则我们新建一个大小为m+1的临时数组并把初始值都设为0，遍历待排序序列，把待排序序列中元素的值作为临时数组的下标，找出临时数组中对应该下标的元素使之+1；然后遍历临时数组，把临时数组中元素大于0的下标作为值按次序依次填入待排序数组，元素的值作为重复填入该下标的次数，遍历完成则排序结束序列有序。

代码实现：

/// <summary>/// 桶排序/// </summary>/// <param name="intArray"></param>/// <param name="max"></param>public static void BucketSort(int[] intArray, int max) {    //声明一个长度为max+1的数组，并把数组中的元素全部初始化为0    int[] tempArray = Enumerable.Repeat(0, max+1).ToArray();    for (int i = 0; i < intArray.Length; i++)        tempArray[intArray[i]] += 1;//将tempArray下标中等于intArray[i]的元素+1    int insertIndex = 0;    for (int j = 0; j < tempArray.Length; j++)    {        for (int k = 0; k < tempArray[j]; k++)            intArray[insertIndex++] = j;//将排序后的元素插入数组tempArray的下标即元素的值    }}
以上就是桶排序的内容。