快速排序算法(JAVA版)

快速排序是不稳定的排序方法，平均时间复杂度为O(nlogn)，空间复杂度为O(logn)，最差时是有序或基本有序时，算法退化为冒泡排序，时间复杂度是O(n²)

/*
	 * 快速排序：选一个值pivokey(一般是第一个),小于pivokey放在左边，大于pivokey放在右边，分成两个序列，递归直到low >= high
	 * 步骤：
	 * 1，设定两个指针low,high。初值是0和数组长度-1，指定关键字pivokey
	 * 2，从high所指的位置向前找，找到一个比pivokey小的，和关键字交换值(arr[low] = arr[high])
	 * 3，从low所指的位置向后找，找到一个比pivokey大的，和关键字交换值
	 * 4，直到low>=high，把关键字赋值arr[low]=pivokey
	 * 5，递归分出的两个序列[lowStart,low-1]  [low+1,highEnd]
	 * */
	int[] quickSort(int[] arr, int low, int high) {
		//为后面的递归使用
		int lowStart = low;
		int highEnd = high;
		if (low < high) {
			int pivokey = arr[low];
			while (low < high) {
				//如果都是大于pivokey，high指针往前移
				while (low < high && arr[high] > pivokey) {
					high--;
				}
				//这里low++是先把arr[low]赋值为arr[high]，再low+=1，因为这个值是比pivokey小的，下一次不用比较了
				if (low < high)
				arr[low++] = arr[high];
				//如果都是小于pivokey，low指针往后移
				while (low < high && arr[low] < pivokey) {
					low++;
				}
				//这里的high--和上面同理
				if (low < high)
				arr[high--] = arr[low];
			}
			arr[low] = pivokey;
			quickSort(arr, lowStart, low - 1);
			quickSort(arr, low + 1, highEnd);
		}
		return arr;
	}