快速掌握Java 常用的排序算法

简单的看一下关于常用的排序结构，如图

本章代码重点实现： 插入排序 、选择排序、交换排序 这三类。

冒泡排序

原理：一次性用两个元素进行比较，如果小/大的就交换。走访数列的工作是重复地进行直到没有再需要交换位置。

代码：

/**
 * 冒泡排序
 * 
 * @author cjl
 *
 */
public class BubblingSort {

    public int[] BubblingSort(int[] res) {
        for (int i = 0; i < res.length; i++) {

  // 设置循环的次数
            for (int j = 0; j < res.length - i - 1; j++) {

  // 排序次数
                if (res[j] > res[j + 1]) {

  // 判断第一个值是否》大于第二个值
                    // 交换两个值就行
                    int temp = res[j]; // 先找一个值记录其中一个值
                    res[j] = res[j + 1];// 把大的值赋值过去
                    res[j + 1] = temp;// 替换位置
                }
            }
        }
        return res;
    }
}

快速排序

快速排序 流程方法:

1. 设置一个基数，通常默认第一个排序。
2. 【顺序逻辑】从后往前比较，基数小于等于后面的值，把该数放在基数对应的位置上（前一个位置坑里）从前往后比较，基数大于前面某个值，把该数放在基数对应的位置上（前一个位置坑里）。
3. 【倒序逻辑】 从后往前比较 ，基数大于后面的值，把该数放到基数对应的位置上（前一个位置坑里），从前往后比较，基数小于等于某个值，把该数放在基数对应的位置上（前一个位置里面）
4. 循环 2.3 步骤

通过图我详细解释一下：

绿色位置 是设置的当前基础值【坑位1】。黄色表示的是坑位。顶上粉红色和蓝色表示 移动游标位置

1、 从后往前比较 比较小于基础值。 5 这个数先从后往前 比较 ，0小于5 因此0 下面挖一个坑2此时将 坑位2 对应 0这个数放到坑位1 对应的数上。
2、 从前往后比较 比较大于等于基础值。 9大于5 挖坑，坑位3，把坑位3对应数字9 填入之前坑位2的位置。
3、 当前最顶部两个游标贴在一起的时候，此时7 坑位 没有数字，把基数放到当前7坑位对应数值下 如图 蓝色5表示。

4、 此时数组就分成3 部分 黄色 + 基数+绿色，再次递归黄色部分 或者绿色部分。每次递归的时候 主要找到 黄色和红色基础值的位置

/**
 * 快速排序
 * <li> 【顺序】  基数大于前者 ，小于等于后者 </li>
 * <li> 【倒序】  基数小于等于前者 ，大于后者 </li>
 * <li>设置一个基础key值</li>
 * <li>从后往前找到比他小/大于等于他的数，找到这个数字，填写到前一个坑里</li>
 * <li>在从前往后找到比它大或者等于/小于等于他的数字，找到后放到填写到前面那个坑里</li>
 * 
 * 
 * 
 * 
 * @author cjl
 *
 */
public class QuickSort {

    /**
     * 顺序逻辑
     * 
     * @param array
     *            数组
     * @param start
     *            数组索引0
     * @param end
     *            数组索引最后一位array.length-1
     * @return
     */
    public void QuickSort(int[] array, int start, int end) {
        // 当前游标索引值相等的时候 停止递归
        if (start < end) {
            int index = getIndex(array, start, end);
            // 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
            QuickSort(array, 0, index - 1);
            QuickSort(array, index + 1, end);
        }
    }

    /**
     * 
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int getIndex(int[] array, int start, int end) {
        int i = start;
        int j = end;
        // 定义初始值
        int x = array[i];
        while (i < j) {
            // 移动游标 从 后--》前移动 基数值小于等于后面的值 游标从右向左推进
            while (i < j && array[j] >= x) {
                j--;
            }
            // 如果出现满足的值
            if (i < j) {
                // 把后面的值赋值给第一个基础值
                array[i] = array[j];
                i++;
            }

            // 移动游标 从前---》往后 基数值大于前面的值 游标从左往右推进
            while (i < j && array[i] < x) {
                i++;
            }
            // 如果出现满足的值
            if (i < j) {
                // 把前的值赋值给上一个值
                array[j] = array[i];
                j--;
            }
        }
        array[i] = x;
        return i;
    }

    /**
     * 倒序逻辑
     * 
     * @param array
     *            数组
     * @param start
     *            数组索引0
     * @param end
     *            数组索引最后一位array.length-1
     * @return
     */
    public void QuickSortDesc(int[] array, int start, int end) {
        // 当前游标索引值相等的时候 停止递归
        if (start < end) {
            int index = getIndexDesc(array, start, end);
            // 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
            QuickSortDesc(array, 0, index - 1);
            QuickSortDesc(array, index + 1, end);
        }
    }

    private int getIndexDesc(int[] ar, int m, int n) {
        int x = ar[m];
        while (m < n) {
            // X>后者
            while (m < n && ar[n]<x) {
                n--;
            }
            if (m < n) {
                ar[m]=ar[n];
                m++;
            }
            //x<=前者
            while (m < n && ar[m]>=x) {
                m++;
            }
            if (m < n) {
                ar[n]=ar[m];
                n--;
            }
        }
        ar[m]=x;

        return m;
    }

}

插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public void insertSort(int[] array) {
        // 设置循环次数 定义游标 取第二个值
        for (int i = 1; i < array.length; i++) {
            // 游标指向 当前元素下一个值
            int temp = array[i];
            // 定义第二个游标指针 指向前一个值
            int j = i - 1;
            // 如果满足 前一个值 大于后一个值，则交换两个的位置，j-- 移动游标 直到与最后一个交换为止
            for (; j >= 0 && array[j] > temp; j--) {
                // 较小的值与相邻的值换位置
                array[j + 1] = array[j];
                // j-- 移动游标 向前移动游标 继续比较
            }
            array[j + 1] = temp;
        }
    }

希尔排序

希尔排序根据 分组插入排序，该方法又称缩小增量排序。

核心流程：

• 先对数组进行分组 数组长度进行分组【length/2】
• 每次减小分组长的增量
• 移动index进行 插入排序
  

/**
 * 希尔排序根据 分组插入排序，该方法又称缩小增量排序
 * 
 * @author cjl
 *
 */
public class ShellSort {

    public void ShellSort(int ar[]) {
        int len = ar.length;
        // 先计算每次分组的个数,分组 长度 =0 时候跳出循环,每次计算完成 组长/2
        for (int space = len / 2; space > 0; space = space / 2) {
            // 循环每组的个分组个数 长度是8 的数组 分组数为8/2=4 循环4次
            for (int currentIndex = 0; currentIndex < space; currentIndex++) {
                // 进行循环比较，每次比较完成交换数据 ，游标移动m+space的位置
                for (int i = currentIndex + space; i < ar.length; i = i + space) {
                    // 插入排序
                    int temp = ar[i];
                    int x = i - 1;
                    for (; x > 0 && ar[x] > temp; x--) {
                        ar[x + 1] = ar[x];
                    }
                    ar[x + 1] = temp;
                }
            }
        }
    }
}

堆排序

先简单给大家简单分享一下
堆的概念：
堆是一棵完全二叉树，所谓完全二叉树即叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆和二叉树的区别：
堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（这里的讨论以大根堆为例），所以，堆是结点之间满足一定次序关系的完全二叉树。
树的度：结点拥有的子树数 。二叉树 小于等于2。

大顶堆、小顶堆

/**
 * 堆排序
 * 
 * @author cjl
 *
 */
public class HeapSort {

    public TreeMap HeapSort(int[] array) {
        TreeMap  tm=new TreeMap<>();
        //建立 小根堆
        for (int i = (array.length-1)/2; i>=0; i--) {
            HeapMap(array, array.length, i);;
        }
        //输入根堆
        int n=array.length;
        while (n>0) {
            tm.put(n, array[0]);
            array[0]=array[n-1];
            n--;
            HeapMap(array, n, 0);
        }
        return tm;
    }

    private void HeapMap(int[] array, int len, int i) {
        int iLeft = i * 2 + 1;
        int iRight = i * 2 + 2;

        if (iLeft>len && iRight>len) {
            return ;
        }

        int tL=Integer.MAX_VALUE;
        int tR=Integer.MAX_VALUE;

        if (iLeft<len) {
            tL=array[iLeft];
        }
        if (iRight<len) {
            tR=array[iRight];
        }

        //当前根小于左右子节点 的话就满足最小根堆条件
        if (tL>array[i]&&tR>array[i]) {
            return;
        }
        //如果不满足的话比较最小的进行交换
        if (tL<tR) {
            swap(array, i, iLeft);
            HeapMap(array, len, iLeft);
        }else{
            swap(array, i, iRight);
            HeapMap(array, len, iRight);
        }
    }

    private void swap(int[] array, int i, int iLeft) {
        int t=array[i];
        array[i]=array[iLeft];
        array[iLeft]=t;
    }

}
//调用
public void  HeapSort() {
           int[]  array={

  8,7,6,6,10,-1,0,2,20,13,-2,-3,-5};  
           HeapSort sh=new HeapSort();
           TreeMap tm=new TreeMap<>();
           tm=sh.HeapSort(array);
           Iterator it=tm.descendingKeySet().iterator();
           while (it.hasNext()) {
            System.out.println(tm.get(it.next()));
        }

    }

简单选择排序

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3）重复第二步，直到所有元素均排序完毕

原理

/**
 * 选择排序
 * 
 * @author cjl
 *
 */
public class SelectSort {

    public void SelectSort(int[] array) {
        // 循环次数
        for (int i = 0; i < array.length - 1; i++) {
            int k = i;
            for (int j = k+1; j < array.length; j++) {
                if (array[k] > array[j]) {
                    k = j; // 记录当前 最小值的位置
                }
            }
            if (i!=k) {
                int temp=array[i];
                array[i]=array[k];
                array[k]=temp;
            }
        }
    }

}

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

说基数排序之前，我们简单介绍桶排序：

算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使 用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

排序效率的比较

在网上搜了搜找到了这么一张图，看似蛮有道理的，如下：

从排序效率上来说：
纯数字的话 ：快速排序 、系统提供的Arrays.sort 相对较快Arrays.sort 实际上也是快速排序算法
带对象排序的：快速排序 比较快
稳定性来说的话：
归并排序，基数排序 比较好。

时间复杂度的问题

什么是时间复杂度？
时间复杂度：执行的语句次数，称为语句频度或者时间频度。

2.简单算法的时间复杂度举例

列举一些简单例子的时间复杂度。

O(1)的算法是一些运算次数为常数的算法。例如：

x=a;// 频度 1
    a=b;// 频度 1 
    b=x;// 频度 1

上面语句共三条操作，平均每条操作的频度为1，即使他有成千上万条操作，也只是个较大常数，这一类的时间复杂度为O(1)。

O(n)的算法是一些线性算法。例如：

int res =0；  //频度 1              
    for(i=0;i<n;i++)   //频度 n         
    res ++；  //频度 n

上面代码中第一行频度1，第二行频度为n，第三行频度为n，所以f(n)=n+n+1=2n+1。所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。

O(logn) 一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间 例子：

int s=1; 
    while (s<=n) 
       s=s*2;

上面代码设第三行的频度是f(n), 则：2*f(n)<=n;f(n)<=log₂n，取最大值f(n)= log₂n，所以T(n)=O(log₂n ) 。

O(n²)（n的k次方的情况）最常见的就是平时的对数组进行排序的各种简单算法都是O(n²)，例如直接插入排序的算法。

而像矩阵相乘算法运算则是O(n³)。

例子：

sum=0；                

 for(i=0;i<n;i++)  

    for(j=0;j<n;j++) 

       sum++；

第一行频度1，第二行n，第三行n²，第四行n²，T(n)=2n²+n+1 =O(n²)

常见的算法时间复杂度由小到大依次为
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

以上是本人参考其他大神代码和博客学习的成果。如果又不足之处各位大神指教。