基數(shù)排序與基數(shù)排序是兩種非比較型排序。

10年的紅寺堡網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整紅寺堡建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“紅寺堡網(wǎng)站設(shè)計(jì)”,“紅寺堡網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

計(jì)數(shù)排序：

//************計(jì)數(shù)排序*********
//先大-最小+1得到開辟空間數(shù)，開辟空間str，在遍歷原數(shù)據(jù)arr在str相應(yīng)位置計(jì)數(shù)，再遍歷str將值寫到原arr中
//適用在密集型數(shù)據(jù)， 無重復(fù)最優(yōu)可轉(zhuǎn)化為位圖
//時(shí)間復(fù)雜度O(N),空間復(fù)雜度O(大數(shù)-最小數(shù)+1)

//設(shè)數(shù)組元素非負(fù)
void CountingSort(int *a, size_t size)
{
 size_t i = 0, j = 0;
 int max = a[0], min = a[0];
 size_t space = 0;
 for (i = 1; i < size; i++)
 {
  if (max < a[i])
  {
   max = a[i];
  }
  if (min > a[i])
  {
   min = a[i];
  }
 }
 space = max - min + 1;
 //str相應(yīng)位置記錄a中個(gè)數(shù)據(jù)的次數(shù)
 int *str = new int[space]();
 for (i = 0; i < size; i++)
 {
  str[a[i] - min] ++;
 }

 //寫回原數(shù)組a中
 for (i = 0, j = 0; i < space, j < size; i++)
 {
  while (str[i]-- > 0)
  {
   a[j++] = i + min;
  }

 }
}

基數(shù)排序：

//***********基數(shù)排序**************
//采用先排低位，在排高位
//時(shí)間復(fù)雜度O(位數(shù)) 空間復(fù)雜度O(N)

//設(shè)數(shù)組元素非負(fù)
size_t GetMaxRadix(int *a, size_t size)//取數(shù)組中大值的位數(shù)
{
 assert(a != NULL);
 size_t i = 0;
 size_t num = 0;
 size_t count = 1;
 for (i = 0; i < size; i++)
 {
  while (a[i] / count>0)
  {
   count *= 10;
   num++;
  }
 }
 return num;
}


void LSDSort(int *a, size_t size)
{
 assert(a != NULL);
 int MaxRadix = GetMaxRadix(a, size);
 int count[10] = { 0 };//同一位上數(shù)字相等的數(shù)字個(gè)數(shù)
 int start[10] = { 0 };//按位上數(shù)字所對應(yīng)的起始位置
 int * bucket = new int[size];
 size_t i = 0;
 int num = 1;
 while (MaxRadix--)
 {
  memset(count, 0, sizeof(int) * 10);//count清零
  //按位排序
  
  for (i = 0; i < size;i++)//count[]
  {
   count[a[i] / num % 10]++;//取某一位上數(shù)字，在count相應(yīng)位置++
  }
  for (i = 0; i < 10; i++)//start[]
  {
   //跳過0 因?yàn)槠鹗嘉恢靡欢?
   if (i == 0)
   {
    start[i] = 0;
   }
   else
    start[i] = start[i - 1] + count[i - 1];
  }

  //寫到bucket[]中
  for (i = 0; i < size; i++)
  {
   bucket[start[a[i] / num % 10]++] = a[i];
  }
  //寫回a[]中
  for (i = 0; i < size; i++)
  {
   a[i] = bucket[i];
  }
  num *= 10;
 }

}

test:

 int a5[] = { 5, 24, 35, 54, 72, 81, 75, 6, 9, 56, 114, 30, 5 };
 int a6[] = { 5, 24, 35, 54, 72, 81, 75, 6, 9, 56, 114, 30, 5 };

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁標(biāo)題：基數(shù)排序與基數(shù)排序-創(chuàng)新互聯(lián)
本文來源：http://weahome.cn/article/dsijgj.html