欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++計數(shù)排序詳解

 更新時間:2016年04月12日 12:01:17   投稿:hebedich  
計數(shù)排序的思想我們之前接觸過的例如:插入排序,歸并排序,快速排序,堆排序等都是基于集合元素之間的比較這一基本的思想,它們執(zhí)行的時間復雜度最優(yōu)是趨于O(nlgn),而計數(shù)排序的運行機制不是基于集合元素之間的大小比較

計數(shù)排序不同于比較排序,是基于計數(shù)的方式,對于計數(shù)排序,假設每一個輸入都是介于0~k之間的整數(shù)。對于每一個輸入元素x,確定出小于x的元素的個數(shù)。假如有17個元素小于x,則x就屬于第18個輸出位置。
計數(shù)排序涉及到三個數(shù)組A[0…..length-1],length為數(shù)組A的長度;數(shù)組B與數(shù)組A長度相等,存放最終排序的結(jié)果;C[0…..K]存放A中每個元素的個數(shù),k為數(shù)組A中的最大值。

int count_k(int A[],int length),此函數(shù)為了確定數(shù)組A中最大的元素,用來確定C數(shù)組的長度。

int count_k(int A[],int length)
{
  int j,max;
  max = A[0];

  for(j=1;j<=length-1;j++)
  {
    if(A[j]>=max)
      max = A[j];
  }

  return max;
}

計數(shù)排序的實現(xiàn):

void count_sort(int A[],int B[],int k)
{
  int *C = (int *)malloc((k+1) * sizeof(int));
  int i,j;
  for(i=0;i<=k;i++)//初始化數(shù)組C
    C[i]=0;

  for(j=0;j<=length-1;j++)//計算A中元素的個數(shù)
    C[A[j]] = C[A[j]]+1;
  for(i=1;i<=k;i++)//計算小于等于C[i]的元素的個數(shù)
    C[i] = C[i] + C[i-1];
  for(j=length-1;j>=0;j--)
  {
    int k=C[A[j]]-1;
    B[k] = A[j];
    C[A[j]] = C[A[j]] - 1;

  }

  free(C);

}

count_sort(A,B,k);

k=5

for(j=0;j<=length-1;j++)//計算A中元素的個數(shù)    
C[A[j]] = C[A[j]]+1;

表示數(shù)組A中有2個0、0個1、2個2、3個3、0個4、1個5

  for(i=1;i<=k;i++)//計算小于等于C[i]的元素的個數(shù)    
C[i] = C[i] + C[i-1];

小于等于0的數(shù)有兩個,小于等于1的數(shù)有兩個、小于等于2的數(shù)有4個、小于等于3的有7個、小于等于4的有7個、小于等于5的有8個

for(j=length-1;j>=0;j--)
  {
    int k=C[A[j]]-1;
    B[k] = A[j];
    C[A[j]] = C[A[j]] - 1;

  }

for循環(huán)分析如下

j=7;A[j]=A[7]=3;C[A[j]]=C[3]=7;C[A[j]]-1=6;B[C[A[j]]-1]=B[6]=A[j]=3;C[A[j]]=C[A[j]]-1=6

 

j=6;A[j]=A[6]=0;C[A[j]]=C[0]=2;C[A[j]]-1=1;B[C[A[j]]-1]=B[1]=A[j]=0;C[A[j]]=C[A[j]]-1=1

 

j=5;A[j]=A[5]=3;C[A[j]]=C[3]=6;C[A[j]]-1=5;B[C[A[j]]-1]=B[5]=A[j]=3;C[A[j]]=C[A[j]]-1=5;

 

j=4;A[j]=A[4]=2;C[A[j]]=C[2]=4;C[A[j]]-1=3;B[C[A[j]]-1]=B[3]=A[j]=2;C[A[j]]=C[A[j]]-1=3;

 

j=3;A[j]=A[3]=0;C[A[j]]=C[0]=1;C[A[j]]-1=0;B[C[A[j]]-1]=B[0]=A[j]=0;C[A[j]]=C[A[j]]-1=0;

 

j=2;A[j]=A[2]=3;C[A[j]]=C[3]=5;C[A[j]]-1=4;B[C[A[j]]-1]=B[4]=A[j]=3;C[A[j]]=C[A[j]]-1=4;

 

j=1;A[j]=A[1]=5;C[A[j]]=C[5]=8;C[A[j]]-1=7;B[C[A[j]]-1]=B[7]=A[j]=5;C[A[j]]=C[A[j]]-1=7;

 

j=0;A[j]=A[0]=2;C[A[j]]=C[2]=3;C[A[j]]-1=2;B[C[A[j]]-1]=B[2]=A[j]=2;C[A[j]]=C[A[j]]-1=2;

 

計數(shù)排序的最后運行截圖

 

計數(shù)排序分析:j=length-1;j>=0;j–此處為倒序,是為了保證排序的穩(wěn)定性,這個在基數(shù)排序中有重要的作用。

您可能感興趣的文章:

相關文章

  • VS2010 boost標準庫開發(fā)環(huán)境安裝教程

    VS2010 boost標準庫開發(fā)環(huán)境安裝教程

    這篇文章主要為大家詳細介紹了VS2010 boost標準庫開發(fā)環(huán)境的安裝教程,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-04-04
  • C語言中volatile關鍵字的深入講解

    C語言中volatile關鍵字的深入講解

    在程序設計中,尤其是在C語言、C++、C#和Java語言中,使用volatile關鍵字聲明的變量或?qū)ο笸ǔ>哂信c優(yōu)化、多線程相關的特殊屬性,這篇文章主要給大家介紹了關于C語言volatile關鍵字的相關資料,需要的朋友可以參考下
    2021-07-07
  • C語言函數(shù)棧幀解析

    C語言函數(shù)棧幀解析

    下面小編就為大家?guī)硪黄獪\談C語言函數(shù)調(diào)用參數(shù)壓棧的相關問題。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-09-09
  • C語言如何寫類實現(xiàn)教程示例

    C語言如何寫類實現(xiàn)教程示例

    這篇文章主要為大家介紹了C語言如何寫類的實現(xiàn)教程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-04-04
  • ipv6實現(xiàn)udp編程示例

    ipv6實現(xiàn)udp編程示例

    這篇文章主要介紹了ipv6實現(xiàn)udp編程示例,需要的朋友可以參考下
    2014-03-03
  • C++基于遞歸和非遞歸算法求二叉樹鏡像的方法

    C++基于遞歸和非遞歸算法求二叉樹鏡像的方法

    這篇文章主要介紹了C++基于遞歸和非遞歸算法求二叉樹鏡像的方法,針對二叉樹遍歷結(jié)合實例形式分析了遞歸與非遞歸算法的實現(xiàn)與使用技巧,需要的朋友可以參考下
    2017-05-05
  • C語言文件操作詳解

    C語言文件操作詳解

    這篇文章主要介紹了C語言 文件操作解析詳解及實例代碼的相關資料,需要的朋友可以參考下,希望能夠給你帶來幫助
    2021-10-10
  • VScode + keil開發(fā)環(huán)境搭建安裝使用過程

    VScode + keil開發(fā)環(huán)境搭建安裝使用過程

    這篇文章主要介紹了VScode + keil開發(fā)環(huán)境搭建及安裝使用過程,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-07-07
  • C語言實現(xiàn)輸入ascii碼,輸出對應的字符方式

    C語言實現(xiàn)輸入ascii碼,輸出對應的字符方式

    這篇文章主要介紹了C語言實現(xiàn)輸入ascii碼,輸出對應的字符方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-01-01
  • MFC擴展DLL中導出類和對話框的實現(xiàn)方法

    MFC擴展DLL中導出類和對話框的實現(xiàn)方法

    這篇文章主要介紹了MFC擴展DLL中導出類和對話框的實現(xiàn)方法,詳細講述了實現(xiàn)擴展DLL中導出類和對話框的具體步驟與方法,具有不錯的實用價值,需要的朋友可以參考下
    2014-10-10

最新評論