假设要排序的数组是A[0]……A[N-1]。首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。这样数组就被关键数据分成了两部分,用相同的办法将这两部分继续进行快速排序,直到分隔的数据为单个为止。
值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
代码
void quick_sort(int a[], int left, int right)
{
if (left >= right) {
return;
}
int i = left;
int j = right;
int t = a[i];
while (i < j) {
// 从右向左找第一个小于x的数
while (i < j && a[j] >= x) {
j--;
}
if (i < j) {
a[i] = a[j];
i++;
}
// 从左向右找第一个大于等于x的数
while (i < j && a[i] < x) {
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = t;
// 递归调用
quick_sort(s, left, i - 1);
quick_sort(s, i + 1, right);
}
网友评论