快速排序让我看了很久,也折磨了我很长时间,因为大体上的思路我是有了,但是写代码时总是出现各种问题,要想把它调试出来对我个人来说还是有一定难度的,而且因为工作和偷懒的原因,导致之前调试不出来的错误放了很久,今天终于出来啦,还是有些小激动的哦,下面来分享一下我的代码并做一点点说明。
要学会快速排序,就必须先要学会分治法,分治的思想是给一串乱序的数字(数字是假设,也可以是其他的对象,当然方法的参数可以自己定义哦,我在这里假设有一个整型的数组吧)然后给他一个中间数,分治法会把这些数字以给他的那个是中间数为分界分为两部分,一部分在中间数的左边,另一部分在右边,以这个数为分界点,两边的数现在还是乱序的,我给他定义的方法如下:
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
|
//left是数组的想分治部分的左端点,right是数组分治部分的总端点,如长度为10的数组,我想对前5个整数进行分治,则传0,4即可 public int signalFenZhi( int left, int right){ if (left< 0 ||left>n- 1 ||right< 0 ||right>n- 1 ){ return - 1 ; } int temp = test[left]; int j=right; int i=left; while (i<j){ while (test[j]>=test[left]&&i<j){ j--; } while (test[i]<=test[left]&&i<j){ i++; } if (i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; } } if (i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } for ( int m= 0 ;m<n;m++){ System.out.print(test[m]+ " " ); } return i; } |
当然,也可以把那个中间数当参数传进来,现在我只是单纯的以数组的传进来的第left数做为分界数,这只是为了说明。
明白了分治,那么快速排序也就简单了,那就是对已经分为两部分的数再进行分治,依次类推,直到全部的数字都有序为止,代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
public void quickSort( int left, int right){ if (right-left< 1 ){ return ; } else { int point = this .signalFenZhi(left, right); System.out.println(point); //if(point!=left&&point!=right){ quickSort(left,point- 1 ); quickSort(point+ 1 ,right); //} } } |
快速排序的效率在众多的排序算法中是很优秀的,时间复杂度为O(N*log2n),但是如果分治的分界点选的不好的话,时间复杂度将会降到(n的平方),因为如果正好这个数组是有序的,然后我们每次都取传过来的最左端的数,那么效率就会很低,所以要避免发生这种情况,如果检测所有的选项,那么将会很花时间,所以一个折中的办法 ,就是把最左端的数和最右端的数加上一个中间的数,找到他们三个中间的数,以这个为分界值就会变的好一点,在上面方法的基础上,修改以后的代码如下,但是我做完了以后这样的做法不是很好,应该把分界值也当做传给分治的方法会好些,细心的朋友可以自己试一下,我在这里就不试了哈,大体上是一样的哦!
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
package com.jll; public class FenZhi { int [] test; int n= 10 ; public FenZhi(){ test = new int [ 10 ]; for ( int i= 0 ;i<n;i++){ test[i]=( int )(Math.random()* 100 )+ 1 ; System.out.print(test[i]+ " " ); } System.out.println(); } public FenZhi( int n){ if (n> 0 ){ this .n=n; test = new int [n]; for ( int i= 0 ;i<n;i++){ test[i]=( int )(Math.random()* 100 )+ 1 ; } } } public int signalFenZhiMajorizationFirst( int left, int right){ if (left< 0 ||left>n- 1 ||right< 0 ||right>n- 1 ||left>=right){ return - 1 ; } if (right-left>= 2 ){ int middle = (right+left)/ 2 ; if (test[left]>test[middle]){ int temp = test[middle]; test[middle] = test[left]; test[left] = temp; } if (test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; test[right] = temp; } if (test[middle]>test[right]){ int temp = test[middle]; test[middle] = test[right]; test[right] = temp; } int temp = test[middle]; test[middle] = test[left]; test[left] = temp; int j=right- 1 ; int i=left+ 1 ; while (i<j){ while (test[j]>=test[left]&&i<j){ j--; } while (test[i]<=test[left]&&i<j){ i++; } if (i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; } } if (i==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } /*if(i==j){ temp = test[middle]; test[middle]=test[i]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" "); }*/ return i; } else { if (test[right]<test[left]){ int temp = test[right]; test[right] = test[left]; test[left] = temp; } return right; } } public void quickSortMajorizationFirst( int left, int right){ if (right-left< 1 ){ return ; } else { int point = this .signalFenZhiMajorizationFirst(left, right); System.out.println( "the point is:" +point); quickSortMajorizationFirst(left,point- 1 ); quickSortMajorizationFirst(point+ 1 ,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out.println(f.signalFenZhiMajorizationFirst( 0 , 9 )); System.out.println(); f.quickSortMajorizationFirst( 0 ,f.n- 1 ); //f.quickSort(0,f.test.length-1); for ( int i:f.test){ System.out.print(i+ " " ); } } } |
代码运行如下:
1
2
3
4
5
6
7
8
9
10
|
95 40 64 18 78 23 73 84 40 the point is: 4 the point is: 1 the point is: 3 the point is: 7 the point is: 6 the point is: 9 18 23 40 40 64 73 78 84 95 |
以上就是我学习到的东西,记录一下,以备后面查阅。