/**
* 快速排序
* @param a
* @param low
* @param high
*/
public static void quickSort(int[] a, int low, int high) {
int l = low;
int h = high;
if (l >= h) {
return;
}
int temp = a[l];
// 此循环完成了一趟排序,将数组中小于temp的数放在左边,大于temp的元素放在右边
while (l < h) {
while (h > l && a[h] > temp) { // 从右往左扫描找到第一个小于temp的元素
h--;
}
if(l<h){
a[l] = a[h]; // 放在temp左边
l++; // i指针右移一位
}
while (l<h&& a[l] < temp) { // 从左往右扫描找到第一个大于temp的元素
l++;
}
if(l<h){
a[h] = a[l]; // 放在temp右边
h--; // h左移一位
}
}// end 一趟排序
a[l] = temp; // 将temp放在最终位置
quickSort(a, low, l-1); // 递归对temp左边元素进行排序
quickSort(a, l+1, high); // 递归对temp右边的元素进行排序
}
public static void main(String[] args) {
int[] a = { 5, 4, 3, 2, 1 };
quickSort(a, 0, a.length-1);
for (int num : a) {
System.out.print(num + " ");
}
}
时间复杂度:最好O(nlogn) 最差O(n*n) 平均O(nlogn)
空间复杂度:O(nlogn) 因为需要栈空间辅助
是否稳定:不稳定