Quick Sort Visualization - Divide and Conquer Animation

Quick Sort is an efficient divide-and-conquer sorting algorithm. It selects a 'pivot' element and partitions the array into two parts: elements smaller than the pivot go to the left, larger ones to the right. Then recursively sorts both parts. Due to its excellent average performance, Quick Sort is one of the most commonly used sorting algorithms in practice.

⚡ Pivot ◀ Left Pointer ▶ Right Pointer

Algorithm Steps

Choose a pivot element (usually the last element)
Set two pointers: i (boundary of smaller section) and j (scanner)
j scans left to right; swap elements smaller than pivot with i+1, increment i
After scanning, swap pivot with position i+1; pivot is now in place
Recursively apply to left and right partitions

Time and Space Complexity

Case	Time Complexity	Description
Best Case	O(n log n)	Each partition splits array evenly
Average Case	O(n log n)	Expected performance on random input
Worst Case	O(n²)	Always picking smallest or largest as pivot
Space Complexity	O(log n)	Recursive call stack depth

Fast速排序是不Stable Sort，但可以通过三路划分等变体来优化。

Use Cases

General sorting: Most language standard libraries use Quick Sort
Large-scale data: Excellent average performance, good cache locality
When stability not required: e.g., numerical sorting
Hybrid approaches: Use insertion sort for small arrays

General Sorting Large Data Standard Library Competitive Programming

Implementation

def partition(arr, low, high):
    """分区函数：选择最后一个元素作为基准"""
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort(arr, low, high):
    """快速排序算法"""
    if low < high:
        # 获取分区点
        pi = partition(arr, low, high)
        
        # 递归排序左右两部分
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)


# 使用示例
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
# 输出: [1, 5, 7, 8, 9, 10]

public class QuickSort {
    
    /**
     * 分区函数
     */
    private static int partition(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++;
                // 交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 将基准放到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;
    }
    
    /**
     * 快速排序算法
     */
    public static 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);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        // 输出: [1, 5, 7, 8, 9, 10]
    }
}