基础排序算法

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
冒泡排序	O( n 2 n^{2} n2)	O( n 2 n^{2} n2)	O(1)	稳定
快速排序	O(n * l o g 2 n log_{2n} log2n​)	O( n 2 n^{2} n2)	O( l o g 2 n log_{2n} log2n​)	不稳定
插入排序	O( n 2 n^{2} n2)	O( n 2 n^{2} n2)	O(1)	稳定
希尔排序	O(n * l o g 2 n log_{2n} log2n​)	O( n 2 n^{2} n2)	O(1)	不稳定
选择排序	O( n 2 n^{2} n2)	O( n 2 n^{2} n2)	O(1)	数组不稳定、链表稳定
堆排序	O(n * l o g 2 n log_{2n} log2n​)	O(n * l o g 2 n log_{2n} log2n​)	O(1)	不稳定
归并排序	O(n * l o g 2 n log_{2n} log2n​)	O(n * l o g 2 n log_{2n} log2n​)	O(n)	稳定
计数排序	O(n + m)	O(n + m)	O(n + m)	稳定
桶排序	O(n)	O(n)	O(m)	稳定
基数排序	O(k * n)	O( n 2 n^{2} n2)		稳定

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
  

1. 冒泡排序 ( Bubble Sort )

• 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
• 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1.1 算法实现

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   

void bubbleSort(int a[], int n)
{
  int i,j;
  int key = 0;
  for(i = 0 ; i< n - 1; ++i) { 
    key = 0; //每次开始冒泡前，初始化 key 值为 0
    for(j = 0; j < n - i - 1; ++j) {
      if(a[j] > a[j+1]) {
        key=1;
        int tmp = a[j];  //交换
        a[j] = a[j+1];
        a[j+1] = tmp;
      }
    }
    if (key == 0) //当存在没有数据交换，就当前数据已经排好序
      break;
  }
}

1.2 测试

void PrintArr (int arr[], int n) //打印数组
{
  for (int i = 0; i < n; i++) {
    printf ("%d ",arr[i]);
  }
  printf ("n");
}

int main (int argc, char *argv[])
{
  int arr[] = {3, 44, 38, 5, 47, 15, 36, 26, 27};
  int len = sizeof(arr)/sizeof(arr[0]);
  int i;

  printf ("原数据:n");
  PrintArr (arr, len);

  bubbleSort (arr, len); //冒泡排序
  
  printf ("新数据:n");
  PrintArr (arr, len);
  
  return 0;
}

2. 快速排序 ( Quick Sort )

• 快速排序（Quicksort）是对冒泡排序算法的一种改进。
• 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2.1 算法实现

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

如上对无序表 {2,3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48} 进行快速排序：

1. 首先从表中选取一个记录的关键字作为分割点（称为“枢轴”或者支点，一般选择第一个关键字），例如选取 3；
2. 将表格中大于 3 的放置于 3 的右侧，小于3 的放置于 3 的左侧，假设完成后的无序表为：{2, 3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48} ；
3. 以3 为支点，将整个无序表分割成了两个部分，分别为 {2} 和 { 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48}，继续采用此种方法分别对两个子表进行排序；
4. 前部分子表只有 {2}，此部分只有一个值，不用排序；后部分子表以 44 为支点，排序后的子表为 {38, 5, 15, 36, 26, 27, 4, 19, 44, 47, 46, 50, 48}，以44分割为两个子表，{38, 5, 15, 36, 26, 27, 4, 19} 和 {47, 46, 50, 48}；

• 重复上述2、3步骤，直到全部排序完成 {2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50};

#define MAX 16
//单个记录的结构体
typedef struct {
    int key;
}SqNote;
//记录表的结构体
typedef struct {
    SqNote r[MAX];
    int length;
}SqList;
//此方法中，存储记录的数组中，下标为 0 的位置时空着的，不放任何记录，记录从下标为 1 处开始依次存放
int Partition(SqList *L,int low,int high)
{
  L->r[0]=L->r[low];
  int pivotkey=L->r[low].key;
  //直到两指针相遇，程序结束
  while (lowr[high].key>=pivotkey) {
      high--;
    }
    //直接将high指向的小于支点的记录移动到low指针的位置。
    L->r[low]=L->r[high];
    //low 指针右移，直至遇到比pivotkey值大的记录，指针停止移动
    while (lowr[low].key<=pivotkey) {
      low++;
    }
    //直接将low指向的大于支点的记录移动到high指针的位置
    L->r[high]=L->r[low];
  }
  //将支点添加到准确的位置
  L->r[low]=L->r[0];
  return low;
}

void QSort(SqList *L,int low,int high)
{
  if (lowlength);
}

2.2 测试

int main (void) 
{
  SqList * L = (SqList*)malloc(sizeof(SqList));
  int i;
  int arr[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

  L->length = sizeof (arr) / sizeof (arr[0]);
  for (i = 0; i < L->length; i++) {
    L->r[i+1].key = arr[i];
  }
  
  printf ("原始数据: n");
  for (i = 0; i < L->length; i++) {
    printf ("%d ",L->r[i+1].key);
  }

  QuickSort(L);
  
  printf ("n快速排序:n");
  for (i = 0; i < L->length; i++) {
    printf("%d ",L->r[i+1].key);
  }
  printf ("n");

  return 0;
}

3. 插入排序 ( Insertion Sort )

• 一般也被称为直接插入排序。
• 对于少量元素的排序，它是一个有效的算法 。
• 一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2] 。

3.1 算法实现

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
   

void InsertSort(int a[], int n) //直接插入排序函数
{
  for(int i= 1; i < n; i++){
    if(a[i] < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
      int j = i - 1;
      int x = a[i];
      while(j > -1 && x < a[j]){  //采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
        a[j+1] = a[j];
        j--;
      }
      a[j+1] = x;      //插入到正确位置
    }
    PrintArr(a,n,i);//打印每次排序后的结果
  }
}

3.2 测试

//自定义的输出函数
void PrintArr(int arr[], int n ,int i) 
{
  printf("第%d次: ",i);

  for(int j = 0; j < n; j++){
    printf("%d ",arr[j]);
  }
  
  printf("n");
}

int main(void)
{
  int arr[] = {3, 44, 38, 5, 44, 4, 19, 50};
  int len = sizeof(arr)/sizeof(arr[0]);
  
  printf ("原数据:n");
  PrintArr(arr, len, 0);
  printf ("n");

  InsertSort(arr, len);

  printf ("n新数据:n");
  PrintArr (arr, len, 0);

  return 0;
}

4. 希尔排序 ( Shell Sort )

• 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
• 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
• 希尔排序又叫缩小增量排序（Diminishing Increment Sort）。
  算法思想：

4.1 算法实现

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

void ShellSort(int arr[], int len) 
{
  int i, h, j;
  h = 1;
  while (h < len / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (i = h; i < len; i++) {
      for (j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
        swap(&arr[j], &arr[j - h]); //交换数组元素
      }
    }
    h = h / 3;
  }
}

4.2 测试

void swap(int *i, int *j) //数组元素交换
{
  *i = *i + *j;
  *j = *i - *j;
  *i = *i - *j;
}

int main (void)
{
  int arr[] = {84, 83, 88, 87, 61, 50, 70, 60, 80, 99};
  int len = sizeof(arr)/sizeof(arr[0]);
  int i;
  
  printf ("原数据:n");
  for (i = 0; i < len; i++) {
    printf ("%d ", arr[i]);
  }
  
  ShellSort(arr, len);

  printf ("n新数据:n");
  for (i = 0; i < len; i++) {
    printf ("%d ", arr[i]);
  }
  printf ("n");

  return 0;
}

5. 选择排序 ( Selection sort )

• 一种简单直观的排序算法。
• 工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

5.1 算法实现

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3. 以此类推，直到所有元素均排序完毕
   

void SelectSort(int arr[], int n) //n为数组元素个数
{
  //进行N-1轮选择
  for(int i = 0; i < n - 1; i++) {
    int min_index = i; 
    //找出第i小的数所在的位置
    for(int j = i + 1; j < n; j++) {
      if(arr[j] < arr[min_index]) {
        min_index = j;
      }
    }

    //将第i小的数，放在第i个位置；如果刚好，就不用交换
    if( i != min_index) {
      int temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
}

5.2 测试

void PrintArr (int arr[], int n) //打印数组
{
  for (int i = 0; i < n; i++) {
    printf ("%d ",arr[i]);
  }
  printf ("n");
}

int main (int argc, char *argv[])
{
  int arr[] = {2, 44, 5, 27, 3, 50, 48};
  int len = sizeof(arr)/sizeof(arr[0]);
  int i;

  printf ("原数据:n");
  PrintArr (arr, len);

  SelectSort (arr, len); //冒泡排序
  
  printf ("新数据:n");
  PrintArr (arr, len);
  
  return 0;
}

6. 堆排序 ( Heap Sort )

• 利用堆这种数据结构所设计的一种排序算法。
• 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

6.1 算法实现

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
   

void swap(int *i, int *j) //数组元素交换
{
  *i = *i + *j;
  *j = *i - *j;
  *i = *i - *j;
}
// 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。

void max_heapify(int arr[], int start, int end) {
	//建立父节点指标和子节点指标
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) { //若子节点在范围内才做比较
		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标，选择最大的
			son++;
		if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成，直接跳出函数
			return;
		else { //否则交换父子內容再继续子节点与孙节点比較
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(int arr[], int len) {
	//初始化，i从最后一个父节点开始调整
	for (int i = len / 2 - 1; i >= 0; i--)
		max_heapify(arr, i, len - 1);
	//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完成
	for (int i = len - 1; i > 0; i--) {
		swap(&arr[0], &arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}

6.2 测试

int main() {
	int arr[] = {91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22};
	int len = (int) sizeof(arr) / sizeof(*arr);
  int i;
 
  printf ("原数据:n");
  for (i = 0; i < len; i++) {
    printf ("%d ", arr[i]);
  }
  
	heap_sort(arr, len);
	
  printf ("n堆排序:n");
  for (i = 0; i < len; i++)
	  printf ("%d ", arr[i]);
	printf ("n");

	return 0;
}

7. 归并排序 ( Merge Sort)

• 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
• 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

7.1 算法实现

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1），然后进行两两合并，使 n 个有序表变为 ⌈n/2⌉ 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表），通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止。

#define  MAX 9
typedef struct{
    int key;
}SqNode;

typedef struct{
    SqNode r[MAX];
    int length;
}SqList;

//SR中的记录分成两部分：下标从 i 至 m 有序，从 m+1 至 n 也有序，此函数的功能是合二为一至TR数组中，使整个记录表有序
void Merge(SqNode SR[],SqNode TR[],int i,int m,int n)
{
  int j,k;
  //将SR数组中的两部分记录按照从小到大的顺序添加至TR数组中
  for (j=m+1,k=i; i<=m && j<=n; k++) {
    if (SR[i].keyr,L->r,1,L->length);
}

7.2 测试

int main()
{
  SqList * L=(SqList*)malloc(sizeof(SqList));
  int arr[] = {26, 27, 2, 46, 4, 19, 50, 48};
  int i;
  L->length = sizeof (arr) / sizeof (arr[0]);

  for (i = 0; i < L->length; i++) {
    L->r[i+1].key = arr[i];
  }

  printf ("原始数据: n");
  for (i = 0; i < L->length; i++) {
    printf ("%d ",L->r[i+1].key);
  }

  MergeSort(L);
  
  printf ("n归并排序:n");
  for (i = 0; i < L->length; i++) {
    printf("%d ",L->r[i+1].key);
  }
  printf ("n");

  return 0;
}

8. 计数排序 ( Counting Sort )

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法实现

1. 引入临时数组。
2. 对于元素i，计算出比i小的数，从而确定i的位置。
3. 计算重复，填充数组。

void count_sort_normal(int source_array[], int source_array_length)
{
  int i, j, k;

  // 定义临时数组，并且初始值为0
  int* tmp_group = (int*)malloc(sizeof(int) * source_array_length);

  // 目标元素在有序数组中的索引
  int target_index;

  // 目标元素的重复数
  int target_num;

  for (i = 0; i < source_array_length; i++) {
    target_index = 0;
    target_num = 0;

    for (j = 0; j < source_array_length; j++) {
      // 遍历得出目标元素的索引
      if (source_array[j] < source_array[i]) {
        target_index++;
      } else { // 计算重复数
          if (source_array[j] == source_array[i]) {
            target_num++;
          }
      }
    }

    // 对临时数组填充。当临时数组中的值为0时，说明未填充。当前元素为0时，无需填充。
    if (tmp_group[target_index] == 0 && source_array[i] !=0 ) {
      // 根据重复数填充
      for (k = 1; k <= target_num; k++) {
        tmp_group[target_index] = source_array[i];
        target_index++;
      }
    }
  }

  // 将原数组替换
  for (i = 0; i < source_array_length; i++) {
    source_array[i] = tmp_group[i];
  }
}

8.2 测试

void printf_arr(int arr[],int size) //打印数组
{
  int i = 0;
  for (; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf ("n");
}

int main (void)
{
  int arr[] = {2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2};
  int len = sizeof(arr) / sizeof(arr[0]);

  count_sort_normal (arr, len);

  printf_arr(arr, len);

  return 0;
}

9. 桶排序 ( Bucket Sort )

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法实现

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。
   

#define BUCKET_SIZE 10   // 单个桶存储大小

typedef struct node {
	int num;
	struct node *next;
}KeyNode;

int ReturnCount (int number)  //返回位数
{
	int count = 0; 

	while(number) {
			number = number / 10;//每次去掉数字最后一位
			count++;//循环一次计数器+1
	}
  
  return count;
}

void bucket_sort(int arr[], int size) 
{
	int i,j;

  //这是一个结构体指针的数组，数组内都是指针，还要分配内存，为结构体指针数组分配大小为BUCKET_SIZE的内存空间
	//使用二维指针表示二维数组，动态分配内存空间
	KeyNode **bucket_num = (KeyNode **)malloc(BUCKET_SIZE * sizeof(KeyNode*));    //分配行所用的空间

	for(i = 0; i < BUCKET_SIZE; i++) {
		bucket_num[i] = (KeyNode*)malloc(sizeof(KeyNode));      //为每个桶分配内存空间，分配列所用的空间
		bucket_num[i]->num = 0;   //记录当前桶中的数量，初始化桶中数量为0
		bucket_num[i]->next = NULL;   //为结构体中的结构体指针变量初始化为空
	}
	for(j = 0; j < size; j++) {
		KeyNode *node = (KeyNode *)malloc(sizeof(KeyNode));     //定义一个结构体变量的指针
		node->num = arr[j];    
		node->next = NULL;
		int index = ReturnCount (arr[j]);  //映射函数计算桶号
    printf ("数组[%d] 数据 %3d   放第%2d个桶n", j, arr[j], index);
		KeyNode *p = bucket_num[index];   //初始化P成为桶中数据链条的头指针
        //该桶中还没有数据
		if(p->num == 0) {
			bucket_num[index]->next = node;
			(bucket_num[index]->num)++;
		} else {
        //链表结构的插入排序
			  while(p->next != NULL && p->next->num <= node->num) {
				  p = p->next;
			  }	
			  node->next = p->next;
			  p->next = node;
			  (bucket_num[index]->num)++;
		}
	}
	//打印结果
	KeyNode * k = NULL;  //定义一个空的结构体指针用于储存输出结果
  int arr_size = 0;
	for(i = 0; i < BUCKET_SIZE; i++) { //赋值回原数组
    for(k = bucket_num[i]->next; k != NULL; k = k->next) {
      arr[arr_size++] = k->num;
    }			
  }		

}

9.2 测试

void PrintArr (int arr[], int n) //打印数组
{
  for (int i = 0; i < n; i++) {
    printf ("%d ",arr[i]);
  }
  printf ("nn");
}
 
int main()
{
	int arr[] = {66, 832, 1, 90, 7, 296, 3, 52};
	int size = sizeof(arr)/sizeof(arr[0]);    //计算数组长度
  
  printf ("原数据:n");
  PrintArr (arr, size);

	bucket_sort(arr, size);

  printf ("n新数据:n");
  PrintArr (arr, size);
  
  return 0;
}

10. 基数排序 ( Radix Sort )

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法实现

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）
   

int get_index(int num, int dec, int order)
{
  int i, j, n;
  int index;
  int div;
 
  
  for (i=dec; i>order; i--) {
    n = 1;
    for (j=0; j= 0; i--) {
    index = get_index(array[i], dec, order);  
    j = --num[index];  
    tmp[j] = array[i]; 
  }
 
  for (i = 0; i < len; i++)
    array[i] = tmp[i];  
 
  printf("the %d timen", order);
  PrintArr (array, len);

  printf("n");
 
  
  radix_sort(array, len, dec, order+1);
 
    return;
}

10.2 测试

void PrintArr (int arr[], int n) //打印数组
{
  for (int i = 0; i < n; i++) {
    printf ("%d ",arr[i]);
  }
  printf ("nn");
}

int main(int argc, char *argv[])
{
  int i;
  int array[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
 
  int len = sizeof (array) / sizeof (array[0]);  
  int dec = 2;   
  int order = 1; 
 
  printf("原数据:n");
  PrintArr (array, len);

  
  radix_sort(array, len, dec, order);
 
  printf("新数据:n");
  PrintArr (array, len);
 
  return 0;
}