P12050

猴子吃桃

部分公司报告

nzta · 发布于 2023-07-20 · 浏览 674 回复 1

这段代码是快速排序算法的实现。下面是对代码的逐行解释：

void quickSort(int *arr, int low, int high): 这是一个快速排序的函数，它接受一个整数数组 arr、最低索引 low 和最高索引 high 作为参数。

if (low >= high) { return; }: 如果最低索引 low 大于等于最高索引 high，则结束递归，返回上一层。

int first = low;: 初始化一个指针 first，它指向最低索引 low。

int last = high;: 初始化一个指针 last，它指向最高索引 high。

int key = arr[first];: 将数组中第一个元素作为基准值 key。

while (first < last) {: 当 first 指针小于 last 指针时，执行以下操作：

while (first < last && arr[last] >= key) { last--; }: 从数组的高位开始，找到第一个比基准值 key 小的元素，并将 last 指针向前移动。

if (first < last) { arr[first++] = arr[last]; }: 如果 first 指针小于 last 指针，将找到的小元素移到低位，并将 first 指针向后移动。

while (first < last && arr[first] <= key) { first++; }: 从数组的低位开始，找到第一个比基准值 key 大的元素，并将 first 指针向后移动。

if (first < last) { arr[last--] = arr[first]; }: 如果 first 指针小于 last 指针，将找到的大元素移到高位，并将 last 指针向前移动。

arr[first] = key;: 将基准值 key 放置到正确的位置上。

quickSort(arr, low, first - 1);: 对基准值左边的子数组进行递归排序。

quickSort(arr, first + 1, high);: 对基准值右边的子数组进行递归排序。

这样，通过不断地选取基准值并进行分区，递归调用快速排序函数，最终实现了对整个数组的排序。

全部回复 共 1 条

  1. 芝士不拉丝 #1 ·

    void quickSort(int* arr, int low, int high) {

    if (low >= high) { // 结束标志
    return;
}

int first = low; //地位坐标
int last = high; //高位坐标
int key = arr[first]; //设置第一个为基准

while (first < last) {
    //将比第一个小的移到前面
    while (first < last && arr[last] >= key) {
        last--;
    }
    if (first < last) {
        arr[first++] = arr[last];
    }
    
    //将比第一个大的移到后面
    while (first < last && arr[first] <= key) {
        first++;
    }
    if (first < last) {
        arr[last--] = arr[first];
    }
}

arr[first] = key;

//前半递归
quickSort(arr, low, first - 1);
//后半递归
quickSort(arr, first + 1, high);

    }

发表回复