C语言基础（二十九）

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

1、快速排序：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 函数声明  
void quickSort(int *arr, int low, int high);  
void swap(int *xp, int *yp);  
void printArray(int *arr, int size);  
int  partition(int *arr, int low, int high);int main() {int times = getTime();  int n, i;  printf("请输入数字n: ");  scanf("%d", &n);  // 动态分配数组  int *arr = (int *)malloc(n * sizeof(int));  if (arr == NULL) {  printf("内存分配失败！\n");  return 1;  }  // 初始化随机数生成器  srand(time(NULL));  // 生成随机数并存储到数组中  for (i = 0; i < n; i++) {  arr[i] = rand() % 100; // 生成0到99之间的随机数  }  // 打印原始数组  printf("原始数组: ");  printArray(arr, n);  // 对数组进行快速排序  quickSort(arr, 0, n - 1);  // 打印排序后的数组  printf("排序后的数组: ");  printArray(arr, n);  // 释放内存  free(arr);  return 0;  
}  // 快速排序函数  
void quickSort(int *arr, int low, int high) {  if (low < high) {  // pi是分区索引，arr[pi]现在位于正确的位置  int pi = partition(arr, low, high);  // 分别对分区前后的子数组进行快速排序  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}  // 分区函数  
int partition(int *arr, int low, int high) {  int pivot = arr[high];    // 选择最后一个元素作为基准  int i = (low - 1);        // 较小元素的索引  for (int j = low; j <= high - 1; j++) {  // 如果当前元素小于或等于基准  if (arr[j] <= pivot) {  i++;    // 增加较小元素的索引  swap(&arr[i], &arr[j]);  }  }  swap(&arr[i + 1], &arr[high]);  return (i + 1);  
}  // 交换两个整数的值  
void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp;  
}  // 打印数组函数  
void printArray(int *arr, int size) {  for (int i = 0; i < size; i++) {  printf("%d ", arr[i]);  }  printf("\n");  
}

运行结果如下：

2、归并排序：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  // 归并排序的辅助函数  
void merge(int arr[], int l, int m, int r) {  int i, j, k;  int n1 = m - l + 1;  int n2 = r - m;  int L[n1], R[n2];  for (i = 0; i < n1; i++)  L[i] = arr[l + i];  for (j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  i = 0; // 初始索引第一个子数组  j = 0; // 初始索引第二个子数组  k = l; // 初始索引合并的子数组  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  } else {  arr[k] = R[j];  j++;  }  k++;  }  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  
}  // 归并排序函数  
void mergeSort(int arr[], int l, int r) {  if (l < r) {  int m = l + (r - l) / 2;  mergeSort(arr, l, m);  mergeSort(arr, m + 1, r);  merge(arr, l, m, r);  }  
}  // 生成随机数并动态添加到数组中 
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");  mergeSort(arr, 0, n - 1);  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>  
#include <time.h>  // 堆调整函数，用于构建最大堆  
void heapify(int arr[], int n, int i) {  int largest = i; // 初始化最大值为根  int left = 2 * i + 1; // 左子节点  int right = 2 * i + 2; // 右子节点  // 如果左子节点大于根  if (left < n && arr[left] > arr[largest])  largest = left;  // 如果右子节点大于当前最大  if (right < n && arr[right] > arr[largest])  largest = right;  // 如果最大值不是根  if (largest != i) {  int swap = arr[i];  arr[i] = arr[largest];  arr[largest] = swap;  // 递归地调整受影响的子树  heapify(arr, n, largest);  }  
}  // 堆排序函数  
void heapSort(int arr[], int n) {  // 构建最大堆  for (int i = n / 2 - 1; i >= 0; i--)  heapify(arr, n, i);  // 一个个从堆顶取出元素  for (int i = n - 1; i > 0; i--) {  // 移动当前根到末尾  int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // 调用最大堆调整函数  heapify(arr, i, 0);  }  
}  // 生成随机数并动态添加到数组中 
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");  heapSort(arr, n);  printf("Sorted array: \n");  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  printf("\n");  free(arr); // 释放动态分配的内存  return 0;  
}

运行结果如下：