main函数
int main(void) {
int n;
scanf("%d", &n);
if (n <= 0) {
puts("");
}
vector<int> vec(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &vec[i]);
}
quickSort(&vec[0], 0, n - 1);
for (int i = 0; i < n; ++i) {
printf("%d ", vec[i]);
}
puts("");
return 0;
}
左右指针不取右,j和j+1
void quickSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left + ((right - left) >> 1)];
int i = left - 1;
int j = right + 1;
while (i < j) {
while (arr[++i] < pivot) {
}
while (arr[--j] > pivot) {
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
quickSort(arr, left, j);
quickSort(arr, j + 1, right);
}
左右指针不取左,i-1和i
void quickSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[(static_cast<int64_t>(left) + right + 1) >> 1];
int i = left - 1;
int j = right + 1;
while (i < j) {
while (arr[++i] < pivot) {
}
while (arr[--j] > pivot) {
}
if (i < j) {
swap(arr[i], arr[j]);
}
}
quickSort(arr, left, i - 1);
quickSort(arr, i, right);
}
快慢指针法,取左
void quickSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left;
int j = left + 1;
while (j <= right) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
++j;
}
swap(arr[i], arr[left]);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
快慢指针法,取右
void quickSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[right];
int i = left - 1;
int j = left;
while (j < right) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
++j;
}
++i;
swap(arr[i], arr[right]);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
牛逼牛逼
牛逼
mark
# 详细
总结到位
总结得真好~!