C语言快速排序算法实现 |21xrx.com

C语言快速排序算法实现

2023-11-05 06:52:15 深夜i -- --

C语言快速排序算法实现

快速排序是一种常用的排序算法，其时间复杂度为O(nlogn)，在处理大量数据时表现出色。在C语言中，我们可以实现快速排序算法来对任意给定的数组进行排序。

算法思想：

快速排序算法的核心思想是分治法。首先从数组中选择一个元素作为基准点（pivot），然后将待排序的数组分割成两部分，一部分是小于基准点的元素，另一部分是大于基准点的元素。接着对这两部分进行递归调用，重复上述步骤，最终完成排序。

算法实现：

下面是在C语言中实现快速排序算法的代码示例：


#include <stdio.h>
void swap(int* a, int* b) {
  int t = *a;
  *a = *b;
  *b = t;
}
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 quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}
int main() {
  int arr[] = 11;
  int n = sizeof(arr) / sizeof(arr[0]);
  
  printf("给定数组为：");
  printArray(arr, n);
  
  quickSort(arr, 0, n - 1);
  
  printf("排序后的数组为：");
  printArray(arr, n);
  
  return 0;
}

示例解析：

上述代码中，首先定义了一个名为`swap`的函数，用于交换两个整数值。接着，`partition`函数被用来确定基准点的位置并对数组进行分割。最后，`quickSort`函数负责递归调用，实现了快速排序的具体算法。在`main`函数中，我们给定了一个数组并将其输出、排序。最终，我们得到了排序后的数组。

总结：

通过实现快速排序算法，我们在C语言中实现了一种高效、快速的排序方法。虽然算法的实现过程相对复杂，但其性能优秀，适用于大量数据的排序任务。在实际应用中，可以根据需要对代码进行优化，以提高算法的效率和适用性。

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

下一篇: FFmpeg实现24小时不间断推流

评论区

()

相似文章