nzta • 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);: 对基准值右边的子数组进行递归排序。
这样,通过不断地选取基准值并进行分区,递归调用快速排序函数,最终实现了对整个数组的排序。
评论:
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);
}
请先登录,才能进行评论