转载

Java排序理解增强版

前言：干了好多年java，由于平时干的都是搬砖工，平时也接触不好烧砖的技术活，所以不晓得砖怎么烧制，白干了这么多年！

冒泡排序：

冒泡排序就是将两两相邻的记录关键字进行比较，反序则调换值，直至到没有反序出现。从大神哪里盗了几张图片，容易理解：

排序前

排序中

排序后

废话不说上代码（直到为什么没是图片吗？我怕我下次copy）：

总结：由于冒泡排序每相邻的两个参数就要比较，所以性能很一般,平均时间复杂度为O(N2)，所以不建议使用。可使用快速排序代替！参考地址：孔乙己学习成长录

快速排序

快速排序是指的选取一个基准值X，然后先从右往左寻找小于X的第一个值，再从左至右寻找大于X的第一个值，将两个值交换位置，持续这样循环，直至左右移动到同一个位置，基准值和此位置交换，此时交换得到了两个序列，基准值左边为小于基准值的值，基准值右边为大于基准值的值，然后采用所谓的二分法进行分别排序（还是上面的方法：交换数据）。继续copy生动的图片来演示：

i和j两位帅哥开始站位在左右两边

基准为6，左找大于等于6的值，右找小于等于6的值

交换后

不离不弃继续找并且交换

找完了，幸福的走到了一起

把基准值和最后位置互换

得到了排序的第一版

可以看出6左边都小于等于它，右边都大于等于他，现在分为两个无序序列，分别按照上面的流程排序，得到最总有序数组。

ps：快速排序是对冒泡排序的优化，因为快速排序是两两交换的距离增大，交换次数少，所以效率提升很多，最差时间复杂度=冒泡时间复杂度，一般时间复杂度为：O(NLOGN)，并且用到了二分思想

一样的，上代码，自己写哦

package com.zwj.java;

/**
 *@author 少林寺三毛
 * 快速排序 找到一个基准值X（一般是获取数组第一个数字），通过和右边比较X，找到比X小则停住，然后做边进行比较X，如果找到大于X则停住，
 * 交换两个数据位置，往而复失，直到X左边小于X，X右边值大于X，在采用此方法对做面方法进行排序，然后对右边开始排序，得到最终结果
 */
public class QuickSort {

    /**
     * 快速排序实现
     * @param numbers 待排序的数组
     * @param start 基准值索引值，一般是第一个
     * @param end 右边最后一个值的索引值
     */
    public static void quick(Integer[] numbers, int start, int end){
        int i,j,t,temp;
        if (start > end){
            return;
        }
        i = start;
        j = end;
        temp = numbers[i];
        while (i < j){
            //先看右边，找到小于等于temp基准值后停留
            while (temp <= numbers[j] && i < j){
                j--;
            }
            while (temp >= numbers[i] && i < j){
                i++;
            }
            if (i < j){
                t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
            //当i与j相等时，则基准值temp与x、y相等下标的值相互交换
            numbers[start] = numbers[i];
            numbers[i] = temp;
            //递归调用左边半数据
            quick(numbers,start,j - 1);
            //递归调用右边半数据
            quick(numbers,j + 1,end);
        }
    }

    public static void main(String[] args) {
        Integer[] numbers = {10,6,7,1,6,3,2,1,8,5,4};
        quick(numbers,0,numbers.length-1);
        for (Integer i : numbers){
            System.out.println(i);
        }
    }
}

复制代码

参考地址：脚丫先生

原文 https://juejin.im/post/5be9b02651882516d725ba55

正文到此结束