quick sort

快速排序（Quick Sort）是一种常见的排序算法，基于分治的思想。它的基本思路是先选取一个基准元素，然后将待排序序列分成两个子序列，左边的子序列中的元素都比基准元素小，右边的子序列中的元素都比基准元素大。接着，对左右两个子序列分别进行递归排序，最终得到有序序列。

以下是快速排序的代码实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quick_sort(left) + [pivot] + quick_sort(right)

该函数的时间复杂度为O(nlogn)，空间复杂度为O(n)。

相关问题

Quick sort

Quick sort is a popular sorting algorithm that works by partitioning an array into two sub-arrays, and then recursively sorting each sub-array. It is a divide-and-conquer algorithm that has an average time complexity of O(n log n), making it one of the fastest sorting algorithms.

The basic idea behind quick sort is to select a pivot element, partition the array around the pivot element, and then recursively apply the same process to each of the sub-arrays. The partitioning process involves selecting a pivot element, rearranging the array so that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side, and then returning the index of the pivot element. This pivot index is then used to divide the array into two sub-arrays, which are recursively sorted.

Here's an example implementation of quick sort in Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quick_sort(left) + [pivot] + quick_sort(right)

This implementation selects the first element of the array as the pivot, and then uses list comprehensions to create the left and right sub-arrays. The left sub-array contains all elements less than the pivot, while the right sub-array contains all elements greater than or equal to the pivot. The function then recursively sorts the left and right sub-arrays and combines them with the pivot element to produce the final sorted array.

quick sort c++

Sure! Here's an implementation of the Quick Sort algorithm in C++:

#include <iostream>
#include <vector>

// Function to partition the array and return the pivot index
int partition(std::vector<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++;
            std::swap(arr[i], arr[j]);
        }
    }
    
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Function to perform quick sort recursively
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    std::vector<int> arr = {9, 5, 2, 7, 1, 8};
    
    std::cout << "Array before sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    quickSort(arr, 0, arr.size() - 1);
    
    std::cout << "\nArray after sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    return 0;
}

In this example, the `partition` function is used to choose a pivot element from the array and rearrange the elements such that all elements less than or equal to the pivot are on the left side, and all elements greater than the pivot are on the right side. The function returns the index of the pivot element.

The `quickSort` function is a recursive function that repeatedly partitions the array and sorts the sub-arrays on either side of the pivot.

The main function demonstrates the usage of the Quick Sort algorithm by creating a vector of integers, sorting it using `quickSort`, and then printing the sorted array.

Note that this implementation uses the last element as the pivot. There are other variations of the Quick Sort algorithm that use different pivot selection strategies.