快速排序是一种采用分治法解决问题的一个典型应用，也是冒泡排序的一种改进。它的基本思想是，通过一轮排序将待排记录分割成独立的两部分，其中一部分均比另一部分小，则可分别对这两部分继续进行排序，已达到整个序列有序。排序的时间复杂度为 O(nlogn)，相比于简单排序算法，运算效率大大提高。
 

public static void quickSort(int[] array, int low, int high) {
/**
* 1.选定一个基准值，array[low]
* 2.右指针从右向左遍历high--，查找比基准值小的数据，左指针从左向右low++，查找比基准值大的数据
* 3.如果指针未相遇，交换左右两值位置，如果指针相遇，则替换基准值的位置
* 4.左递归，右递归
*/
// 方法退出条件,指针相遇或错过
if (low >= high) {
return;
}
// 基准值和左右指针记录位置
int pivot = array[low];
int l = low;
int r = high;
int temp = 0;
// 遍历条件，左右指针位置
while (l < r) {
//右侧遍历
while (l < r && array[r] >= pivot) {
r--;
}
//左侧遍历
while (l < r && array[l] <= pivot) {
l++;
}
//l指针还在r指针左侧，尚未相遇
if (l < r) {
temp = array[l];
array[l] = array[r];
array[r] = temp;
}
}
//当左右指针相遇，交换基准值位置
array[low] = array[l];
array[l] = pivot;
//根据条件左侧递归遍历
if (low < l) {
quickSort(array, low, l - 1);
}
//根据条件右侧递归遍历
if (r < high) {
quickSort(array, r + 1, high);
}
}

时间复杂度

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。

可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法

最后

以上就是爱听歌寒风为你收集整理的java实现快速排序算法时间复杂度的全部内容，希望文章能够帮你解决java实现快速排序算法时间复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。