文章目录

• 一、什么是排序
• 二、冒泡排序
• • 解析冒泡排序
  • 代码实现
  • 冒泡排序优化
• 三、选择排序
• • 解析选择排序
  • 代码实现
• 四、插入排序
• • 解析插入排序
  • 代码实现
• 五、希尔排序
• • 解析希尔排序
  • 代码实现
• 六、归并排序
• • 解析归并排序
  • 代码实现
• 七、快速排序
• • 解析快速排序
  • 代码实现
• 八、堆排序
• • 解析堆排序
  • 代码实现
• 九、计数排序
• • 解析计数排序
  • 代码实现
• 十、桶排序
• • 解析桶排序
  • 代码实现
• 十一、基数排序
• • 解析基数排序
  • 代码实现

一、什么是排序

  排序就是将输入的数字按照从小到大的顺序进行排序。这里我们用柱形来表示数字，数字越大，柱形就越高。

  假设现在有如上图所示的输入数据，那么我们的目标就是将它们像下图一样，按从小到大的顺序从左边开始依次排列。

  如果只有8个数据，手动排序也能轻松完成，但如果有10000个、1000000个数据，排序就不那么容易了。这时，使用高效率的排序算法便是解决问题的关键。这就涉及到排序算法设计与使用了。
  排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、桶排序等。


 
 

二、冒泡排序

解析冒泡排序

  冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从左往右“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。

  在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。

  由于13>4，所以交换这两个数字。

  完成后，天平往左移动一个位置，比较两个数字的大小。此时5<13，所以需要交换。

  继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最右端。

  不断对数字进行交换，天平最终到达了最右边。通过这一系列操作，序列中最大的数字就会移动到最右端。

  最右边的数字已经归位。

  将天平移回最左边，然后重复之前的操作，直到天平到达最右边第2个位置为止。

  当天平到达最右端第2个位置，序列中第2大的数字也就到达了指定位置。

  将天平移回最左端，重复同样的操作直到所有数字都归位为止。

总结：
  在冒泡排序中，第 1 轮需要比较 n-1 次，第 2 轮需要比较 n-2 次…第 n-1 轮需要比较 1 次。因此，总的比较次数为 (n-1) + (n-2) + … + 1 ≈ n²/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
  不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据需要以大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度O(n²)。

代码实现

void bubble_sort(int arr[], int len) {
        for (int i = 0; i < len - 1; i++)
                for (int j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                int temp;
								temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
}

冒泡排序优化

冒泡排序的问题： 冒泡排序算法不管你是否有序，就直接循环比较就是啦！

  比如一个数组为：[ 1，2，3，4，5 ]，一个有序的数组，根本不需要排序，仍然进行双层循环将数据遍历一遍，这是完全没有必要的，浪费计算机资源。
  我们可以设定一个临时遍历来标记该数组是否有序，如果已经有序了就不需要排序了，直接结束即可。

void bubble_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i++){
    	int flag = 1;
        for (int j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                int temp;
				temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = 0;
            }
        if(flag)
        	break;
	}
}

三、选择排序

解析选择排序

  选择排序就是重复 “从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换” 这一操作的算法。在序列中寻找最小值时使用的是线性查找。
  选择排序的思路是这样的（以从小到大排序为例）：首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。


  使用线性查找在数据中寻找最小值，于是我们找到了最小值 1 （从第一个记录开始，逐个比较记录的关键字，找到最小值）。

  将最小值 1 与序列最左边的 7 进行交换，最小值 1 归位。不过，如果最小值已经在最左端，就不需要任何操作了！

  在余下的数据中继续寻找最小值。这次找到的是4。

  将数字4与左边第2个数字 13 进行交换，余下数字中最小值 4 归位。


  排序完成！
总结：
  选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较 n-1 个数字，第2轮需要比较 n-2 个数字……到第 n-1 轮的时候就只需要比较 1 个数字。因此，总的比较次数与冒泡排序的相同，都是 (n-1)+(n-2)+…+1 ≈ n²/2次。
  每轮中交换数字的次数最多为 1 次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O(n²)。
 
 

代码实现

void selection_sort(int arr[], int len){
    for (int i = 0 ; i < len - 1 ; i++){
        int min = i;
        for (int j = i + 1; j < len; j++)     //查询未排序的元素
            if (arr[j] < arr[min])    //找到目前最小值
            min = j;    //记录最小值
        int temp;    //做交换
        temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

四、插入排序

解析插入排序

  插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
  插入排序的思想和我们打扑克牌的时候一样，从牌堆例一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。


  首先，我们假设最左边的数字 7 已经完成排序，所以此时只有 7 是已归位的数字。

  接下来，从待排数字（未排序区域）中取出最左边的数字13，将它与左边已归位的数字进行比较。7<13，所以13不需要动，直接结束第2轮排序。

  接下来，从待排数字（未排序区域）中取出最左边的数字4，将它与左边已归位的数字进行比较。若左边的数字更大，就交换这两个数字。重复该操作，直到左边已归位的数字比取出的数字更小，或者取出的数字已经被移动整个序列的最左边为止。

  4<13，13向右移动！下一步将4与7进行比较。

  由于7>4，所以交换着两个数字。

  所以4也归位了，右边还有5个数字尚未排序。


总结：
  如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体说，就是第k轮需要 k-1 次。因此，在最糟糕的情况下，第2轮需要操作 1 次，第3轮操作 2 次……第 n 轮操作 n-1 次，所以时间复杂度和冒泡排序的一样，都为O(n²)。
  最好情况的时间复杂度是O(n)，最坏情况的时间复杂度是O(n²)。
 
 

代码实现

void insertion_sort(int arr[], int len){
    int key;
    for (int i=1;i<len;i++){
        key = arr[i];
        int j=i-1;
        while((j>=0) && (arr[j]>key)) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

五、希尔排序

解析希尔排序

  希尔排序这个名字，来源它的发明者希尔，也称作“缩小增量排序”，是插入排序的一种更高效的改进版本。
  希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

  希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
  将一个序列分成好几个序列，用一个数来表示：那个数称为增量。显然的是，增量是不断递减的(直到增量为1)。
  增量一般：{n/2,(n/2)/2…1}，每次增量都/2。


  分为四组：{ 7，8 }，{ 13，1 }，{ 4，11 }，{ 5，9 }

  将四组分别插入排序：{ 7，8 }，{ 1，13 }，{ 4，11 }，{ 5，9 }
  增量更新： 4 / 2 = 2

  增量为2。
  分为两组：{ 7，4，8，11 }，{ 1，5，13，9 }

  将两组分别插入排序：{ 4，7，8，11 }，{ 1，5，9，13 }
  增量更新： 2 / 2 = 1

  增量为1。
  分为两组：{ 4，1，7，5，8，9，11，13 }

总结：
时间复杂度情况如下：（n指待排序序列长度）

1. 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2. 最坏情况：O(nlog₂n)。
3. 渐进时间复杂度（平均时间复杂度）：O(nlog₂n)

代码实现

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)//增量 
        for (i = gap; i < len; i++) {//插入排序 
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

六、归并排序

解析归并排序

  归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列只有一个数据时），就对子序列进行归并。归并指的是吧两个排好的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体。




  分割完毕！接下来对分割后的元素进行合并。

  合并7和13，合并后的顺序为[ 7，13 ]。

  合并4和5，合并后的顺序为[ 4，5 ]。

  [ 7，13 ]和[ 4，5 ]合并，要先比较首位数字，再移动较小的数字。



  右半边也使用相同的方法。



总结：
  归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这行数据的两。
  从上图可以看出，每行数据量都是n，每行的运行时间都是O(n)。而将一个数据量为n的序列对半分割，可以分成 log₂n 行。因此，总的运行时间就是O(nlogn)。
 
 

代码实现

int min(int x, int y) {//比较大小，返回小的 
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {//归并排序 
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));//申请临时空间存放排序数组 
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {//归并排序的分割：1、2、4、8、16... 
        for (start = 0; start < len; start += seg * 2) {//行，一次循环跳一个归并 
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);//low:第一个序列的开始 mid:第一个序列的结束、第二个序列的开始 high:第二个序列的结束 
            int k = low;
            int start1 = low, end1 = mid;//第一个序列的标记开始和结束 
            int start2 = mid, end2 = high;//第二个序列的标记开始和结束 
            while (start1 < end1 && start2 < end2)//归并排序 
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;//数组交换 
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)//赋值 
            b[i] = a[i];
        b = a;
    }
    free(b);//释放临时空间 
}

七、快速排序

解析快速排序

  快速排序的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放左边，然后再对左边和右边的两组数分别选择出一个基准值，进行同样的比较移动，重复步骤，直到都变成单个元素，整个数组就成了有序的序列。

  首先，我们选一个基准值，一般我们选取中间的为基准值。
  从数组剩下的序列左右两边进行扫描，先从左往右找到一个大于等于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于等于基准值的元素，交换这两个元素的位置，重复上述步骤，直到左右两个指针相遇，再将基准值与左侧、右侧的数分别进行上述操作。

  左边扫描到7，右边扫描到1，交换。

  左边扫描到13，右边扫描到5，交换。

  该轮结束，数组分为两块。

  分为两块后，继续进行上述的操作。
  我们先看左边这块。


  继续分块。



  指针相遇继续分块。


  其他的也是类似的操作

总结：
  快速排序是一种“分治法”。它将原本的问题分成两个子问题(比基准值小的数和比基准值大的数)，然后再分别解决这两个问题。子问题，也就是子序列完成排序后，再像一开始说明的那样，把他们合并成一个序列，那么对原始序列的排序也就完成了。
  不过，解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。
  分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序的运行时间和归并排序的一样，都为O(nlogn)。和归并排序类似，将序列对半分割logn次之后，子序列里便只剩下一个数据，这时子序列的排序也就完成了。因此，如果像下图这样一行行地展现根据基准值分割序列的过程，那么总共会有logn行。
  每行中每个数字都需要和基准值比较大小，因此每行所需的运行时间为On)。由此可知，整体的时间复杂度为O(nlogn)o
  如果运气不好，每次都选择最小值作为基准值，那么每次都需要把其他数据移到基准值的右边，递归执行n行，运行时间也就成了O(n’)。这就相当于每次都选出最小值并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为O(nlogn,

代码实现

void quick_sort(int q[], int l, int r)//l起始下标，r结束下标 
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//x为基准值，去中间点 
    while (i < j)
    {
        do i ++ ; while (q[i] < x);//扫描大于基准值的数 
        do j -- ; while (q[j] > x);//扫描小于基准值的数 
        if (i < j) swap(q[i], q[j]);//交换q[i]和q[j] 
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

八、堆排序

解析堆排序

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

  数组是线性结构，我们构建堆一般如下图所示：节点下标为 n，它在左孩子为 2n+1，右孩子为 2n+2。

  开始排序。

  建堆。

  我们是从小到大排序，应该构建大顶堆。下面我们开始构建大顶堆。这系列操作属于初始化阶段。

  最后一个父节点为5，比较5与9，大顶堆需要交换。而无后续的孙节点，所以本次结束。

  下一个父节点为4，比较4、1、11，交换4与11而无后继的孙节点，结束.

  下一个父节点为13，比较13、9、8，无需交换。

  下一个父节点为7，比较7、13、11，交换7与13由于有孙节点，所以继续往下去维护大顶堆。

  延续下去的父节点为7,比较7、9、8，交换7与9由于有孙节点，所以继续下午维护大顶堆。

  延续下去的父节点为7,比较7、5,交换7与5无孙节点，所以结束。

  大顶堆的初始化结束，开始排序。

  使顶堆与已排序的前一个进行交换，在从堆顶进行维护大顶堆。

  由于交换会破坏大顶堆，所以我们需要对其进行维护。而我们只需要从堆顶进行自上而下的维护即可，而不会像初始化一样重新来一遍，因为交换只会破坏最上层的。

  父节点为：5，比较5，9，11，交换5和11有孙节点所以需要继续向下!

  父节点为:5，比较5，1，4，无需交换，结束本次维护！剩下的元素再次构成一个大顶堆。
  下面只需要重复上面的排序步骤，直到堆为空即可完成排序。

总结：
  堆排序一开始需要将n个数据存进堆里，所需时间为O(nlogn)。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于log₂n，所以插入1个数据所需要的时间为O(logn)o
  每轮取出最大的数据并重构堆所需要的时间为O(logn)。由于总共有n轮，所以重构后排序的时间也是O(nlogn)。因此，整体来看堆排序的时间复杂度为O(nlogn)。
  这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O(n²)都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

代码实现

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

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) {
    int i;
    // 初始化，i从最后一个父节点开始调整 
    for (i = len / 2 - 1; i >= 0; i--)//初始化构建顶堆过程 
        max_heapify(arr, i, len - 1);
    // 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

九、计数排序

解析计数排序

  计数排序是一种非基于比较的排序算法，我们之前介绍的各种排序算法几乎都是基于元素之间的比较来进行排序的，计数排序的时间复杂度为 O(n + m )，m 指的是数据量，说的简单点，计数排序算法的时间复杂度约等于 O(n)，快于任何比较型的排序算法，但是空间复杂度较高。
  计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

  这样排序就结束了！
总结：
  计数排序十分好理解，实现也简单，时间复杂度也十分优秀，且是稳定的。但是如果数据的范围较大，数据较为稀疏时，会导致需要消耗大量的空间，且很多空间可能用不上，空间复杂度较高。
  计数排序只适用于正整数并且取值范围相差不大的数组排序使用，它的排序的速度是非常快的。
 
 

代码实现

void counting_sort(int *a,int n){
	 //找出数组中的最大值
    int max = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    //初始化计数数组
    int arr[max+1];
    for(int i = 0;i < max+1;i++)
    	arr[i] = 0;

    //计数
    for (int i = 0; i < n; i++) {
        arr[a[i]]++;
        a[i] = 0;
    }

    //排序
    int index = 0;
    for (int i = 0; i < max+1; i++) {
        while (arr[i] > 0) {
            a[index++] = i;
            arr[i]--;
        }
    }
}

十、桶排序

解析桶排序

  桶排序可以看成是计数排序的升级版，它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。

  length：8
  （max-min）/（length）=1.5

  将桶划分好，向里面填写数据，再分别对桶内的数据进行排序。

总结：
  为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

  同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
 
 

代码实现

桶内排序算法可以随意使用。（时间复杂度不同）

public static void bucket_sort(int[] arr){
	    //最大最小值
	    int max = arr[0];
	    int min = arr[0];
	    int length = arr.length;

	    for(int i=1; i<length; i++) {
	        if(arr[i] > max) {
	            max = arr[i];
	        } else if(arr[i] < min) {
	            min = arr[i];
	        }
	    }

	    //最大值和最小值的差
	    int diff = max - min;

	    //桶列表
	    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
	    for(int i = 0; i < length; i++){
	        bucketList.add(new ArrayList<>());
	    }

	    //每个桶的存数区间
	    float section = (float) diff / (float) length;
	    //System.out.println(section);

	    //数据入桶
	    for(int i = 0; i < length; i++){
	        //当前数除以区间得出存放桶的位置
	        int num = (int) ((arr[i]-min) / section);
	        //最大数除出的超限了，将最大值控制放在最后一个桶内
	        if(arr[i] == max)
	        	num = length - 1;
	        if(num < 0){
	            num = 0;
	        }
	        bucketList.get(num).add(arr[i]);
	    }

	    //桶内排序
	    for(int i = 0; i < bucketList.size(); i++){
	        //jdk的排序速度当然信得过
	    	//System.out.println((section*i+min) + ":" + bucketList.get(i));
	        Collections.sort(bucketList.get(i));
	    }

	    //写入原数组
	    int index = 0;
	    for(ArrayList<Integer> arrayList : bucketList){
	        for(int value : arrayList){
	            arr[index] = value;
	            index++;
	        }
	    }
	}

十一、基数排序

解析基数排序

  基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
  基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

• MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

步骤：
① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

  按照数组的顺序使他们依次进入队列，取出时前进先出。

  刚刚排列的是个位，按照从低位到高位的排列顺序，还需要排列一下十位。


  十位是最高位！排序结束！
总结：
  

代码实现

int GetNum(int num,int pos){//获取num的第pos位数字 

	int temp = 1,i;
	for(i=1;i<pos;i++)
	 	temp*=10;
	return (num/temp)%10; 
	
}


void RadixSort(int *s,int n){//基数排序 
	
	int b[10][10001] = {0};
	int c[10] = {0};
	for(int i=1;i<=4;i++){//数据最大四位数 
		int j;
		for(j=0;j<n;j++){//让数组中的数根据第j位放置于桶中 
			int d = GetNum(s[j],i);
			b[d][c[d]++] = s[j];
		}
		int m = 0; 
		for(j=0;j<10;j++){//将排序好的一组数，放回数组中 
			int k;
			for(k=0;k<c[j];k++){
				s[m++] = b[j][k];
			}
			c[j] = 0;
		}
	}
	
}