桶排序

核心代码
  1 void InsertSort(Bucket *pHead)
  2 {
  3     Bucket *pFirst = NULL;
  4     Bucket *pSecond = NULL;
  5     int temp;
  6 
  7     assert(pHead != NULL);
  8 
  9     pFirst = pHead;
 10     pSecond = pHead->pNext;
 11 
 12     while(pSecond)
 13     {
 14         //有序数组最后一个
 15         pFirst = pSecond->pPre;
 16         //无序数组的第一个
 17         temp = pSecond->nValue;
 18 
 19         //将无序数组元素依次插入有序数组
 20         while(pFirst!=NULL && temp<pFirst->nValue)
 21         {
 22             pFirst->pNext->nValue = pFirst->nValue;
 23             pFirst = pFirst->pPre;
 24         }
 25 
 26         //将元素放入对应位置
 27         if(NULL == pFirst)
 28         {
 29             pHead->nValue = temp;
 30         }
 31         else
 32         {
 33             pFirst->pNext->nValue = temp;
 34         }
 35 
 36         pSecond = pSecond->pNext;
 37     }
 38 }
 39 
 40 void BucketSort(int arr[], int len)
 41 {
 42     int nMax;
 43     int nMin;
 44     int i;
 45     int nTemp;
 46     int nCount;
 47     int nMaxIndex;
 48     int nMinIndex;
 49     Bucket **pBucket = NULL;
 50     int nIndex;
 51     Bucket *pTemp = NULL;
 52     Bucket *pDel = NULL;
 53 
 54     assert(arr!=NULL && len>0);
 55 
 56     nMax = arr[0];
 57     nMin = arr[0];
 58     //找最大值  最小值
 59     for(i=1; i<len; ++i)
 60     {
 61         if(arr[i] > nMax)
 62         {
 63             nMax = arr[i];
 64         }
 65         if(arr[i] < nMin)
 66         {
 67             nMin = arr[i];
 68         }
 69     }
 70 
 71     //计算数据位数
 72     nTemp = nMax;
 73     nCount = 0;
 74     while(nTemp)
 75     {
 76         nTemp /= 10;
 77         ++nCount;
 78     }
 79 
 80     //求被除基数
 81     nTemp = 1;
 82     while(nCount > 1)
 83     {
 84         nTemp *= 10;
 85         --nCount;
 86     }
 87 
 88     //拿到最高位
 89     nMaxIndex = nMax/nTemp%10;
 90     nMinIndex = nMin/nTemp%10;
 91 
 92     //根据最大值和最小值高位来开辟桶的个数
 93     pBucket = (Bucket **)malloc(sizeof(Bucket *)*(nMaxIndex-nMinIndex+1));
 94 
 95     //桶清空
 96     memset(pBucket, 0, sizeof(Bucket *)*(nMaxIndex-nMinIndex+1));
 97 
 98     //各元素如桶
 99     for(i=0; i<len; ++i)
100     {
101         nIndex = arr[i]/nTemp%10;
102 
103         //新节点开辟空间
104         pTemp = (Bucket *)malloc(sizeof(Bucket));
105         pTemp->nValue = arr[i];
106         pTemp->pPre = NULL;
107 
108         //头添加
109         //新来节点的下一个是原来的头
110         //原来的头的前一个是新来的节点
111         pTemp->pNext = pBucket[nIndex];
112         if(pBucket[nIndex] != NULL)
113         {
114             pBucket[nIndex]->pPre = pTemp;
115         }
116 
117         pBucket[nIndex] = pTemp;
118     }
119 
120     //各桶内进行排序
121     for(i=0; i<nMaxIndex-nMinIndex+1; ++i)
122     {
123         InsertSort(pBucket[nIndex]);
124     }
125 
126     //桶内元素放回原数组
127     nTemp = 0;
128     for(i=0; i<nMaxIndex-nMinIndex+1; ++i)
129     {
130         pTemp = pBucket[i];
131         while(pTemp)
132         {
133             arr[nTemp] = pTemp->nValue;
134             ++nTemp;
135             pTemp = pTemp->pNext;
136         }
137     }
138 
139     //释放空间
140     for(i=0; i<nMaxIndex-nMinIndex+1; ++i)
141     {
142         pTemp = pBucket[i];
143         while(pTemp)
144         {
145             pDel = pTemp;
146             pTemp = pTemp->pNext;
147             free(pDel);
148             pDel = NULL;
149         }
150     }
151 }