java冒泡排序和快速排序

一、冒泡排序

1.算法介绍

设排序表长为n,从后向前或者从前向后两两比较相邻元素的值,如果两者的相对次序不对(A[i-1] > A[i]),则交换它们,其结果是将最小的元素交换到待排序序列的第一个位置,我们称它为一趟冒泡。下一趟冒泡时,前一趟确定的最小元素不再参与比较,待排序序列减少一个元素,每趟冒泡的结果把序列中最小的元素放到了序列的”最前面”。

2.算法实现

冒泡排序封装函数的代码如下

public void bubbleSort(int[] arr) {
    int temp;//定义一个临时变量
    for(int i=0;i<arr.length-1;i++){//冒泡趟数
        for(int j=0;j<arr.length-i-1;j++){
            //如果顺序不对,则交换两个元素
            if(arr[j+1]<arr[j]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

测试代码如下

public static void main(String[] args) {
    Test t = new Test();
    int arr[] = new int[]{13,26,22,22,35,18};
    t.bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

运行结果如下

[13, 18, 22, 22, 26, 35]

3.算法分析

冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1),它是一种稳定的排序算法。当然了,这也是非常基础的一种算法,一般找工作有些公司喜欢出笔试题。

下面我们来看看java中的Arrays.sort(int []a)方法是怎么实现的。


二、快速排序

java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。

快速排序主要是对哪些基本类型数据(int,short,long等)排序, 而合并排序用于对对象类型进行排序。

使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型,稳定性没有意义,而对于对象类型,稳定性是比较重要的,因为对象相等的判断可能只是判断关键属性,最好保持相等对象的非关键属性的顺序与排序前一直;另外一个原因是由于合并排序相对而言比较次数比快速排序少,移动(对象引用的移动)次数比快速排序多,而对于对象来说,比较一般比移动耗时。

1.实现原理

java1.7之后的版本,开始用双轴快排取代了以前的排序算法,现在只实现了8种基本数据类型性的双轴快排,对象的排序在1.7中还在用老式的,不过都标了过时,估计以后版本中就会被新的双轴快排取代了。

他的DualPivotQuicksort()方法,里边一共写了三种算法(不算改进版的插入排序话),对于大数组而且部分高度有序的用归并排序,其余的用双轴快排进行分割, 分割到足够小的时候用插入排序(主要是改进版的pair insertion sort)。

双轴快排的基本原理是取两个pivot,所有比pivot1小的放到最左边,比pivot2大的放到最右边,然后递归下去,就可以把两端的元素完成排序,之后处理中间部分,中间部分如果过大就继续递归用这种方式继续分割,如果不大,就用单轴分割对两部分递归调用下去。

2.实现代码

代码截取自jdk1.7中的Arrays类

/**
 * Sorts the specified range of the array.
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 */
public static void sort(int[] a, int left, int right) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }

    /*
     * Index run[i] is the start of i-th run
     * (ascending or descending sequence).
     */
    int[] run = new int[MAX_RUN_COUNT + 1];
    int count = 0; run[0] = left;

    // Check if the array is nearly sorted
    for (int k = left; k < right; run[count] = k) {
        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                if (--m == 0) {
                    sort(a, left, right, true);
                    return;
                }
            }
        }

        /*
         * The array is not highly structured,
         * use Quicksort instead of merge sort.
         */
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);
            return;
        }
    }

    // Check special cases
    if (run[count] == right++) { // The last run contains one element
        run[++count] = right;
    } else if (count == 1) { // The array is already sorted
        return;
    }

    /*
     * Create temporary array, which is used for merging.
     * Implementation note: variable "right" is increased by 1.
     */
    int[] b; byte odd = 0;
    for (int n = 1; (n <<= 1) < count; odd ^= 1);

    if (odd == 0) {
        b = a; a = new int[b.length];
        for (int i = left - 1; ++i < right; a[i] = b[i]);
    } else {
        b = new int[a.length];
    }

    // Merging
    for (int last; count > 1; count = last) {
        for (int k = (last = 0) + 2; k <= count; k += 2) {
            int hi = run[k], mi = run[k - 1];
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                if (q >= hi || p < mi && a[p] <= a[q]) {
                    b[i] = a[p++];
                } else {
                    b[i] = a[q++];
                }
            }
            run[++last] = hi;
        }
        if ((count & 1) != 0) {
            for (int i = right, lo = run[count - 1]; --i >= lo;
                b[i] = a[i]
            );
            run[++last] = right;
        }
        int[] t = a; a = b; b = t;
    }
}

3.源码分析

源码中的快速排序,主要做了以下几个方面的优化:

  1)当待排序的数组中的元素个数较少时,源码中的阀值为7,采用的是插入排序。尽管插入排序的时间复杂度为0(n^2),但是当数组元素较少时,插入排序优于快速排序,因为这时快速排序的递归操作影响性能。

  2)较好的选择了划分元(基准元素)。能够将数组分成大致两个相等的部分,避免出现最坏的情况。例如当数组有序的的情况下,选择第一个元素作为划分元,将使得算法的时间复杂度达到O(n^2).

源码中选择划分元的方法:

    当数组大小为 size=7 时 ,取数组中间元素作为划分元。int n=m>>1;(此方法值得借鉴)

    当数组大小 7<size<=40时,取首、中、末三个元素中间大小的元素作为划分元。

    当数组大小 size>40 时 ,从待排数组中较均匀的选择9个元素,选出一个伪中数做为划分元。

  3)根据划分元 v ,形成不变式 v* (<v)* (>v)* v*

  普通的快速排序算法,经过一次划分后,将划分元排到素组较中间的位置,左边的元素小于划分元,右边的元素大于划分元,而没有将与划分元相等的元素放在其附近,这一点,在Arrays.sort()中得到了较大的优化。

最后,如果你有仍何开发上面的问题都可以和我交流沟通。

原文发布于微信公众号 - java工会(javagonghui)

原文发表时间:2018-04-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

2975
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

1979
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

3736
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

3307
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1363
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

832
来自专栏数据结构与算法

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

2588
来自专栏AI派

Numpy 修炼之道 (2)—— N维数组 ndarray

ndarray中的每个元素在内存中使用相同大小的块。 ndarray中的每个元素是数据类型对象的对象(称为 dtype)。

3486
来自专栏蜉蝣禅修之道

算法考试填数字问题

1772
来自专栏赵俊的Java专栏

LeetCode 557 Reverse Words in a String III

首先按照空格对字符串进行分隔,然后将每个单词进行翻转后再拼接回字符串即可,需要注意拼接时记得加空格,但最后一个单词不需要加。

661

扫码关注云+社区