﻿ Binsort implementation 桶排序实现 - 鸿网互联

Binsort implementation 桶排序实现

Binsortisaclassicalimplementationoftheideathatsacrificingspacetoimproveefficiency. 本例实现桶排序，这是算法分析中一个经典的以空间换时间的案例。桶排序以被排序数组的数据作为新数组的下标，该数据出现的次数作为新数组的数据。新数组录入完毕后，依
Binsort is a classical implementation of the idea that sacrificing space to improve efficiency.

```#pragma once

#include<stdlib.h>
#include<stdio.h>
#include<array>

using namespace std;

class BinSort
{
public:
BinSort(int data[], int size)
{
datalist = data;
datasize = size;
int maxVal = datalist[0];
for (int index = 0; index < size; index++)
{
if (datalist[index] > maxVal)
maxVal = datalist[index];
}//end loop

binlist = new int[maxVal];
binsize = maxVal;

for (int index = 0; index < binsize; index++)
binlist[index] = 0;

performBinSort();
}//end cons

void performBinSort()
{
for (int index = 0; index < datasize; index++)
binlist[datalist[index] - 1] ++;

int dataIterator = 0;
for (int index = 0; index < binsize; index++)
{
if (binlist[index] != 0)
{
int datanum = binlist[index];
for (int i = 0; i < datanum; i++)
{
datalist[dataIterator] = index + 1;

////Testing code:
//printf("Data: %d\n", index);
//printf("Appeared: %d\n", datanum = binlist[index]);

dataIterator++;
}//store data into original data array.
}//end if: If there are data representing certain original elements.
}//end for

printf("\n");
}//end method: Perform bin sort

int * getSortedArray()
{
return datalist;
}//Get sorted array

~BinSort()
{
printf("Bin sort finishes!\n");
system("pause");
}//end distructor

private:
int datasize;
int binsize;
int * datalist;
int * binlist;
};//end class```
```#include "Binsort.h"

void printArray(int * dataarray, int size)
{
for (int index = 0; index < size; index++)
printf("%d ", dataarray[index]);
printf("\n");
}//end method: Print array.

int main()
{
int intarray[] = { 5, 3, 2, 8, 9, 11, 5, 6, 2, 1, 3, 14 };
printf("Array before sorting: \n");
printArray(intarray, 12);
BinSort sortarray(intarray, 12);
printf("Array after sorting: \n");
int * newarray = sortarray.getSortedArray();
printArray(newarray, 12);
system("pause");
return 0;
}```

<