学习C语言快速排序算法 |21xrx.com

学习C语言快速排序算法

2023-09-29 06:05:31 深夜i -- --

C语言快速排序算法学习算法分析实现

快速排序是一种常用的排序算法，特别适用于大规模数据的排序。它基于分治的思想，通过将一个大问题分割成多个小问题来解决。在C语言中，快速排序算法的实现较为简单。

快速排序的基本思想是选择一个基准元素（通常是数组的第一个元素），将数组分成两个子数组，一个子数组中的所有元素都小于等于基准元素，另一个子数组中的所有元素都大于基准元素。然后，递归地对这两个子数组进行快速排序，最终将整个数组排序完成。

下面是一个使用C语言实现快速排序的示例代码：


#include <stdio.h>
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
int partition(int arr[], int low, int high) {
  int pivot = arr[low]; // 选择第一个元素为基准
  int i = low;
  int j = high;
  while (i < j) {
    while (arr[j] > pivot)
      j--;
    
    while (arr[i] <= pivot && i < j) {
      i++;
    }
    if (i < j) {
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[low], &arr[j]);
  return j;
}
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int index = partition(arr, low, high);
    quickSort(arr, low, index - 1);
    quickSort(arr, index + 1, high);
  }
}
int main() {
  int arr[] = 8;
  int n = sizeof(arr) / sizeof(arr[0]);
  printf("原始数组：");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  quickSort(arr, 0, n - 1);
  printf("排序后数组：");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  return 0;
}

在这个示例中，我们首先定义了一个`swap`函数来交换两个元素的值。接下来，`partition`函数用来选择基准元素并将数组分成两个子数组。最后，`quickSort`函数通过递归地调用`partition`函数来实现快速排序。

在`main`函数中，我们定义了一个包含一些无序元素的数组，并通过`printf`函数打印原始数组。然后，我们调用`quickSort`函数对数组进行排序，并再次使用`printf`函数打印排序后的数组。

编译并运行这段代码，将得到以下结果：

原始数组：7 2 1 6 8 5 3 4 排序后数组：1 2 3 4 5 6 7 8

可以看到，快速排序算法有效地将数组排序。由于它的平均时间复杂度为O(nlogn)，快速排序是一种高效的排序算法，被广泛应用于各种排序问题中。通过学习和掌握快速排序算法，可以提高编程能力并解决实际问题中的排序需求。

上一篇: idea打包java可执行jar包

下一篇: 使用OpenCV计算二值图像的切割线

评论区

()

相似文章