FilesExpand file tree

 master

/

SimpleQuickSort.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

48 lines (46 loc) · 1.46 KB

 master

/

SimpleQuickSort.java

Top

File metadata and controls

• Code
• Blame

48 lines (46 loc) · 1.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package sort;

import java.util.Arrays;

import java.util.Random;

/*

* 单路快速排序

* 由于 单路快速排序仰仗于目标的既定数组的初始排序情况（取基数是只取序列的第一个数），最好时Ω(nlogn)，最坏时Ω(n^2)

* 所以我们改变取基数的方法，使用随机数来取基数

* */

public class SimpleQuickSort {

public static void main(String[] args) {

int a[]={5,6,9,1,7,6,2,3,8};

new SimpleQuickSort().quickSort(a,0,8);

System.out.println(Arrays.toString(a));

}

public void quickSort(int [] nums,int start,int end){

//选择基数 0

if (start<end){

int index=swapNums(nums,start,end);

quickSort(nums,start,index-1);

quickSort(nums,index+1,end);

}

}

//返回基数排序交换后的索引

public int swapNums(int [] a,int left,int right){

int i=left;

int j=right;

//产生随机数之后，向头部或者尾部交换基数，因为目的是交换除了基数的某个特定区域的序列

int temp=a[new Random().nextInt(right-left+1)+left];

int leftNum=a[left];

a[left]=temp;

temp=leftNum;

while(i<j)

{

while(i<j && a[j]>=temp)

j--;

if(i<j)

a[i]=a[j];

while(i<j && a[i]<=temp)

i++;

if(i<j)

a[j]=a[i];

}

a[i]=temp;

return i;

}

}