写一个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)

# Example usage
arr = [5, 2, 1, 8, 4, 7, 6, 3]
sorted_arr = quick_sort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4, 5, 6, 7, 8]

相关问题

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.