快速排序算法(JAVA版)

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

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;
	}



fatkun

7条评论

发表评论

电子邮件地址不会被公开。