快速排序c++代码(c++快速排序sort)

快速排序是一种常用的排序算法,在排序算法中具有较快的平均情况复杂度和较好的性能表现。本文将介绍快速排序算法的C代码实现。

### 1. 算法简介

快速排序(Quicksort)是由英国计算机科学家Tony Hoare于1959年提出的一种排序算法。它的基本思想是通过一趟排序将待排序的序列分割成独立的两部分,其中一部分的所有元素都比另一部分的元素小,并且分割点在序列中的正确位置。然后再对这两部分继续进行排序,从而达到整个序列有序的目的。

### 2. 算法实现

```c

#include

// 交换两个元素的值

void swap(int *a, int *b) {

int temp;

temp = *a;

*a = *b;

*b = temp;

// 找到分割点并返回分割点的下标

int partition(int arr[], int low, int high) {

int pivot = arr[low]; // 设置基准值为序列的第一个元素

while (low < high) {

while (low < high && arr[high] >= pivot) {

high--;

}

swap(&arr[low], &arr[high]); // 将小于基准值的元素移到左侧

while (low < high && arr[low] <= pivot) {

low++;

}

swap(&arr[low], &arr[high]); // 将大于基准值的元素移到右侧

}

return low; // 返回分割点的下标

// 快速排序函数

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, 7};

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

printf("原始序列:");

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

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

}

printf("\n");

quickSort(arr, 0, n - 1);

printf("排序后序列:");

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

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

}

printf("\n");

return 0;

```

### 3. 算法解析

快速排序的核心思想是通过递归将待排序序列分割成较小的子序列,直到子序列中只剩一个元素或者为空。每次分割过程中,选择一个基准值,将比基准值大的元素移动到右侧,比基准值小的元素移动到左侧,然后递归地对左右子序列进行快速排序,直到整个序列有序。

算法实现中,我们通过`partition`函数找到分割点的下标,然后将左右子序列进行递归快速排序。最后我们利用`swap`函数交换元素的值,实现序列的排序。

### 4. 算法示例

以输入序列`{5, 2, 8, 3, 9, 1, 7}`为例,经过快速排序后,得到有序序列`{1, 2, 3, 5, 7, 8, 9}`。

快速排序算法是一种高效的排序算法,其平均时间复杂度为O(nlogn),最坏情况下的时间复杂度为O(n^2),但由于其递归性质,空间复杂度较高。但在实际应用中,快速排序的性能优势明显,被广泛应用于各种排序场景中。

标签列表