일반적인 정렬 알고리즘 6 - 계수 정렬

계수 정렬 의 사상 은 계수 정렬 법 은 간단 한 정렬 방법 이다. 이런 정렬 알고리즘 은 정렬 할 배열 을 정렬 하고 정렬 결 과 를 다른 배열 에 넣 는 것 이다.계수 정렬 알고리즘 은 정렬 대기 배열 의 모든 기록 에 대해 정렬 대기 배열 을 한 번 스 캔 하고 정렬 대기 배열 에 몇 개의 기록 값 이 이 기록 의 값 보다 작은 지 통계 합 니 다.특정한 기록 에 대해 통 계 된 계수 값 이 c 라 고 가정 하면 이 기록 은 새로운 질서 있 는 배열 에 적당 한 저장 위 치 는 c 이다.
다음은 C 언어 구현:

   1:  #include <malloc.h>

   2:  void count_sort(int a[], int length)

   3:  {

   4:      int* count = (int*)malloc( sizeof(int) * length);//               

   5:      int* des = (int*)malloc( sizeof(int) * length);  //         

   6:      

   7:      for (int i = 0; i < length; i++)

   8:      {

   9:          count[i] = 0;

  10:      }

  11:   

  12:      /*

  13:        A     Xi（0<=i<n），       Xj（0<=i<n）    ，    Xi       count[i]。

  14:        ，    ，            ，   Xi Xj   ，        Xj Xi 。

  15:                           。   A    Xi Xj    ，

  16:           Xj j     i<j<=n ，   Xi           。      ，  Xi > Xj ，

  17:       count[i] = count[i]+1；  ，count[j]=count[j]+1 。        ，count     

  18:        A       B      

  19:      */

  20:      for ( int i = 0; i < length; i++)

  21:      {

  22:          for (int j = i + 1; j < length; j++)

  23:          {

  24:              if (a[i] > a[j])

  25:              {

  26:                  count[i] = count[i] + 1;

  27:              }else{

  28:                  count[j] = count[j] + 1;

  29:              }

  30:          }

  31:      }

  32:   

  33:      for(int i = 0; i < length; i++){

  34:          des[count[i]] = a[i];

  35:      }

  36:   

  37:      for (int i = 0; i < length; i++)

  38:      {

  39:          a[i] = des[i];

  40:      }

  41:   

  42:      free(count);

  43:      free(des);

  44:   

  45:  }