快速排序的java_快速排序(Java)

  • Post author:
  • Post category:java


1、普通快速排序

思想:

该方法运用了分治的思想,它将一个数组分成两个子数组,将两部分独立地排序,当两个子数组都有序时,整个数组也就自然有序了,其重点在于对数组进行切分。

图示:

切分轨迹

NUetQ.png

快速排序

NULuE.png

代码: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

61public class Quick {

public static void sort(Comparable[] a){

StdRandom.shuffle(a);

sort(a,0,a.length-1);

}

private static void sort(Comparable[] a,int lo,int hi){

if(hi<=lo)

return;

int j = partition(a,lo,hi);//切分

sort(a,lo,j-1);//左边部分排序

sort(a,j+1,hi);//右边部分排序

}

private static int partition(Comparable[] a,int lo,int hi){

int i =lo,j=hi+1;//左右扫描指针

Comparable v=a[lo];//切分元素

while(true){

//扫描左右,检查扫描是否结束并交换元素

while(less(a[++i],v))

if(i==hi)

break;

while(less(v,a[–j]))

if(j==lo)

break;

if(i>=j)

break;

exch(a,i,j);

}

exch(a,lo,j);//将v=a[j]放入正确的位置

return j;

}

private static boolean less(Comparable v,Comparable w){

return v.compareTo(w)<0;

}

private static void exch(Comparable[] a,int i,int j){

Comparable t = a[i];

a[i]=a[j];

a[j]=t;

}

private static void show(Comparable[] a){

for(int i=0;i

StdOut.print(a[i]+” “);

}

StdOut.println();

}

public static boolean isSorted(Comparable[] a){

for(int i=1;i

if(less(a[i],a[i-1]))

return false;

}

return true;

}

public static void main(String[] args) {

String[] a = In.readStrings();

sort(a);

assert isSorted(a);

show(a);

}

}

说明:主要是对partition函数进行分析,两个while循环用于对下标进行控制,以切分点为分割,一个从左向右,一个从右向左,其中有3个break条件,一个是左边走完,一个是右边走完,一个是左边部分的下标超过右边部分,最后就对满足要求的值进行交换,循环结束之后将切分的值进行交换完成整个排序。

时间复杂度:平均情况O(nlog2n),最坏O(n2),最好O(nlog2n)

空间复杂度:O(nlog2n)

稳定性:不稳定,可能会随着前后部分数值的调换而使两个相同数值的位置进行调换。

2、三向切分快速排序

思想:

它与快排的主要区别在于它适合处理重复元素较多的情况。这样就可以减少在已经选定切分元素的情况下,仍然将多个与切分元素相同的值放入子数组中进行排序。它维护了三个指针,lt指针使得a[lo…lt-1]中的元素都小于v(v为选定的切分元素),gt指针使得a[gt+1…hi]中的元素都大于v,而指针i使得a[lt…i-1]中的元素都等于v。

总共处理3种情况:

a[i]

a[i]>v,将a[gt]和a[i]交换,将gt减一

a[i]等于v,将i加一。

图示:

NUUw2.png

代码: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

51public class Quick3way {

public static void sort(Comparable[] a){

StdRandom.shuffle(a);

sort(a,0,a.length-1);

}

private static void sort(Comparable[] a,int lo,int hi){

if(hi<=lo)

return;

int lt=lo,i=lo+1,gt=hi;

Comparable v =a[lo];

while(i<=gt){

int cmp = a[i].compareTo(v);

if(cmp<0)

exch(a,lt++,i++);

else if(cmp>0)

exch(a,i,gt–);

else

i++;

}

sort(a,lo,lt-1);

sort(a,gt+1,hi);

}

private static boolean less(Comparable v,Comparable w){

return v.compareTo(w)<0;

}

private static void exch(Comparable[] a,int i,int j){

Comparable t = a[i];

a[i]=a[j];

a[j]=t;

}

private static void show(Comparable[] a){

for(int i=0;i

StdOut.print(a[i]+” “);

}

StdOut.println();

}

public static boolean isSorted(Comparable[] a){

for(int i=1;i

if(less(a[i],a[i-1]))

return false;

}

return true;

}

public static void main(String[] args) {

String[] a = In.readStrings();

sort(a);

assert isSorted(a);

show(a);

}

}

时间复杂度:平均情况O(nlog2n),最坏O(n2),最好O(nlog2n)

空间复杂度:O(nlog2n)

稳定性:不稳定,可能会随着前后部分数值的调换而使两个相同数值的位置进行调换。

这其中的StdOut、StdRandom以及StdIn库使用自algs4这个jar包,下载地址:

https://algs4.cs.princeton.edu/code/algs4.jar



版权声明:本文为weixin_39863008原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。