How to use quicksort algorithm in C++

How to use the quick sort algorithm in C

The quick sort algorithm is a commonly used sorting algorithm. Its core idea is to continuously divide the sequence to be sorted into smaller The two subsequences, small and larger, are then sorted recursively, and finally the entire sequence is sorted. This article will introduce how to use the quick sort algorithm in C and provide specific code examples.

The implementation idea of ​​the quick sorting algorithm is as follows:

1. Select a reference element pivot, which can be any element in the sequence. Usually the first or last element is chosen as the base.
2. Put the elements in the sequence that are smaller than the pivot to the left of the pivot, and the elements that are larger than the pivot are placed on the right.
3. Quickly sort the left and right subsequences recursively.

The following is a code example using C to implement the quick sort algorithm:

#include <iostream>
using namespace std;

// 交换两个元素的值
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 - 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);  // 对右子数组进行递归排序
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原始数组：";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组：";
    printArray(arr, n);
    return 0;
}

After running the above code, you will get the following output:

原始数组：10 7 8 9 1 5 
排序后的数组：1 5 7 8 9 10 

This code implements The quick sort algorithm first selects the last element as the benchmark, and then uses the partition function to divide the array, placing elements smaller than the benchmark on the left and elements larger than the benchmark on the right. Then the left and right sub-arrays are sorted recursively until the entire array is sorted.

Summary:
Quick sort is an efficient sorting algorithm. Its average time complexity is O(n log n). It is relatively simple to implement the quick sort algorithm using C. Through the above code examples, you can understand the basic principles and implementation methods of the quick sort algorithm, and you can also use it flexibly in practical applications.

The above is the detailed content of How to use quicksort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!