快速排序

快速排序。基于比较的排序中基本上最快的算法O(nlgn)。数据基本有序且每次取第一个元素作划分点（含基本相同）时将遭遇“最坏”情形，时间复杂度为O(n^2)。换言之数据越乱越高效。缺点：非稳定排序。

	public void q_sort(int[] arr, int from, int to) {
		if (arr == null || arr.length == 0 || to < 0 || from < 0) {
			return;
		}
		if (from >= to) {
			return;
		}
		if (to - from < 50) {////数据量少于50,采取直接插入排序
			for (int i = from + 1; i <= to; i++) {
				int temp = arr[i];
				int j = i;
				for (; j > from; j--) {
					if (arr[j - 1] > temp) {
						arr[j] = arr[j - 1];
					} else {
						break;
					}
				}
				arr[j] = temp;
			}
			return;
		}
		int middle = partion(arr, from, to);
		q_sort(arr, from, middle - 1);
		q_sort(arr, middle + 1, to);
	}
	private int partion(int[] arr, int from, int to) {
		int middle = (from + to) / 2;
		if (arr[from] > arr[middle]) {
			swap(arr, from, middle);
		}
		if (arr[middle] > arr[to]) {
			swap(arr, middle, to);
		}
		if (arr[from] < arr[middle]) {
			swap(arr, from, middle);
		}
		int temp = arr[from];//三路取中法，使分拆后2个子数组规模大致相同。
		while (from < to) {
			while (from < to && arr[to] > temp) {
				to--;
			}
			if (from < to) {
				arr[from] = arr[to];
				from++;
			}
			while (from < to && arr[from] < temp) {
				from++;
			}
			if (from < to) {
				arr[to] = arr[from];
				to--;
			}
		}
		arr[from] = temp;
		return from;
	}

	public void swap(int[] arr, int start, int middle) {
		arr[start] = arr[start] ^ arr[middle];
		arr[middle] = arr[middle] ^ arr[start];
		arr[start] = arr[start] ^ arr[middle];
	}