手撕快速排序-Java代码

手撕快排

复杂度和稳定性

时间复杂度：

1. 最好：O(nlog2n)
2. 最坏：O(n^2)
3. 平均：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] + " ");
		}
	}
}