桶排序的思想和基數排序有點類似,都要借助臨時空間.基數排序是先映射到大小為10的計數數組中,然後再映射到大小等于待排序數組長度的臨時數組中.
而桶排序就是直接整個足夠大的臨時數組,把待排序的元素全部映射過來.其索引為待排序元素數值.是以為了确定臨時數組的大小得先算出數組中最大數.
簡單桶排序
int GetMaxVal(int* arr, int len)
{
int maxVal = arr[0];
for(int i = 1; i < len; i++)
{
if(arr[i] > maxVal)
maxVal = arr[i];
}
return maxVal;
}
void SimpleBucketSort(int* arr, int len)
{
int tmpArrLen = GetMaxVal(arr , len) + 1; //因為數組索引是從0開始,是以數組得是最大數加1
int* tmpArr = new int[tmpArrLen];
int i, j;
for( i = 0; i < tmpArrLen; i++)
tmpArr[i] = -1; //把臨時數組的值全部賦予-1,如果賦予0的話待排序數組中有0值就不能排序了
for(i = 0; i < len; i++)
tmpArr[ arr[i] ] = arr[i];
for(i = 0, j = 0; i < tmpArrLen; i ++)
{
if( tmpArr[i] != -1)
{
arr[j] = tmpArr[i];
j++;
}
}
}
簡單桶排序的缺點很明顯
1.不能有重複的元素.
2.元素不能為負數.
對于第2點我們無能為力,但對于第一點可以改進下.
改進的桶排序
因為臨時數組的索引就是待排序數組元素的值了,是以臨時數組中可以不必再存儲元素的值了.此時先把臨時數組全部指派為0,當有元素映射過來時就加1,有重複有元素就大于1
void BucketSort(int* arr , int len)
{
int tmpArrLen = GetMaxVal(arr , len) + 1;
int* tmpArr = new int[tmpArrLen];
int i, j;
for( i = 0; i < tmpArrLen; i++)
tmpArr[i] = 0;
for(i = 0; i < len; i++)
tmpArr[ arr[i] ] ++;
for(i = 0, j = 0; i < tmpArrLen; i ++)
{
while( tmpArr[ i ] != 0)
{
arr[j ] = i;
j++;
tmpArr[i]--;
}
}
}