初始版本
void quick_sort(long long a[], int left, int right)
{
if (left > right) return;
int i = left, j = right;
long long pivot = a[left]; // 以最左边的数为基准数
while(i < j) {
while (i < j && pivot <= a[j]) j--; // 从最右边开始找
while (i < j && pivot >= a[i]) i++;
swap(a[i], a[j]);
}
swap(a[j], a[left]);
quick_sort(a, left, j-1);
quick_sort(a, j+1, right);
}
优化版本 - 1（填坑法）
void quick_sort(long long a[], int left, int right)
{
if (left > right) return;
int i = left, j = right;
long long pivot = a[left]; // 以最左边的数为基准数
while(i < j) {
while (i < j && pivot <= a[j]) j--; // 从最右边开始找
a[i] = a[j];
while (i < j && pivot >= a[i]) i++;
a[j] = a[i];
}
a[i] = pivot;
quick_sort(a, left, j-1);
quick_sort(a, j+1, right);
}
优化版本 - 2 （随机快排）
void quick_sort(long long a[], int left, int right)
{
if (left >= right) return;
srand(unsigned(time(NULL)));
int random = rand()%(right - left + 1) + left; // 产生left ~ right 的随机数
swap(a[left], a[random]); // 和最左边的数交换
int i = left, j = right;
long long pivot = a[left]; // 以最左边的数为基准数
while(i < j) {
while (i < j && pivot <= a[j]) j--; // 从最右边开始找
a[i] = a[j];
while (i < j && pivot >= a[i]) i++;
a[j] = a[i];
}
a[i] = pivot;
quick_sort(a, left, j-1);
quick_sort(a, j+1, right);
}
wxc0914
发布了29 篇原创文章 · 获赞 10 · 访问量 2570
私信
关注