【Sorting - Quick sort】

【Sort - Quick Sort】

2024-07-12

Quick Sort is an efficient sorting algorithm based on the Divide and Conquer strategy. The core idea of this sorting algorithm is to select a pivot element, split the array into two parts, so that the elements on the left are less than or equal to the pivot element, and the elements on the right are greater than or equal to the pivot element, and then recursively apply quick sort to the two parts.

Algorithm steps:

Select the base element: Select an element from the array as the pivot. Usually the first element, the last element, or a random element is selected as the pivot.
Partition: Rearrange the array so that all elements smaller than the pivot element are to the left of the pivot element, and all elements larger than the pivot element are to the right. At the same time, the pivot element is in the final sorted position.
Recursive sorting: Recursively sort the subarrays on the left and right sides of the pivot element.

Implementation steps:

The following is the code for implementing quick sort in C language:

#include <stdio.h>

// 函数：交换数组中两个元素的值
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;  // 初始化分区索引，比基准元素小的元素会放在左边

    for (int j = low; j < high; 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++) {
        printf("%d ", arr[i]);
    }
    printf("n");
}

// 主函数：测试快速排序的实现
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: n");
    printArray(arr, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Code analysis:

swap Function: Used to exchange the values of two elements in an array.
partition function: Select the last element in the array as the benchmark, divide the array into two parts, and return the final position index of the benchmark element.
quickSort Function: A recursive algorithm that implements quick sort. In each recursion, the array is first partitioned using the partition function, and then the two partitioned parts are recursively sorted.
printArray Function: Used to print array elements to facilitate viewing of sorting results.
main function: Test the implementation of quick sort and print the array before and after sorting.

time complexity:

The time complexity of quick sort depends mainly on the time complexity of the partition operation and the number of recursive calls. In the worst case, the time complexity of quick sort is O(n^2), but in the average case it is O(n log n), which makes it an efficient sorting algorithm.

Summarize:

Quick sort achieves efficient sorting through divide-and-conquer strategy and partition operation. It does not require additional storage space (except for stack space during recursive calls) and has good performance on average. Therefore, quick sort is one of the commonly used sorting algorithms in practical applications, especially suitable for sorting tasks of large data sets.

Technology Sharing