快速排序。
* 从数组中取出一个基准数,遍历数组中的每个元素,与基准数比较大小,将小于基准数的元素放在其左侧,大于基准数的元素放在其右侧,
* 在分好后的两侧内递归执行上述操作
时间复杂度O(nlog2n);
空间复杂度O(log2n);
**不稳定
static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right, x = array[left];
while (i < j) {
// 从右向左找第一个小于x的数
while (i < j && array[j] >= x) {
j--;
}
if (i < j) {
array[i++] = array[j];
}
// 从左向右找第一个大于等于x的数
while (i < j && array[i] < x) {
i++;
}
if (i < j) {
array[j--] = array[i];
}
}
array[i] = x;
// 递归调用此方法排序左侧部分
quickSort(array, left, i - 1);
// 递归调用此方法排序右侧部分
quickSort(array, i + 1, right);
}
还没有评论,来说两句吧...