c语言写快速排序代码网站首页 技术交流

c语言写快速排序代码

jacks-hu 2023-06-26 12:00:02

简介c语言写快速排序代码

一、快速排序

快速排序是一种基于比较的排序算法，可以在平均情况下运行时间为o(n log n)，是最常使用的快速、通用的排序算法之一。这个算法的基本思想是选择一个元素作为“枢轴”（通常是数组中的第一个或最后一个元素），然后将数组中的所有其他元素与枢轴进行比较，把小于等于枢轴的元素放到一个子数组中，把大于枢轴的元素放到另一个子数组中，在对每个子数组递归地应用此过程，直到子数组只有零个或一个元素，最后将子数组按顺序连接起来即可得到排序后的数组。

具体步骤如下：

选择枢轴元素，通常是第一个元素或最后一个元素。
将数组分成两个子数组，根据枢轴元素将小于等于枢轴元素的元素放在左边的子数组中，将大于枢轴元素的元素放在右边的子数组中。
对左右子数组递归执行快速排序操作。
最后将左、枢轴、右三部分连接起来即为排序结果。
这个算法的性能取决于所选择的枢轴元素，理想情况下每次都能够选择到位于数组正中间的元素作为枢轴，此时快速排序算法的时间复杂度为o(n log n)。但是如果每次选到的枢轴都离两端比较远，则可能会导致算法效率降低，时间复杂度达到o(n^2)。因此，在实际应用中，通常会采用一些优化策略来提高算法性能

以下是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[high]; // 选取最后一个元素作为基准值  
    int i = (low - 1); // i指向左边界  
  
    for (int j = low; j < high; j++) {  
        if (arr[j] <= pivot) {  
            i++;  
            int temp = arr[i];  
            arr[i] = arr[j];  
            arr[j] = temp;  
        }  
    }  
  
    int temp = arr[i + 1];  
    arr[i + 1] = arr[high];  
    arr[high] = temp;  
  
    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[] = {5, 2, 8, 3, 9, 1, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
  
    quickSort(arr, 0, n - 1);  
  
    printf("排序后的数组：
");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    printf("
");  
  
    return 0;  
}

在上面的代码中，swap函数用于交换两个元素的值，partition函数用于将数组分成左右两部分，并返回左右指针，quickSort函数是快速排序的主要函数，用于递归地对数组进行排序。在main函数中，我们定义了一个整数数组，并调用quickSort函数对其进行排序。最后，我们输出排序后的数组。

方法二：

#include <stdio.h>

void quicksort(int *arr, int left, int right) {
  
  if (left < right) {

    int pivot = arr[right];
    int i = left - 1;
    int temp;

    for (int j = left; j < right; j++) {
      if (arr[j] <= pivot) {
        i++;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    
    i++;
    temp = arr[i];
    arr[i] = pivot;
    arr[right] = temp;

    quicksort(arr, left, i-1);
    quicksort(arr, i+1, right);

  }
}

int main() {
  
  int arr[] = {4, 2, 1, 6, 3, 5};
  int n = sizeof(arr)/sizeof(int);

  quicksort(arr, 0, n-1);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}