快排,顾名思义,就是很快的一种排序算法。
核心就是:每次排序的时候,设置一个基准点,将小于等于基准点的放左边,大于等于基准点的放右边,跳跃式交换。基于“二分”的一种思想。
但快排也有最坏情况,就是基准值选到最大或最小,导致数据跑到一边,最差时间复杂度是O(N2),平均时间复杂度为O(NlogN)。
思路:
选最左作为基准,
用 j 从右往左遍历,如果比基准大,继续,比基准小,停,
用 i 从左网游遍历,如果比基准小,继续,比基准大,停,
然后交换 i 和 就 j 处的值,交换之后接着走,直到 i = j;
将基准和 i 处值交换,一轮就结束了,
然后在通过递归,左边和右边继续上诉步骤,
直至左边不小右边,排序就结束了。
自己在本子上手动模拟一下就明白了。
注意:因为选择左边作为基准,所以要从右往左遍历,这样可以保证左边全最小,右边全最大。
代码:
复制代码
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56public class QuickSort { //快排,基于二分思想的算法 public static void quickSort(int arr[], int left, int right) { int i, j, t, temp; //如果左边大于右边,直接返回 if (left > right) return; //用temp保存一下left位置的数,temp作为基准 temp = arr[left]; i = left; j = right; //当左和右没有碰头时候 while (i != j) { //顺序很重要,要先从右往左 while (arr[j] >= temp && i < j) j--; while (arr[i] <= temp && i < j) i++; //当上边两个while跑出来,如果i<j,交换i和j处的值 if (i < j) { t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } //此时交换left和i处值 arr[left] = arr[i]; arr[i] = temp; //从上边跑到这里,说明一轮交换完成了, //i处左边小于i处的值和右边大于i处的值 //递归,处理左边的 quickSort(arr, left, i - 1); //递归,处理右边的 quickSort(arr, i + 1, right); } public static void main(String[] args) { int [] arr = {6,1,2,7,9,5}; quickSort(arr, 0, arr.length - 1); //输出 int len = arr.length; for (int i = 0; i <len; i++) { System.out.println(arr[i]); } } }
最后
以上就是爱笑钢笔最近收集整理的关于快速排序算法的全部内容,更多相关快速排序算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复