博客排序

数据结构&算法

发布日期: 2022-01-19

文章字数: 6.2k

阅读时长: 26 分

排序

基本概念

排序(Sort)

排序是计算机中非常重要的操作，是按照关键字进行递增或递减排列的操作。

排序的稳定性

排序的分类

排序的算法效率

冒泡排序

冒泡排序(Bubble Sort)是一种简单的交换排序，通过元素两两比较大小，判断是否符合排序要求(升序或降序)，如果不符合就交换位置，遍历完一趟元素，元素中最大或最小的元素将会沉底。

示例

我们通过一个例子来简单了解冒泡排序的过程。

这里有一个数组，元素初始状态为4，9，5，7，3，0，2，8，我们要实现使数组元素呈从小到大排序。

第一趟冒泡

下图为排序过程。

比较0号元素和1号元素，4 小于 9，不发生交换。
比较1号元素和2号元素，9 大于 5，发生交换。
比较2号元素和3号元素，9 大于 7，发生交换。
比较3号元素和4号元素，9 大于 3，不发生交换。
比较4号元素和5号元素，9 大于 0，发生交换。
比较5号元素和6号元素，9 大于 2，发生交换。
比较6号元素和7号元素，9 大于 8，发生交换。

此时，元素中最大元素9已经沉底。

第二趟冒泡

比较0号元素和1号元素， 4 小于 5，不发生交换。
比较1号元素和2号元素， 5 小于 7，不发生交换。
比较2号元素和3号元素， 7 大于 3，发生交换。
比较3号元素和4号元素， 7 大于 0，发生交换。
比较4号元素和5号元素， 7 大于 2，发生交换。
比较5号元素和6号元素， 7 小于 8，不发生交换。

第三趟冒泡

比较0号元素和1号元素， 4 小于 5，不发生交换。
比较1号元素和2号元素， 5 大于 3，发生交换。
比较2号元素和3号元素， 5 大于 0，发生交换。
比较3号元素和4号元素， 5 大于 2，发生交换。
比较4号元素和5号元素， 5 小于 7，不发生交换。

第四趟冒泡

比较0号元素和1号元素， 4 大于 3，发生交换。
比较1号元素和2号元素， 4 大于 0，发生交换。
比较2号元素和3号元素， 4 大于 2，发生交换。
比较3号元素和4号元素， 4 小于 5，不发生交换。

第五趟冒泡

比较0号元素和1号元素， 3 大于 0，发生交换。
比较1号元素和2号元素， 3 大于 2，发生交换。
比较2号元素和3号元素， 3 小于 4，不发生交换。

第六趟冒泡

比较0号元素和1号元素， 0 小于 2，不发生交换。
比较1号元素和2号元素， 2 小于 3，不发生交换。

第七趟冒泡

比较0号元素和1号元素， 0 小于 2，不发生交换。

此时，冒泡排序完毕，元素有序排列。

代码实现

#include <stdio.h>
/*
		
外循环控制冒泡趟数，每一次都可以确定一个元素的位置，n个元素需要确定n - 1次
内循环控制冒泡次数，n个元素两两比对需要n - 1次，每进行完一趟冒泡，内循环次数可以减少一次，所以为n - 1 - i
flag用来标记是否发生过交换，如果未发生交换，说明元素有序排列，直接返回。
*/
void BubbleSort(int arr[], int len);
void Print(int arr[], int len);
//
//
void BubbleSort(int arr[], int len)
{
    int flag = 0;
    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 = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = 1;
            }
        }
        if(!flag)
            return;
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = {6, 12, 54, 69, 7, 108, -2, 0};
    int len = sizeof(arr) / sizeof(int);
    BubbleSort(arr, len);
    Print(arr, len);
    return 0;
}

选择排序

选择排序(Selection sort)是一种简单直观的选择排序算法，其基本原理是将待排序序列划分成有序和无序两部分，不断地从无序部分选择最小的或最大的元素加入到有序序列。

示例

下面通过一个例子来演示选择排序的过程。(升序)

蓝色区域表示有序部分，灰色区域表示无序部分，绿标负责遍历无序部分找到无序部分最小的值，判断是否需要和有序部分的最后一个元素进行交换。

第一轮

有序序列末尾为21，找到最小值13，21和13交换位置。

第二轮

有序序列末尾为30，找到最小值15，30和15交换位置。

第三轮

有序序列末尾为19，由于无序部分没有比19小的元素，所以没有发生交换。

第四轮

有序序列末尾为30，找到最小值21，30和21交换位置。

第五轮

有序序列末尾为37，找到最小值30，37和30交换位置。

第六轮

有序序列末尾为40，找到最小值37，40和37交换位置。

自此元素排序完毕。

代码实现

#include <stdio.h>
void SelectionSort(int arr[], int len);
void Print(int arr[], int len);
//
//
void SelectionSort(int arr[], int len)
{
    int index;
    for(int i = 0 ; i < len ; i++)
    {
        index = i;
        for(int j = i + 1 ; j < len ; j++)
        {
            if(arr[j] < arr[index])
            {
                index = j;
            }
        }
      if(index != i)
      {
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
      }
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ",arr[i]);
}
int main()
{
    int arr[] = {4, 9, 5, 7, 3, 0, 2, 8};
    int len = sizeof(arr) / sizeof(int);
    SelectionSort(arr, len);
    Print(arr, len);
    return 0;
}

插入排序

插入排序(InsertionSort)是一种简单明了的插入排序，又叫直接插入排序。其原理就是将序列分为无序和有序两个部分，待排序元素从有序部分由后往前，就像打扑克时整理牌一样找到合适的位置进行插入。

示例

因为一个数天然呈序，我们将第一个数字作为一个有序序列，从第二个元素开始到最后一个元素为无序序列，接着依次扫描无序序列，将其插入到合适的位置。

第一轮

从9开始排序，9比4大，结束循环。

第二轮

5 比 9 小，9向后挪。

5 比 4 大，结束循环。

第三轮

1 比 9 小，9向后挪。

1 比 5 小，5向后挪。

1 比 4 小，4向后挪。

1到达边界，结束循环。

第四轮

8 比 9 小，9向后挪。

8 比 5 大，结束循环。

第五轮

7 比 9 小，9向后挪。

7 比 8 小，8向后挪。

7 比 5 大，结束循环。

第六轮

10 比 9 大，结束循环。

排序完成。

代码实现

#include <stdio.h>
void Printf_Array(int a[], int len){
    for(int i = 0 ; i < len ; i++)
        printf("%d ",a[i]);
    printf("\n");
}
void InsertionSort(int a[], int len){
  	int key, j;
    for(int i = 1 ; i < len ; i++){
        key = a[i];
        j = i - 1;
        while(key < a[j] && j >= 0){
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
int main(int argc, const char * argv[]) {
    int a[] = {2, 3, 1, 4, 7};
    int len = sizeof(a) / sizeof(int);
    Printf_Array(a, len);
    Insertion_Sort(a, len);
    Printf_Array(a, len);
    return 0;
}

希尔排序

希尔排序(Shell Sort)是一种插入排序，又名缩小增量排序，它是对直接插入排序的优化。其原理是通过步长将一定间隔的元素划分为一组进行插入排序。

为什么不直接进行插入排序，而是要分组进行插入排序？这是因为插入排序的优点是对于一个基本有序的序列进行排序的速度是很快的，但对于基本乱序的序列，排序的速度就会变得很慢，如果有一个很小的元素排在后面，依次从后往前比对需要移动大量元素，所以排序的性能很低。而希尔排序通过步长划分元素，可以使得小的元素很快的就被调整到前面去。

示例

希尔排序中的步长一般开始为数组大小的一半，每一轮过后步长减一半。

下面这个序列大小为16，步长分别为8、4、2、1,步长为1时就和普通的插入排序一样。

第一轮

被标记的元素为同一组，最后一个被标记的进行插入排序。

第二轮

第三轮

第四轮

最后一轮就是普通的插入排序，此时序列基本有序，所以最后一轮很快就排序完成。

代码实现

#include <stdio.h>
void Print(int arr[], int len);
void ShellSort(int arr[], int len);
//
//
void ShellSort(int arr[], int len)
{
    int step, key, i, j;
    for(step = len / 2 ; step > 0 ; step /= 2)
    {
        for(i = step ; i < len ; i++)//待排序元素
        {
            key = arr[i];
            j = i - step;
            while(arr[j] > key && j >= 0)//遍历有序部分
            {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = key;
        }
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {97, 91, 7, 84, 10, 38, 61, 59, 6, 47, 80, 63, 39, 20, 51, 32};
    int len = sizeof(arr) / sizeof(arr[0]);
    Print(arr, len);
    ShellSort(arr, len);
    Print(arr, len);
    return 0;
}

快速排序

快速排序(Quick Sort)是一种交换排序，是对冒泡排序改良后的，并且是排序算法中平均性能最好的一种排序。

其基本原理是选择一个基数，将小于基数的数交换到数组左边，将大于基数的数交换到数组右边，交换完后这时将基数进行归位，那么基数左边都是小于或等于它，右边都是大于或等于它，接着再进行分治。

具体步骤如下

选择一个值作为基数，一般选择数组第一个元素(也可以是最后一个或者中间，具体代码实现略有不同),再设置两个变量i、j分别代表待排序数组的起始位置和结束位置，j从后开始往前扫描，找到第一个值小于基数的元素，i从前开始向后扫描，找到第一个大于基数元素，接着交换i和j。当i和j没有相遇时重复执行上述步骤，如果i和j相遇了那么基数进行归位，此时，再进行递归将左边和右边排序。

示例

下图为一轮快速排序的过程，两个绿标 i ，j 分别从左右相向，右边负责找到小于基数的值，左边负责找到大于基数的值。

j找到第一个小于基数的值2，i找到第一个大于基数的值9，2 和 9进行交换

j找到第一个小于基数的值0，i找到第一个大于基数的值5，0 和 5进行交换

j找到第一个小于基数的值3，i找到第一个大于基数的值7，3 和 7进行交换

这时i 和 j相遇，基数归位，将基数放到 i 和 j 相遇的位置

接着再递归左、右进行排序

为什么基数要归位到i 和 j相遇的位置呢？i 和 j相遇有两种情况，一种是 j 移动后两者相遇，这代表右边已经没有比基准数小的元素了，另一种情况是 i 移动后两者相遇，说明左边已经没有比基准数大的元素了。

关于快速排序的递归可以参考归并排序的递归流程，这里就不多赘述了。

代码实现

#include <stdio.h>
void QuickSort(int arr[], int left, int right);
void Print(int arr[], int len);
//
//
void QuickSort(int arr[], int left, int right)
{
    if(left >= right)//递归出口
        return;
    int key = arr[left], i = left, j = right;
    while(i != j)
    {
        //j找比key小的值
        while(arr[j] >= key && i < j)
            j--;
        //i找比key大的值
        while(arr[i] <= key && i < j)
            i++;
        //交换
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //基数归位
    arr[left] = arr[i];
    arr[i] = key;
    QuickSort(arr, left, i - 1);
    QuickSort(arr, i + 1, right);
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {4 ,9, 5, 7, 3, 0, 2, 8};
    int len = sizeof(arr) / sizeof(int);
    QuickSort(arr, 0, len - 1);
    Print(arr, len);
    return 0;
}

归并排序

归并排序(Merge Sort)是一种采用分治法的排序算法。分治法是指把一个复杂的大问题分解成一个个相似的小问题，再分别解决这些小问题，当局部的问题被解决就能得到整体的解。

归并排序的基本步骤是划分和合并，将序列不断划分，接着再把有序的序列进行合并，也就是将两个有序的序列合并成一个有序序列，即二路归并。

二路归并是归并排序里的一个重要操作，为了方便理解排序算法，下面先讲一下如何进行二路归并。

二路归并的操作很简单，如下图，蓝色序列和黄色序列是两个有序序列，这两个序列分别有一个绿色的工作指针，两个工作指针之间不断地比较大小，较小的加入到新序列中，然后工作指针向后移动。

示例

很多人对归并排序的这个递归一头雾水，不知道递归到底如何执行、什么时候返回，下面演示递归的流程，搞懂了递归的步骤，归并排序自然也就理解了。

首先我们来看一下MergeRecursive函数，这个函数负责划分并调用二路归并函数，把它划分为三个任务，第一个任务是划分左部分，第二个任务划分右部分，第三个为合并左右部分。

可以看到程序会一直执行任务1直到不满足递归条件，才会返回到上一层执行任务2，当执行完任务2返回上一层执行任务3。

代码实现

/*************************************************
 * Author           : TangRan                    
 * Blog             : tongyin.site               
 * Email            : tarngran@outlook.com       
 * Last modified    : 2022-01-25 22:53
 * Filename         : MergeSort.c
 * Description      :                            
 *************************************************/
#include <stdio.h>
#include <stdlib.h>
void Merge(int arr[], int *temp, int left, int mid, int right);//二路归并
void MergeRecursive(int arr[], int *temp, int left, int right);//划分
void MergeSort(int arr[], int len);
void Print(int arr[], int len);
// 
//
void Merge(int arr[], int *temp, int left, int mid, int right)
{
    int i = left;
    int j = mid + 1;
    int index = left;
    while(i <= mid && j <= right)
        temp[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    while(i <= mid)
        temp[index++] = arr[i++];
    while(j <= right)
        temp[index++] = arr[j++];
    for(int k = left ; k <= right ; k++)
        arr[k] = temp[k];
}
void MergeRecursive(int arr[], int *temp, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        //划分左
        MergeRecursive(arr, temp, left, mid);
        //划分右
        MergeRecursive(arr, temp, mid + 1, right);
        //归并
        Merge(arr, temp, left, mid, right);
    }
}
void MergeSort(int arr[], int len)
{
    int *temp = malloc(sizeof(int) * len);//辅助数组
    MergeRecursive(arr, temp, 0, len - 1);
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {8, 0, 1, 7, 2, 6, 5, 4, 9, 3};
    int len = sizeof(arr) / sizeof(int);
    Print(arr, len);
    MergeSort(arr, len);
    Print(arr, len);
    return 0;
}

堆排序

基本概念

堆排序(Heap Sort)是利用到堆这种数据结构来进行排序的算法。

堆具有下列性质

它是一棵完全二叉树(即从上至下，从左到右)

堆中的结点总是大于等于其子结点或总是小于等于其子结点

堆顶为最大的堆叫做大顶堆，堆顶为最小的堆为小顶堆。(兄弟结点之间无逻辑关系)

通过数组实现完全二叉树，因为完全二叉树一定是连续的，将上面的数据映射到数组中，如下图。

我们可以得出规律，即可以用公式通过父结点求出左、右结点或者通过左右节点求出父结点。

设当前结点为 i ，其父结点为(i - 1) / 2
设当前结点为 i ，其左孩子结点为 2 * i + 1 ，其右孩子结点为 2 * i + 2

将无序序列构造成堆，需要两个操作：堆化和建堆。

堆化：当堆不符合堆的特性，需要调整使其满足堆特性

建堆 : 从最后一个结点的父结点开始，从下往上，从右至左进行堆化，如果发生交换，向下进行堆化

示例

我们通过一个例子来演示建堆过程。(大顶堆)

最后一个结点下标为 6 ，其父结点为 2 ，建堆顺序为 2 -> 1 -> 0。

第一次

0、5、2中，5为最大元素，不符合大顶堆特性，调整。

第二次

3、7、9中，9为最大元素，不符合大顶堆特性，调整。

第三次

1、9、5中，9为最大元素，不符合大顶堆特性，调整。

第四次

由于第三次发生了交换，调整下来的元素可能破坏了下面堆的特性，所以向下递归重新堆化。

此时建堆完成，序列中最大元素位于树的根部，下面进行堆排序。

堆排序的具体做法是:

将树根与最后一个结点进行交换(每交换一个结点，最后结点的位置要提前)
从树根开始做堆化
重复1和2步骤

将 9 和 2 进行交换

交换上来的 2 可能破坏堆特性，所以从根结点开始做堆化

调整序列为7、3、5、1、2、0、9

将 7 和 0 进行交换

重复上述步骤，即可得到有序序列。

代码实现

/*************************************************
 * Author           : TangRan                    
 * Blog             : tongyin.site               
 * Email            : tarngran@outlook.com       
 * Last modified    : 2022-01-20 16:23
 * Filename         : heapsort.c
 * Description      :                            
 *************************************************/
#include <stdio.h>
void Swap(int *x, int *y);
void Heapify(int arr[], int root, int len);
void BuildMaxHeap(int arr[], int len);
void HeapSort(int arr[], int len);
//
//
void Swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
void Heapify(int arr[], int root, int len)
{
    int lchild = root * 2 + 1;
    int rchild = root * 2 + 2;
    int max = root;
    if(lchild < len && arr[lchild] > arr[max])
        max = lchild;
    if(rchild < len && arr[rchild] > arr[max])
        max = rchild;
    if(max != root)//发生调整
    {
        Swap(&arr[root], &arr[max]);
        Heapify(arr, max, len);
    }
}
void BuildMaxHeap(int arr[], int len)
{
    int index = (len - 1 - 1) / 2;
    for( ; index >= 0 ; index--)
    {
        Heapify(arr, index, len);
    }
}
void HeapSort(int arr[], int len)
{
    int index = len - 1;
    for( ; index > 0 ; index--)
    {
        Swap(&arr[0], &arr[index]);
        Heapify(arr, 0, index);
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {5, 9, 6, 8, 1, -2, 1000};
    int len = sizeof(arr) / sizeof(int);
    printf("排序前：");
    Print(arr, len);
    printf("建堆后：");
    BuildMaxHeap(arr, 7);
    Print(arr, len);
    printf("排序后:");
    HeapSort(arr, 7);
    Print(arr, 7);
    return 0;
}

测试结果

计数排序

计数排序(Counting Sort)是一种非比较排序算法，其利用数组下标本身天然成序的特性，来确定元素正确的位置，主要有分配和收集两个步骤。

这里有一个数组，此时如果要求输出数组排序后并且去重后的序列，你会选择什么样的方法？

我们可以利用数组下标，首先开一个稍微大点的空间，然后遍历原序列，元素是x就分配到数组下标为x的位置，分配的过程其实就是排序的过程，分配完后再进行收集，就可以得到去重、有序的序列。

那么这个稍微大点的空间为多大合适，如果太大将会浪费很多空间，如果太小元素就没有对应的空间可以分配。假设取序列中最大元素加一为空间大小,在arr[1000,990,956,942,970,900]中，将开辟1000+1的空间，然而序列中的元素都是在900 ~ 1000的区间，前面900个空间都给浪费了，所以按照最大元素加一来开空间是不合理的。其实我们只需要序列中最小值到最大值之间的空间大小，对于上面的序列，取最大值减去最小值就能对应空间，即 size = max(1000) - min(900) + 1,将开辟101个空间下标0 ~ 100, 下标加上最小值就能取得原来的值。

示例

该数组最大值为4，最小值为1，将开辟4 - 1 + 1个空间。

首先进行分配，扫描该序列将元素放到下标为自身减去最小值的位置，得到的counter数组如下图

接着进行收集，扫描counter数组，如果下标标记不为0，将下标加上最小值并放入原数组中。

例如

下标0 代表 0 + 1 即有两个1

下标2 代表 2 + 1 即有两个3

下标3 代表 3 + 1 即有一个4

收集完毕后排序完毕。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void GetMaxMin(int arr[], int len, int *x, int *y);
void CountingSort(int arr[], int len);
//
//
void GetMaxMin(int arr[], int len, int *x, int *y)
{
    int max = arr[0], min = arr[0];
    for(int i = 0 ; i < len ; i++)
    {
        if(arr[i] > max)
            max = arr[i];
        if(arr[i] < min)
            min = arr[i];
    }
    *x = min;
    *y = max;
}
void CountingSort(int arr[], int len)
{
    int min, max, index = 0;
    GetMaxMin(arr, len, &min, &max);
    int ctsize = max - min + 1;
    int *counter = malloc(sizeof(int) * ctsize);
  	memset(counter, 0, sizeof(int) * ctsize);
    for(int i = 0 ; i < len ; i++)//分配
    {
        counter[arr[i] - min]++;
    }
    for(int i = 0 ; i < ctsize ; i++)//回收
    {
           while(counter[i]--)
           {
                arr[index++] = i + min;
           }
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ;i++)
        printf("%d ",arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {19, 11, 13, 12, 13, 9, 7, 5, 1, 5, 0};
    int len  = sizeof(arr) / sizeof(int);
    CountingSort(arr, len);
    Print(arr, len);
    return 0;
}

基数排序

基数排序(Radix Sort)是一种多关键字排序，与计数排序非常相似，其原理是将元素切割成位数，按照位数分别进行比较。

基数排序和计数排序一样都要用到桶，但是计数排序每个元素单独占一个桶，而基数排序是相同基数的元素占一个桶，在基数排序中，一共只有10个桶，也就是分别对应数字0到9。

示例

下面演示基数排序的过程

主要操作就是分配和回收，按照最大元素的位数为分配的次数。

第一轮

序列中最大元素为4位数，所以要进行4轮分配，从个位开始逐一比较，第一轮比较个位。

第二轮

第二轮比较十位，每一轮都是在上一轮回收后的基础上进行分配，回收顺序要和分配顺序一样。

第三轮

第三轮比较百位。

第四轮

第四轮比较千位，此轮回收完排序完毕。

由于基数排序是用位数做关键字，如果要处理负数就需要将序列中所有的元素加上最小值的绝对值，在排序完再将元素还原即可。

代码实现

#include <stdio.h>
#include <string.h>
const int radix = 10;//0 - 9 个桶
void GetDigit(int arr[], int len, int *d);//找最大位数
void GetMin(int arr[], int len, int *m);//找最小数判断是否需要处理负数
void RadixSort(int arr[], int len);
void Print(int arr[], int len);
//
//
void GetDigit(int arr[], int len, int *d)
{
    int max = arr[0], digit = 0;
    for(int i = 0 ; i < len ; i++)
    {
        if(arr[i] > max)
            max = arr[i];
    }
    do
    {
        digit++;
    } while (max /= 10);
    *d = digit;
}
void GetMin(int arr[], int len, int *m)
{
    int min = arr[0];
    for(int i = 0 ; i < len ; i++)
    {
        if(arr[i] < min)
            min = arr[i];
    }
    *m = min;
}
void RadixSort(int arr[], int len)
{
    int bucket[radix][len + 1];//这样开会浪费很多空间，但是我还没想到好的写法:(
    int digit,min,w,index,d = 1;
    GetMin(arr, len, &min);
    GetDigit(arr, len, &digit);
    if(min < 0)//需要处理负数
    {
        for(int i = 0 ; i < len ; i++)
            arr[i] -= min;
    }
    for(int i = 0 ; i < digit ; i++)//分配
    {
        memset(bucket, 0, sizeof(bucket));//清空桶
        index = 0;
        for(int j = 0 ; j < len ; j++)
        {
            w = arr[j] / d % 10;//拿位数
            bucket[w][++bucket[w][0]] = arr[j];//每个桶的第一个位置存当前桶存放元素个数
        }
        for(int j = 0 ; j < radix ; j++)//回收桶
        {
            for(int k = 1 ; k <= bucket[j][0] ; k++)//从每个桶的1号标开始回收
            {
                arr[index++] = bucket[j][k];
            }
        }
        d *= 10;
    }
    if(min < 0)//如果有负数还原处理前的数据
    {
        for(int i = 0 ; i < len ; i++)
            arr[i] += min;
    }
}
void Print(int arr[], int len)
{
    for(int i = 0 ; i < len ; i++)
        printf("%d ",arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {400, 0, 1000, 33, 5, 325, 6, 96, 199, 59, -4, -1};
    int len = sizeof(arr) / sizeof(int);
    Print(arr, len);
    RadixSort(arr, len);
    Print(arr, len);
    return 0;
}

tang ran

http://tongyin.site/2022/01/19/Sort/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 tang ran !

博客排序

CPP QUICKSTART

这篇文章带你快速上手CPP

2022-07-09 CPP

博客编程语言

AVL Tree

AVL树的介绍

2022-01-14 数据结构&算法

博客树

Sort

排序

基本概念

排序(Sort)

排序的稳定性

排序的分类

排序的算法效率

冒泡排序

示例

代码实现

选择排序

示例

代码实现

插入排序

示例

代码实现

希尔排序

示例

代码实现

快速排序

示例

代码实现

归并排序

示例

代码实现

堆排序

基本概念

示例

代码实现

计数排序

示例

代码实现

基数排序

示例

代码实现

你的赏识是我前进的动力