快速排序

发表于 | 分类于 | | 次阅读

Java数据结构与算法–快速排序

1.快速排序思想与原理

快速排序是综合性无序排序比较强的方法，但对于基本有序的数组，快排就慢的很多

1.1基本思想：

通过一趟排序将数据分割为前后两个部分，第一部分所有数据比第二组小（前面）然后分别继续快排，使用递归实现。

1.2时间复杂度与空间复杂度

平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
O(n log n) O(n log n) O(n^2) O(log n) 内部排序 不稳定

1.3原理

就是在一组数据中找到一个轴值（一般是第一个数），然后从后往前扫，在待排数据中比轴值小的数放在待排数据的前面，然后从前往后扫，比轴值大的放在数据后面。然后左右大致已经分好大小区域，这时使用递归将左右元素继续排序。下面代码中教材代码为：49、38、65、97、76、13、27。其实是数据结构课的作业稍作修改。

算法代码：

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
//快排方法
    public void sort(){
        quicksort(qsort,0,qsort.length-1);
    }
    //方法
    private void quicksort(int[] qsort,int low,int high){
        this.qsort=qsort;
        if(low<high){//当i和j没相遇时
        int pivotkey=qsort[low];//取第一个元素作为轴值
        int i=low;
        int j=high;
//开始从右往左扫描
            while (i < j){
                while(i < j && qsort[j] > pivotkey){//遇到比轴值大的，继续往前移动
                    j--;
                }
                if(i < j){//找到比轴值小的，交换当前的两组数据，然后开始从左扫描
                    qsort[i]=qsort[j];
                    i++;
                }
//从左扫描
                while (i < j && qsort[i] < pivotkey){//遇到比轴值小的，继续移动
                    i++;
                }
                if(i < j){//找到比轴值大的，交换当前两组数据，开始从右扫描
                    qsort[j]=qsort[i];
                    j--;
                }
            }
            qsort[i]=pivotkey;//把轴值放到轴的位置
            quicksort(qsort,low,i-1);//左侧按照快排，递归
            quicksort(qsort,i+1,high);//右侧按照快拍，递归
        }
    }

然后测试代码中，为了熟悉Java中的Scanner类，就修改了一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class QuickSort {//测试代码
    public static void main(String[] args){
        /*选择*/
        System.out.println("请选择要执行快排的选项：\n1.输入数组\n2.使用教材数组");
        Scanner n=new Scanner(System.in);
        int a=n.nextInt();
        switch (a){
            case 1:
                ScannerSort();
                break;
            case 2:
                testQuickSort();
                break;
        }

    }

输入代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*输入数组*/
   private static void ScannerSort(){
       System.out.println("请输入十组数据；");
       int a=10;
       int[] sqsort=new int[a];
       Scanner sc=new Scanner(System.in);
       for (int i = 0; i < a; i++) {
           sqsort[i]=sc.nextInt();
       }
       Qsort qs=new Qsort(sqsort);
       System.out.println("输入的数组为：");
       for (int j = 0; j < sqsort.length; j++) {
           System.out.print(" "+sqsort[j]+" ");
       }
       System.out.print("\n");
       System.out.println("快排中...");
       qs.sort();
       System.out.println("快排后：");
       qs.printSort();
   }

教材代码：

1
2
3
4
5
6
7
/*教材数组*/
    private static void testQuickSort(){
        int[] qsort={49,38,65,97,76,13,27};
        Qsort qs=new Qsort(qsort);
        qs.sort();
        qs.printSort();
    }

最后附上全套粘贴就能用的代码（QuickSort.java）:

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
import java.util.Scanner;//导入Scanner类

class Qsort{
    private int[] qsort;//创建数组

    public Qsort(int[] qsort){
        this.qsort=qsort;
    }
    //输出
    public void printSort(){
        for (int i = 0; i < qsort.length; i++) {
            System.out.print(" "+qsort[i]+" ");
        }
    }
    //快排方法
    public void sort(){
        quicksort(qsort,0,qsort.length-1);
    }
    //方法
    private void quicksort(int[] qsort,int low,int high){
        this.qsort=qsort;
        if(low<high){//当i和j没相遇时
        int pivotkey=qsort[low];//取第一个元素作为轴值
        int i=low;
        int j=high;
//开始从右往左扫描
            while (i < j){
                while(i < j && qsort[j] > pivotkey){//遇到比轴值大的，继续往前移动
                    j--;
                }
                if(i < j){//找到比轴值小的，交换当前的两组数据，然后开始从左扫描
                    qsort[i]=qsort[j];
                    i++;
                }
//从左扫描
                while (i < j && qsort[i] < pivotkey){//遇到比轴值小的，继续移动
                    i++;
                }
                if(i < j){//找到比轴值大的，交换当前两组数据，开始从右扫描
                    qsort[j]=qsort[i];
                    j--;
                }
            }
            qsort[i]=pivotkey;//把轴值放到轴的位置
            quicksort(qsort,low,i-1);//左侧按照快排，递归
            quicksort(qsort,i+1,high);//右侧按照快拍，递归
        }
    }
}

public class QuickSort {//测试代码
    public static void main(String[] args){
        /*选择*/
        System.out.println("请选择要执行快排的选项：\n1.输入数组\n2.使用教材数组");
        Scanner n=new Scanner(System.in);
        int a=n.nextInt();
        switch (a){
            case 1:
                ScannerSort();
                break;
            case 2:
                testQuickSort();
                break;
        }

    }
    /*教材数组*/
    private static void testQuickSort(){
        int[] qsort={49,38,65,97,76,13,27};
        Qsort qs=new Qsort(qsort);
        qs.sort();
        qs.printSort();
    }
    /*输入数组*/
    private static void ScannerSort(){
        System.out.println("请输入十组数据；");
        int a=10;
        int[] sqsort=new int[a];
        Scanner sc=new Scanner(System.in);
        for (int i = 0; i < a; i++) {
            sqsort[i]=sc.nextInt();
        }
        Qsort qs=new Qsort(sqsort);
        System.out.println("输入的数组为：");
        for (int j = 0; j < sqsort.length; j++) {
            System.out.print(" "+sqsort[j]+" ");
        }
        System.out.print("\n");
        System.out.println("快排中...");
        qs.sort();
        System.out.println("快排后：");
        qs.printSort();
    }
}
0%