21xrx.com
2025-03-28 05:46:29 Friday
文章检索 我的文章 写文章
C语言实现快速排序算法
2023-09-29 22:51:24 深夜i     23     0
快速排序算法 C语言实现

快速排序是一种常用的排序算法，它可以在平均情况下以O(nlogn)的时间复杂度对数组进行排序。C语言是一种广泛使用的编程语言，也是快速排序算法常用的实现语言之一。本文将介绍如何在C语言中实现快速排序算法。

首先，让我们了解一下快速排序的基本原理。快速排序的核心思想是通过选取一个基准元素，将数组分为左右两个部分。左侧部分的元素都小于等于基准元素，右侧部分的元素都大于等于基准元素。接下来，递归地对左右两个部分进行快速排序，直到数组有序。

在C语言中，我们可以通过以下步骤实现快速排序算法：

1. 定义一个函数，命名为quickSort，用于递归地对数组进行快速排序。函数的原型可以这样定义：void quickSort(int arr[], int low, int high)。

2. 在quickSort函数中，我们需要选择一个基准元素，并将数组进行分区。选择基准元素的方法有很多种，常用的方法是选取数组的中间元素。我们可以定义一个函数partition，用于将数组分为左右两个部分，并返回基准元素的索引。

3. 在partition函数中，我们可以通过以下步骤完成分区。首先，定义两个变量i和j，分别指向数组的第一个元素和最后一个元素。然后，选择基准元素，可以将其赋值给一个临时变量pivot。接下来，使用循环将数组分区：从左侧开始，找到一个大于等于基准元素的元素，从右侧开始，找到一个小于等于基准元素的元素，然后交换这两个元素。重复这个过程，直到i和j指针相遇。最后，将基准元素放置在相遇位置，并返回相遇位置的索引。

4. 接下来，在quickSort函数中，我们需要按照基准元素的索引，递归地对左右两个部分进行快速排序。具体方式是调用quickSort函数，传入数组、low和pivot-1，以及传入数组、pivot+1和high。

5. 最后，在主函数中，我们可以创建一个数组，并调用quickSort函数对数组进行快速排序。排序完成后，我们可以遍历数组并输出排序结果。

下面是一个完整的示例代码：

#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; 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 pivot = partition(arr, low, high);
    
    quickSort(arr, low, pivot-1);
    quickSort(arr, pivot+1, high);
  }
}
int main(){
  int arr[] = 7;
  int n = sizeof(arr)/sizeof(arr[0]);
  
  quickSort(arr, 0, n-1);
  
  printf("Sorted array: ");
  for(int i=0; i<n; i++){
    printf("%d ", arr[i]);
  }
  return 0;
}

通过以上步骤，在C语言中实现了快速排序算法。从结果上看，程序将输入数组[10, 7, 8, 9, 1, 5]排序为[1, 5, 7, 8, 9, 10]。这个示例展示了C语言中如何实现快速排序算法，对于更复杂的数组也可以使用相同的思路进行处理。

  
  

评论区

请求出错了