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

C语言实现快速排序算法

2023-10-05 18:55:36 深夜i -- --

C语言快速排序算法

快速排序是一种常用的排序算法，它通过将一个待排序的序列分成两个子序列来进行排序。该算法的基本思想是通过选择一个基准元素，将比基准元素小的元素放在基准元素的左边，比基准元素大的元素放在基准元素的右边，然后递归地对左右两个子序列进行排序，最终得到一个有序的序列。

下面是使用C语言实现快速排序算法的代码：


#include <stdio.h>
// 快速排序函数
void quickSort(int arr[], int left, int right) {
  int i, j, temp, pivot;
  
  if (left < right) {
    pivot = left; // 将首元素作为基准元素
    i = left;
    j = right;
    
    while (i < j) {
      while (arr[i] <= arr[pivot] && i < right)
        i++;
      while (arr[j] > arr[pivot])
        j--;
      if (i < j) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    
    temp = arr[pivot];
    arr[pivot] = arr[j];
    arr[j] = temp;
    
    quickSort(arr, left, j - 1); // 对左子序列递归排序
    quickSort(arr, j + 1, right); // 对右子序列递归排序
  }
}
// 主函数
int main() {
  int arr[] = 8;
  int n = sizeof(arr) / sizeof(arr[0]);
  
  printf("Original array: ");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
  
  quickSort(arr, 0, n - 1);
  
  printf("Sorted array: ");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
  
  return 0;
}

上述代码中，首先定义了一个快速排序函数`quickSort`，该函数接受一个数组`arr`、左边界`left`和右边界`right`作为参数。在函数体中，选择首元素作为基准元素`pivot`，然后通过两个指针`i`和`j`分别从左和右向中间扫描数组。当`arr[i]`大于基准元素且`i`小于`j`时，两个指针相向移动，并交换两个指针所指向的元素；若`i`不小于`j`，则将基准元素与`arr[j]`交换位置。最后，对左右两个子序列分别递归调用快速排序函数。

在主函数中，我们定义了一个待排序的数组，并调用`quickSort`函数进行排序。最后，输出排序前的数组和排序后的数组。

快速排序算法的时间复杂度为O(nlogn)，其中n是待排序序列的长度。快速排序是一种高效的排序算法，常用于处理大数据量的排序问题。无论是在算法竞赛中还是在实际开发中，掌握快速排序算法都是非常重要的。

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

下一篇: 使用ffmpeg的一键脚本

评论区

()

相似文章