C语言基础（三十）

2024-09-01 18:20

文章标签 语言基础三十

本文主要是介绍C语言基础（三十），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、希尔排序：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 希尔排序函数  
void shellSort(int arr[], int n) {  for (int gap = n / 2; gap > 0; gap /= 2) {  // 对每个子列表进行插入排序  for (int i = gap; i < n; i += 1) {  int temp = arr[i];  int j;  for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  arr[j] = arr[j - gap];  }  arr[j] = temp;  }  }  
}  // 生成随机数并动态添加到数组中 
int* generateRandomArray(int n) {  int *arr = (int*)malloc(n * sizeof(int)); // 动态分配内存  if (!arr) {  fprintf(stderr, "Memory allocation failed\n");  exit(EXIT_FAILURE);  }  srand(time(NULL)); // 初始化随机数种子  for (int i = 0; i < n; i++) {  arr[i] = rand() % 100; // 生成0到99之间的随机数  }  return arr;  
}  int main() { int times = getTime(); int n;  printf("Enter the number of elements: ");  scanf("%d", &n);  int *arr = generateRandomArray(n);  printf("Original array: \n");  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  printf("\n");  shellSort(arr, n);  printf("Sorted array: \n");  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  printf("\n");  free(arr); // 释放动态分配的内存  return 0;  
}

运行结果如下：

2、计数排序：

#include "date.h" 
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 计数排序函数  
void countingSort(int *arr, int n) {  // 假设arr中的元素范围是0到100  int output[101] = {0};  // 计算每个元素的频率  for (int i = 0; i < n; i++) {  output[arr[i]]++;  }  // 根据频率累加和修改原数组  int index = 0;  for (int i = 0; i < 101; i++) {  while (output[i] > 0) {  arr[index++] = i;  output[i]--;  }  }  
}  // 生成随机数并动态加入到数组中 
int* generateRandomArray(int n) {  int *arr = (int*)malloc(n * sizeof(int));  if (!arr) {  fprintf(stderr, "Memory allocation failed\n");  exit(EXIT_FAILURE);  }  srand(time(NULL)); // 初始化随机数种子  for (int i = 0; i < n; i++) {  arr[i] = rand() % 101; // 生成0到100之间的随机数  }  return arr;  
}  int main() {  int times = getTime();int n;  printf("Enter the number of elements: ");  scanf("%d", &n);  int *arr = generateRandomArray(n);  printf("Original array: \n");  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  printf("\n");  countingSort(arr, n);  printf("Sorted array: \n");  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  printf("\n");  free(arr); // 释放动态分配的内存  return 0;  
}

运行结果如下：

3、基数排序：

#include "date.h"
#include <stdio.h>
#include <stdlib.h>// 获取数组中最大的数
int getMax(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}// 以exp为基数对数组arr进行计数排序
void countSort(int arr[], int n, int exp) {int output[n];int count[10] = {0};for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}for (int i = 0; i < n; i++) {arr[i] = output[i];}
}// 基数排序
void radixSort(int arr[], int n) {int max = getMax(arr, n);for (int exp = 1; max / exp > 0; exp *= 10) {countSort(arr, n, exp);}
}int main() {int times = getTime();int n;printf("请输入数组的大小 n：");scanf("%d", &n);int* arr = (int*)malloc(n * sizeof(int));// 生成随机数并动态添加到数组中for (int i = 0; i < n; i++) {arr[i] = rand() % 100; // 生成 0-99 的随机数}// 排序前的数组printf("基数排序前的数组为：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 对数组进行基数排序radixSort(arr, n);// 排序后的数组printf("基数排序后的数组为：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}free(arr);return 0;
}

运行结果如下：