快速排序算法c（快速排序算法C++代码）

快速排序算法是一种高效的排序算法，它采用了分治的策略来排序一个无序的数组。本文将详细介绍快速排序算法的思想、步骤以及C语言实现。

## 简介

快速排序算法是由英国计算机科学家Tony Hoare在1959年提出的一种排序算法。它是一种基于比较的排序算法，具有平均时间复杂度为O(nlogn) 的特点，是目前最常用的排序算法之一。快速排序算法通过将数组分成两个子数组，然后对这两个子数组进行递归排序来实现对整个数组的排序。

## 步骤

快速排序算法的基本步骤如下：

1. 选择一个元素作为基准pivot。

2. 将小于基准的元素放在左边，大于基准的元素放在右边，相等的元素可以放在任意一边。

3. 对左右两边的子数组分别进行递归调用。

## C语言实现

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

```c

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);

}

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

printf("Sorted array: \n");

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

return 0;

```

上述代码中，`partition`函数用于找到基准元素的正确位置，并将小于基准的元素放在其左边，大于基准的元素放在右边。`quickSort`函数用于对子数组进行递归调用，直到排序完成。

## 总结

快速排序算法是一种高效的排序算法，具有平均时间复杂度为O(nlogn) 的特点。它通过选择基准元素，将数组分成两个子数组，然后递归对子数组进行排序，最终实现对整个数组的排序。通过C语言的实现，我们可以更好地理解快速排序算法的思想和应用。