Of course! Here is a detailed explanation and a Python implementation of the Quick Sort algorithm, including a step-by-step example.

What is Quick Sort?

Quick Sort is a highly efficient, in-place, divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Key Concepts

1. Pivot: An element from the array that is used to partition the other elements. The choice of pivot can affect the algorithm's performance. Common strategies are:

   • First Element: Simple but can lead to poor performance on already sorted arrays.
   • Last Element: Also simple but has the same potential issue.
   • Random Element: A good strategy to avoid worst-case performance on sorted data.
   • Median-of-Three: Choose the median of the first, middle, and last elements. This is a robust but more complex strategy.

2. Partitioning: This is the core of the algorithm. You rearrange the array so that all elements smaller than the pivot come before it, and all elements larger than the pivot come after it. After this step, the pivot is in its final, sorted position.

3. Recursion: After partitioning, the algorithm recursively applies the same process to the sub-array of smaller elements and the sub-array of larger elements.

   
   （图片来源网络，侵删）

The Algorithm (Step-by-Step)

Let's sort the array [8, 3, 1, 7, 0, 10, 2] using the last element as the pivot.

Initial Array: [8, 3, 1, 7, 0, 10, 2]

Step 1: First Partition

• Pivot: 2 (the last element)
• Goal: Move all elements smaller than 2 to the left, and all elements greater than 2 to the right.
• We use two pointers: i (to track the end of the "less than pivot" section) and j (to scan the array).

Now, place the pivot (2) in its correct position by swapping it with the element at i + 1.

• Swap arr[i+1] (which is arr[2], value 8) with the pivot (arr[6], value 2).

Array after partition: [1, 0, 2, 7, 3, 10, 8] The pivot 2 is now in its final sorted place.

Step 2: Recursive Calls

Now we recursively sort the two sub-arrays:

• Left sub-array: [1, 0] (elements less than 2)
• Right sub-array: [7, 3, 10, 8] (elements greater than 2)

Recursive Call 1: Sort [1, 0]

• Pivot: 0 (last element)
• Partitioning: 1 is greater than 0. Swap pivot 0 with 1.
• Result: [0, 1] (sorted)

Recursive Call 2: Sort [7, 3, 10, 8]

• Pivot: 8 (last element)
• Partitioning: 7 and 3 are less than 8. 10 is greater. The pivot 8 is placed correctly.
• Result: [3, 7, 8, 10] (sorted)

Step 3: Combine Results

The final sorted array is the sorted left sub-array, followed by the pivot, followed by the sorted right sub-array.

[0, 1] + [2] + [3, 7, 8, 10] = [0, 1, 2, 3, 7, 8, 10]

Python Implementation

Here is a common and efficient implementation of Quick Sort in Python. This version sorts the array "in-place," meaning it doesn't create new lists for the sub-arrays, saving memory.

def quick_sort(arr):
    """
    Public function to initiate the quick sort.
    It calls the helper function with the initial low and high indices.
    """
    _quick_sort_helper(arr, 0, len(arr) - 1)
def _quick_sort_helper(arr, low, high):
    """
    The recursive helper function that implements the core logic.
    """
    # Base case: if the sub-array has 0 or 1 element, it's already sorted.
    if low < high:
        # Partition the array and get the pivot's final sorted position.
        pivot_index = partition(arr, low, high)
        # Recursively sort the elements before the pivot.
        _quick_sort_helper(arr, low, pivot_index - 1)
        # Recursively sort the elements after the pivot.
        _quick_sort_helper(arr, pivot_index + 1, high)
def partition(arr, low, high):
    """
    This function takes the last element as a pivot, places the pivot element
    at its correct position in the sorted array, and places all smaller elements
    to the left of the pivot and all greater elements to the right.
    """
    # Choose the rightmost element as the pivot.
    pivot = arr[high]
    # Pointer for the greater element.
    # This 'i' tracks the boundary of the section of elements smaller than the pivot.
    i = low - 1
    # Traverse through all elements and compare them with the pivot.
    for j in range(low, high):
        if arr[j] <= pivot:
            # If an element smaller than the pivot is found, swap it with the
            # greater element pointed by 'i'.
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    # Finally, swap the pivot element with the greater element specified by 'i'.
    # This places the pivot in its correct sorted position.
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    # Return the position from where the partition is done.
    return i + 1
# --- Example Usage ---
my_array = [8, 3, 1, 7, 0, 10, 2, 9]
print("Original array:", my_array)
quick_sort(my_array)
print("Sorted array:  ", my_array)
# Another example
my_array_2 = [3, 6, 8, 10, 1, 2, 1]
print("\nOriginal array:", my_array_2)
quick_sort(my_array_2)
print("Sorted array:  ", my_array_2)

Complexity Analysis

• Time Complexity:

  • Best Case: O(n log n). This occurs when the pivot always divides the array into two roughly equal halves.
  • Average Case: O(n log n). Quick Sort is very efficient on average.
  • Worst Case: O(n²). This occurs when the pivot is consistently the smallest or largest element (e.g., sorting an already sorted array with the first/last element as the pivot). This leads to highly unbalanced partitions.

• Space Complexity:

  • O(log n) on average. This is due to the recursion stack. In the best/average case, the recursion depth is log n.
  • O(n) in the worst case, if the recursion becomes a linear chain of n calls.

Pros and Cons

Pros:

• Very Fast: On average, it's one of the fastest sorting algorithms in practice.
• In-place: It requires very little additional memory (only for the recursion stack).
• Cache-friendly: It has good locality of reference, which makes it fast on modern computer architectures.

Cons:

• Worst-case Performance: Its O(n²) worst-case time complexity can be a problem if the input data is likely to be sorted or nearly sorted.
• Not Stable: A stable sort maintains the relative order of equal elements. Quick Sort is not inherently stable. (This can be fixed with more complex implementations).