【基本思想】

快速排序在元素较多的情况下,排序效率是相当高的。其基本思想是这样:

假设数组为int[] arr = { 49, 38, 65, 97, 76, 13, 27, 22, 26, 41, 13, 17, 32 },数组元素个数为13个。

选定a[0]为left标记,a[12]为right标记,基准点pivot的初始位置一般也为a[0](其值记为p)。

定义i,j分别代表了不断变化的left和right标记。

此时,先让基准点归位。即以p为基准,左侧元素均小于p,右侧元素均大于p。

具体即为:

1.左标记不断右移,比较p与所在位置元素的大小,若比p大,停止比较,记下此点;

2.右标记不断左移,比较p与所在位置元素的大小,若比p小,停止比较,记下此点;

3.交换左右标记;

4.直至左右标记重合,这个位置就是基准点的位置。

然后被基准点分开的这两小段序列重复上述步骤。

【代码实现】

 1     public static void quickSort(int[] arr, int left, int right) { 
 2         // 如果left不小于right,需要排序的部分只有一个元素,方法结束调用。 
 3         if (left >= right) { 
 4             return; 
 5         } 
 6         // 将最左侧的元素设置为pivot(基准点) 
 7         int p = arr[left]; 
 8         // 把比p小的放到左边,比p大的放到右边。 
 9         int i = left, j = right; 
10         while (i < j) { 
11             // j向左移,找到一个比p小的元素。 
12             while (arr[j] >= p && i < j) { 
13                 j--; 
14             } 
15             // i向右移,找到一个比p大的元素。 
16             while (arr[i] <= p && i < j) { 
17                 i++; 
18             } 
19             // i和j交换。 
20             if (i < j) { 
21                 int temp = arr[i]; 
22                 arr[i] = arr[j]; 
23                 arr[j] = temp; 
24             } 
25         } 
26         // 让基准点归位,此时i与j是相同的,用谁都行。 
27         arr[left] = arr[i]; 
28         arr[i] = p; 
29         // 基准点左侧序列的元素递归进行快速排序。 
30         quickSort(arr, left, i - 1); 
31         // 基准点右侧序列的元素递归进行快速排序。 
32         quickSort(arr, i + 1, right); 
33     }

发布评论
IT序号网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Java中常见的排序方式-选择排序(升序)知识解答
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。