fatkun's blog

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

	/*
	 * 快速排序：选一个值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;
	}

/* * 快速排序：选一个值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; }