package Java;
public class QuickSort {
/**
* 时间复杂度O(nlogn)
* 空间复杂度O(logn)递归需要栈的辅助
* 最坏时间复杂度O(n^2)
* @param nums
* @param start
* @param end
*/
public static void QuickSort(int[] nums, int start, int end) {
int i = start;
int j = end;
if (start >= end) {
return;
}
int temp = nums[i];
while (i < j) {
//从右往左扫描，找到小于temp的值
while (i < j && nums[j] >= temp) {
j--;
}
//找到小于temp的值，将其赋值给nums[i]，并将i向右移一位。
if (i < j) {
nums[i] = nums[j];
i++;
}
//从左往右扫描，直到找到大于temp的值
while (i < j && nums[i] <= temp) {
i++;
}
//找到大于temp的值，将其赋值给nums[j]，并将j往左移一位。
if (i < j) {
nums[j] = nums[i];
j--;
}
}
//最后是temp的值
nums[i] = temp;
//递归将temp左边的数组排序
QuickSort(nums, start, i - 1);
QuickSort(nums, i + 1, end);
//递归将temp右边的数组排序
}
public static void main(String[] args) {
int[] nums = {6,89,2,11,3,79,51,19,87};
QuickSort(nums, 0, nums.length - 1);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
}
}
QuickSort
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
