快速排序

 

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

 

public static int[] QuickSort(int[] pData, int left, int right) {

		int i, j;
		int mid, k;

		i = left;
		j = right;
		mid = (left + right) / 2;
		k = pData[mid];

		// pData[left ... X - 1] < k 和 pData[X + 1 ... right] > k
		while (i <= j) {
			// 从left开始
			while (k > pData[i] && i < right) {
				i++;
			}
			// 从right开始
			while (k < pData[j] && j > left) {
				j--;
			}
			if (i <= j) {
				System.out.println(pData[i] + ":" + pData[j]);
				// i==j说明是一个数，不用交换
				if (i != j) {
					pData[i] += pData[j];
					pData[j] = pData[i] - pData[j];
					pData[i] = pData[i] - pData[j];
				}
				i++;
				j--;
			}
		}

		// 递归
		if (right > i) {
			QuickSort(pData, i, right);
		}
		if (j > left) {
			QuickSort(pData, left, j);
		}

		return pData;
	}