c 语言怎么实现三个数大小排序

一、排序算法介绍

在编程中，排序算法是常用的一类算法。它们的基本思路是对一组数据进行重新排列，使得数据满足某种规律或者约束条件。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。

在本文中，我们将使用三个数大小排序问题来介绍排序算法的实际应用。

二、三个数大小排序问题描述

给定三个整数，要求按照从小到大的顺序将它们排列。

三、方案分析

对于这个问题，一种简单的想法是使用 if-else 语句进行判断：

#include 
void swap(int* a, int* b);
int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  if (a > b) {
    swap(&a, &b);
  }
  if (a > c) {
    swap(&a, &c);
  }
  if (b > c) {
    swap(&b, &c);
  }
  printf("%d %d %d\n", a, b, c);
  return 0;
}
void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

上述代码使用了三个 if-else 语句来判断三个数的大小，并使用交换函数 swap() 来交换值。这种方法的时间复杂度为 O(1)，在只有三个数时效率较高。

除此之外，我们还可以使用排序算法来解决这个问题。下面将介绍两种不同的排序算法。

1.冒泡排序

冒泡排序是一种基础的排序算法，其基本思路是通过相邻元素的比较和交换来将小的元素“冒泡”到数组前面，大的元素“沉”到数组后面。

void bubble_sort(int* arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}

冒泡排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

2.快速排序

快速排序是一种常用的排序算法，其基本思路是通过一趟排序将待排序列分割成两部分，一部分的所有元素都比另一部分的元素小，然后分别对这两部分进行排序，递归地进行下去，直到整个序列有序。

int partition(int* arr, int low, int high) {
  int pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot) high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
void quick_sort(int* arr, int low, int high) {
  if (low < high) {
    int mid = partition(arr, low, high);
    quick_sort(arr, low, mid - 1);
    quick_sort(arr, mid + 1, high);
  }
}

快速排序的时间复杂度为 O(nlogn)，最坏情况下为 O(n^2)，空间复杂度为 O(logn)。

四、代码实现

下面是上述三种算法的完整代码实现：

#include 
void swap(int* a, int* b);
void bubble_sort(int* arr, int n);
int partition(int* arr, int low, int high);
void quick_sort(int* arr, int low, int high);
int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  // 方法1：使用 if-else 语句
  if (a > b) {
    swap(&a, &b);
  }
  if (a > c) {
    swap(&a, &c);
  }
  if (b > c) {
    swap(&b, &c);
  }
  printf("%d %d %d\n", a, b, c);
  // 方法2：冒泡排序
  int arr1[3] = {a, b, c};
  bubble_sort(arr1, 3);
  printf("%d %d %d\n", arr1[0], arr1[1], arr1[2]);
  // 方法3：快速排序
  int arr2[3] = {a, b, c};
  quick_sort(arr2, 0, 2);
  printf("%d %d %d\n", arr2[0], arr2[1], arr2[2]);
  return 0;
}
void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void bubble_sort(int* arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}
int partition(int* arr, int low, int high) {
  int pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot) high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
void quick_sort(int* arr, int low, int high) {
  if (low < high) {
    int mid = partition(arr, low, high);
    quick_sort(arr, low, mid - 1);
    quick_sort(arr, mid + 1, high);
  }
}

五、总结

排序算法在日常开发中有着广泛的应用，不仅可以解决像本文中提到的三个数大小排序问题，还可以优化数据库查询、图片处理等复杂的应用场景。在实际开发中需要结合实际问题来选择合适的排序算法，并注意时间复杂度、空间复杂度等因素。