C语言实现基础排序算法

article/2025/9/30 15:06:08
排序算法平均时间复杂度最差时间复杂度空间复杂度数据对象稳定性
冒泡排序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 值为 0for(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 (low<high) {//high指针左移，直至遇到比pivotkey值小的记录，指针停止移动while (low<high && L->r[high].key>=pivotkey) {high--;}//直接将high指向的小于支点的记录移动到low指针的位置。L->r[low]=L->r[high];//low 指针右移，直至遇到比pivotkey值大的记录，指针停止移动while (low<high && L->r[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 (low<high) {//找到支点的位置int pivotloc=Partition(L, low, high);//对支点左侧的子表进行排序QSort(L, low, pivotloc-1);//对支点右侧的子表进行排序QSort(L, pivotloc+1, high);}
}void QuickSort(SqList *L){QSort(L, 1,L->length);
}

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].key<SR[j].key) {TR[k]=SR[i++];} else {TR[k]=SR[j++];}}//将剩余的比目前TR数组中都大的记录复制到TR数组的最后位置while(i<=m) {TR[k++]=SR[i++];}while (j<=n) {TR[k++]=SR[j++];}
}void MSort(SqNode SR[],SqNode TR1[],int s,int t)
{SqNode TR2[MAX];//递归的出口if (s==t) {TR1[s]=SR[s];} else {int m=(s+t)/2;//每次递归将记录表中记录平分，直至每个记录各成一张表MSort(SR, TR2, s, m);//将分开的前半部分表中的记录进行排序MSort(SR,TR2, m+1, t);//将后半部分表中的记录进行归并排序Merge(TR2,TR1,s,m, t);//最后将前半部分和后半部分中的记录统一进行排序}
}//归并排序
void MergeSort(SqList *L)
{MSort(L->r,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;// 定义临时数组，并且初始值为0int* 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;   //记录当前桶中的数量，初始化桶中数量为0bucket_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 ("\n\n");
}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进行计数排序（利用计数排序适用于小范围数的特点）
    在这里插入图片描述
/* 获取输入数字的索引值，dec指定数字的位数，3代表百位数，order指定需要获取哪一位的索引，1代表个位，2代表十位，3代表百位 */
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<dec-1; j++)n *= 10;div = num/n;num -= div * n;dec--;}/* 获得对应位数的整数 */n = 1;for (i = 0; i < order-1; i++)n *= 10;/* 获取index */index = num / n;return index;
}/* 进行基数排序 */
void radix_sort(int array[], int len, int dec, int order)
{int i, j;int index;     /* 排序索引 */int tmp[len];  /* 临时数组，用来保存待排序的中间结果 */int num[10];   /* 保存索引值的数组 */memset(num, 0, 10*sizeof(int));  /* 数组初始清零 */memset(tmp, 0, len*sizeof(int)); /* 数组初始清零 */if (dec < order) /* 最高位排序完成后返回 */return;for (i = 0; i < len; i++) {index = get_index(array[i], dec, order);  /* 获取索引值 */num[index]++;  /* 对应位加一 */}for (i = 1; i < 10; i++)num[i] += num[i-1]; /* 调整索引数组 */for (i = len-1; i >= 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 time\n", 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 ("\n\n");
}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;   /* 最大数据位数，2代表1位数 */int order = 1; /* 排序的位数，1代表个位、2代表十位、3代表百位 */printf("原数据:\n");PrintArr (array, len);/* 排序函数，从个位开始 */radix_sort(array, len, dec, order);printf("新数据:\n");PrintArr (array, len);return 0;
}

在这里插入图片描述


http://chatgpt.dhexx.cn/article/40bT5XnO.shtml

相关文章

排序算法-总结（c语言）

排序算法-总结（c语言）

排序算法有很多种&#xff0c;但是我看网络上大多数都是十大经典排序算法&#xff0c;分别有&#xff1a; 目录 冒泡排序 1. 算法步骤 2.代码 选择排序 1. 算法步骤 2.代码 插入排序 1. 算法步骤 2.图解&#xff08;源自我主页文章&#xff09; 3.代码 希尔排序 1.…
阅读更多...
C语言实现八种排序算法

C语言实现八种排序算法

文章目录 排序算法选择排序冒泡排序插入排序归并排序希尔排序快速排序堆排序计数排序 排序算法 平时用惯了高级语言高级工具高级算法&#xff0c;难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维&#xff0c;熟练运用可起到举一反三之功效。 …
阅读更多...
c语言八大排序算法详细版

c语言八大排序算法详细版

概述排序有内部排序和外部排序&#xff0c;内部排序是数据记录在内存中进行排序&#xff0c;而外部排序是因排序的数据很大&#xff0c;一次不能容纳全部的排序记录&#xff0c;在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大&#xff0c;则应采用时…
阅读更多...
C语言各大排序算法整理及动画演示

C语言各大排序算法整理及动画演示

&#xff08;一&#xff09;插入排序 插入排序基本思想&#xff1a;从初始的子集合开始&#xff0c;不断地将新的元素插入到已排序好的子集合当中的合适位置。&#xff08;未排序的插入到已排序当中&#xff09;具体分为直接插入排序和希尔排序两种。 ①直接插入排序 void Ins…
阅读更多...
浅谈排序算法：冒泡排序法和选择排序法的区别

浅谈排序算法：冒泡排序法和选择排序法的区别

之前学习了冒泡排序法和选择排序法&#xff0c;最近被老师问某个道题用的是什么排序法。自己居然答不出来&#xff0c;才发现自己没有真正弄懂&#xff0c;这两个算法的原理和区别&#xff0c;所以 1冒泡排序法 1.1什么是冒泡排序法&#xff1f; 顾名思义&#xff0c;冒泡排…
阅读更多...
Java语言实现常用的十种排序算法

Java语言实现常用的十种排序算法

排序问题一直都是程序工作或面试中的重点&#xff0c;特别是对于排序算法而言&#xff0c;在一些公司的笔试中&#xff0c;手写个冒泡啥的也不足为奇&#xff0c;因此今天抽空整理一下Java语言实现的各类排序算法&#xff0c;互勉学习一下。根据排序的不同方式大概可归为一下五…
阅读更多...
排序算法（二）—— 选择法排序算法

排序算法（二）—— 选择法排序算法

1、选择法排序简介 选择法排序算法是一种常用的排序算法&#xff0c;他的实现方法是遍历数组所有元素&#xff0c;找出最小的元素&#xff0c;将它与第一个元素交换&#xff1b;然后遍历剩下的元素&#xff0c;找出最小的元素并与第二个元素交换&#xff1b;接下来再遍历剩下的…
阅读更多...
Java编程：排序算法——选择排序

Java编程：排序算法——选择排序

基本介绍 选择式排序也属于内部排序法&#xff0c;是从欲排序的数据中&#xff0c;按指定的规则选出某一元素&#xff0c;再依规定交换位置后达到排序的目的。 选择排序思想: 选择排序&#xff08;select sorting&#xff09;也是一种简单的排序方法。它的基本思想是&#x…
阅读更多...
Java常用排序算法/程序员必须掌握的8大排序算法

Java常用排序算法/程序员必须掌握的8大排序算法

本文由网络资料整理而来&#xff0c;如有问题&#xff0c;欢迎指正&#xff01; 参考链接&#xff1a;维基百科-排序算法 // 排序原始数据 private static final int[] NUMBERS {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15,…
阅读更多...
排序算法：选择排序

排序算法：选择排序

1. 什么是选择排序&#xff1f;&#xff08;摘抄自百度百科&#xff09; 选择排序&#xff08;Selection sort&#xff09;是一种简单直观的排序算法。 它的工作原理是&#xff1a; 第一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c…
阅读更多...
排序算法——选择排序

排序算法——选择排序

目录 &#x1f43e;基本介绍 &#x1f31e;算法思想&#xff1a; &#x1f330;实例&#xff1a; ⛅思路分析&#xff1a; &#x1f308;总结&#xff1a; &#x1f6f4;代码实现: &#x1f6f9;算法性能分析 &#x1f355;时间复杂度 &#x1f367;空间复杂度 &…
阅读更多...
基本算法-选择排序

基本算法-选择排序

作者&#xff1a;翟天保Steven 版权声明&#xff1a;著作权归作者所有&#xff0c;商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处 前言 本文介绍一种经典排序算法——选择排序&#xff0c;是入门级的排序算法之一。以下是本篇文章正文内容&#xff0c;包括算法简…
阅读更多...
程序员八大排序算法之直接选择排序算法（java版）

程序员八大排序算法之直接选择排序算法（java版）

一&#xff0c;选择排序算法思路&#xff1a;每趟选择序列的最小值/最大值&#xff0c;采取贪心选择策略。 二&#xff0c;选择排序算法有两种&#xff1a;1.直接选择排序 2.堆排序&#xff08;基于二叉树&#xff09;。 &#xff08;这里讲解直接选择排序&#xff09; 三&a…
阅读更多...
排序算法--选择排序（Java实现）

排序算法--选择排序（Java实现）

选择排序概念 选择排序&#xff08;Selection sort&#xff09;是一种简单直观的排序算法。它的工作原理是&#xff1a;第一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;然后再从剩余的未排序元素中寻…
阅读更多...
java之选择排序

java之选择排序

基本介绍 选择排序同样属于内部排序法&#xff0c;是从欲排序的数据中&#xff0c;按指定的规则选出某一元素&#xff0c;再按规定交换位置达到排序的目的。 排序思想 选择排序是一种简单的排序方法。它的基本思想是&#xff1a;第一次从arr[0]~arr[n-1]中选取最小值&#xf…
阅读更多...
java选择排序（含选择排序代码）

java选择排序（含选择排序代码）

目录 一&#xff1a;选择排序的思想 ​二&#xff1a;选择排序的代码 三&#xff1a;结果 一&#xff1a;选择排序的思想 选择排序是一种简单直观的排序算法。它的工作原理是&#xff1a;第一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&…
阅读更多...
选择排序算法

选择排序算法

选择排序&#xff08;Selection Sort&#xff09;是一种简单直观的排序算法。它的工作原理是&#xff1a;第一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;然后再从剩余的未排序元素中寻找到最小&…
阅读更多...
Java——常见的几种排序算法

Java——常见的几种排序算法

一、冒泡排序 每次冒泡过程都是从数列的第一个元素开始&#xff0c;然后依次和剩余的元素进行比较, 跟列队一样, 从左到右两两相邻的元素比大小, 高的就和低的换一下位置. 最后最高(值最大)的肯定就排到后面了. 但是这只是把最高的排到后面了, 还得找出第二高的, 于是又从第一…
阅读更多...
Java实现选择排序

Java实现选择排序

Java实现选择排序 选择排序原理为&#xff1a;随机确定一个标志位&#xff08;一般为第一个数字&#xff09;作为最小数&#xff0c;然后向后遍历&#xff0c;找到比标志位更小的数便与标志位互换位置并更新最小数&#xff0c;实现步骤为&#xff1a; 将数组的第一个数字设置…
阅读更多...
【算法】选择排序法

【算法】选择排序法

一、介绍 1.选择排序法是将序列分为两段&#xff0c;有序前列和无序后列&#xff0c;每次查找无序后列中最大元素&#xff0c;将其插入到有序前列的最末尾处&#xff0c;直至无序后列最后一个元素&#xff0c;最终排序后的序列为降序序列 2.适用于包括数组和向量在内的序列 …
阅读更多...
推荐文章

Copyright @ 2022~2023