手撕快排
复杂度和稳定性
时间复杂度:
- 最好:O(nlog2n)
- 最坏:O(n^2)
- 平均:O(nlog2n)
空间复杂度:O(log2n)
稳定性:不稳定
Java代码
public class QuickSort {
int[] sortByRecursion(int[] array, int l, int r) {
if(l == r) { // 如果当前数组只有一个值,直接返回
return array;
}
int left = l, right = r; // 定义左右指针
int temp = array[l]; // 备份分治点
boolean flag = false; // false:左指针不动,右指针动左移,←right true:右指针不动,左指针右移,left→
while (left != right) {
if (flag) { // 右指针不动
if (array[left] > temp) { // 如果左侧数字大于右侧数字
array[right] = array[left]; // 右侧数字赋值为左侧数字
flag = false; // 指针换动
} else { // 如果左侧数字不大于右侧数字
left++; // 左指针右移
}
} else { // 左指针不动
if (array[right] < temp) { // 如果右侧数字小于左侧数字
array[left] = array[right]; // 左侧数字赋值为右侧数字
flag = true; // 指针换动
} else { // 如果如果右侧数字不小于左侧数字
right--; // 右指针左移
}
}
}
array[left] = temp; // 把分治点赋值
if (l < left - 1) { // 递归,将分治点左侧的数组一次快排
array = sortByRecursion(array, l, left - 1);
}
if (right + 1 < r) { // 递归,将分治点右侧的数组一次快排
array = sortByRecursion(array, right + 1, r);
}
return array;
}
public static void main(String[] args) {
QuickSort qs = new QuickSort();
int[] arr = {5,6,89,7,48,15,65,32,8,15,84,9,33,4,
3,14,74,15,84,96,1,62,84,2,36,15,47,82,41,64,0,61};
arr = qs.sortByRecursion(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}