ctsort.c

//
//  ctsort.c
//  Algorithms - Counting sort
//
//  Created by YourtionGuo on 11/05/2017.
//  Copyright © 2017 Yourtion. All rights reserved.
//

#include <stdlib.h>
#include <string.h>

#include "sort.h"

#pragma mark - Public

int ctsort(int *data, int size, int k)
{
  int       *counts, *temp;
  int       i, j;

  /// 初始化 counts 数组空间
  if ((counts = (int *)malloc(k * sizeof(int))) == NULL)return -1;

  /// 初始化空间用于排序结果
  if ((temp = (int *)malloc(size * sizeof(int))) == NULL) return -1;

  /// 初始化 counts
  for (i = 0; i < k; i++) {
    counts[i] = 0;
  }

  /// 计算元素出现个数
  for (j = 0; j < size; j++)
    counts[data[j]] = counts[data[j]] + 1;

  /// 调整计数值，加上前一个元素出现次数
  for (i = 1; i < k; i++) {
    counts[i] = counts[i] + counts[i - 1];
  }

  /// 使用 counts 将元素放到对应位置
  for (j = size - 1; j >= 0; j--) {

    temp[counts[data[j]] - 1] = data[j];
    counts[data[j]] = counts[data[j]] - 1;
  }

  /// 将已排序数据放回
  memcpy(data, temp, size * sizeof(int));

  /// 销毁用于排序的临时空间
  free(counts);
  free(temp);
  
  return 0;
}