当前位置:   article > 正文

算法--快速排序(Java)_快速排序算法java实现1000个随机数

快速排序算法java实现1000个随机数

一、什么是快速排序

引用百度百科的解释:快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

二、快速排序实现过程

1、分析过程

首先,在这一串数字中挑一个基准数,作为排序的参考,将大于该基准数的数字放在后面,小于基准数的数字放在前面。

然后,这样一来,一串数字分成了两部分,左部分都比基准数小,右部分都比基准数大。接着,同样的方法,再分别从左右部分都挑出一个基准数,同样作为排序的参考,同样将大于该基准数的数字放在后面,小于基准数的数字放在前面。

以此类推,直至大小排序完成为止。

2、具体数字模拟过程

  • 假设有如下一串数字:“22,1,43,23,6,34,2,7,22,88,32,54”
  • 为了方便,我们将第一个数字22作为基准数。
  • 假设一“探针”从右往前遍历找到一个比22小的数,然后另一“探针”从左往右遍历找到一个比22大的数,交换它们位置。直到两“探针”相遇,此时左边的都比22小,右边的都比22大。
  • 然后将分割好数字串的按以上方法排序

a:右探针从右往左勘测,找到比22小的数,那么探针停在7位置上;

b:左探针从左往右勘测,找到比22大的数,那么探针停在43位置上;

c:交换7和43;
如下图:
在这里插入图片描述
继续a步骤:右探针找到比22小的数,探针停在了2位置上;
继续b步骤:左探针找到比22大的数,探针停在了23位置上;
继续c步骤:交换2和23
如下图:
在这里插入图片描述
继续a步骤:右探针找到比22小的数,探针停在了6位置上;
继续b步骤:左探针右移与右探针重合,发现6比22小,那么交换6和22
如下图:
在这里插入图片描述
最终,整串数字被22分割成两部分,左边全部比22小,右边全部比22大。
然后,以此类推,按照上述方法,将左右部分分别排序,如下左半部分排序:
在这里插入图片描述
同理,可得出右半部分排序。

三、快速排序代码实现和效率

1、代码

public static void main(String[] args) {
        int[] array = {22,1,43,23,6,34,2,7,22,88,32,54};
        int start = 0;
        int end = array.length - 1;
        quickSort(array, start, end);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    public static void quickSort(int[] a, int left, int right) {
        int start = left;
        int end = right;
        int key = a[left];
        while (end > start) {
            // 从后往前比较,如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置
            while (end > start && a[end] >= key)
                end--;
            if (a[end] <= key) {
                // 如果比基准数小交换位置
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // 从前往后比较,如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
            while (end > start && a[start] <= key)
                start++;
            if (a[start] >= key) {
                // 如果比基准数大交换位置
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            // 左右探针重合后,以基准值分为左右两部分,左边都比基准值小,右边都比基准值大
        }
        // 然后递归,直到排完所有数字
        if (start > left) quickSort(a, left, start - 1);
        if (end < right) quickSort(a, end + 1, right);
    }
  • 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

2、效率

快速排序(Quicksort)是对冒泡排序的一种改进。

那么以下是十万个随机数通过两种排序方式用时的对比:

(1)代码

 public static void main(String[] args) {
        int a[] = new int[100000];
        // 生成10万个随机数
        for (int i = 0; i < 100000; i++) {
            int num = (int) (Math.random() * 100000);
            a[i] = num;
        }
        int b[] = a;

        long l = System.currentTimeMillis();
        int start = 0;
        int end = a.length - 1;
        quickSort(a, start, end);
        System.out.println("100000个随机数快速排序用时 = " + (System.currentTimeMillis() - l));

        long s = System.currentTimeMillis();
        // 冒泡排序
        bubooSort(b);
        System.out.println("100000个随机数冒泡排序用时 = " + (System.currentTimeMillis() - s));
    }
    public static void quickSort(int[] a, int left, int right) {
        int start = left;
        int end = right;
        int key = a[left];
        while (end > start) {
            // 从后往前比较,如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置
            while (end > start && a[end] >= key)
                end--;
            if (a[end] <= key) {
                // 如果比基准数小交换位置
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // 从前往后比较,如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
            while (end > start && a[start] <= key)
                start++;
            if (a[start] >= key) {
                // 如果比基准数大交换位置
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            // 左右探针重合后,以基准值分为左右两部分,左边都比基准值小,右边都比基准值大
        }
        // 然后递归,直到排完所有数字
        if (start > left) quickSort(a, left, start - 1);
        if (end < right) quickSort(a, end + 1, right);
    }
    private static void bubooSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
  • 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

(2)输出结果

100000个随机数快速排序用时 = 58
100000个随机数冒泡排序用时 = 2884
  • 1
  • 2

在10万条数据时,所用时间长短显而易见,那么在大数据情况下,这种对比将更加明显。所以可以得出:快速排序是对冒泡排序的优化和改进。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/107035
推荐阅读
相关标签
  

闽ICP备14008679号