排序

1冒泡排序

/*
 * @Author liuhaidong
 * @Description 冒泡排序
 * @Date 15:43 2019/9/15 0015
 * @Param
 * @return
 **/
public static void BubbleSort(long[] arr){
    long tmp = 0;
    for(int i=0;i<arr.length-1;i++){
        for(int j=arr.length-1;j>i;j--){
            //进行交换
            if(arr[j] <arr[j-1]){
                tmp = arr[j];
                arr[j] = arr[j -1];
                arr[j-1] = tmp;
            }
        }
    }
}

方法2

/** * @Author liuhaidong * @Description 冒泡排序 * @Date 14:35 2019/10/2 0002 */
    private static void BubbleSort(int[] source) {
   
        int tmp = 0;
        for(int i =0;i<source.length;i++){
   
            for (int j =0;j<source.length-1-i;j++){
   
                if(source[j]>source[j+1]){
   
                    tmp = source[j+1];
                    source[j+1] = source[j];
                    source[j] = tmp;
                }
            }
        }
``

图示


外层循环决定几次，内层循环决定循环几次

2选择排序

(相比比冒泡排序效率高一点)

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

/*
 * @Author liuhaidong
 * @Description 选择排序
 * @Date 16:01 2019/9/15 0015
 * @Param
 * @return
 **/
public static void SelectionSort(long[] arr){
    int k = 0;
    long tmp = 0;
    for(int i = 0;i<arr.length-1;i++){
        k = i;
        for(int j =i;j<arr.length;j++){
            if(arr[j] <arr[k]){
                k = j;
            }
        }
        tmp = arr[i];
        arr[i] = arr[k];
        arr[k] = tmp;
    }
}

图示

3直接插入排序

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

实例
基本思想：
　　把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。
　实例：
　　0.初始状态 3，1，5，7，2，4，9，6（共8个数）
　　 有序表：3；无序表：1，5，7，2，4，9，6
　　1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，3；无序表：5，7，2，4，9，6
　　2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，3，5；无序表：7，2，4，9，6
　　3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，3，5，7；无序表：2，4，9，6
　　4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，2，3，5，7；无序表：4，9，6
　　5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，2，3，4，5，7；无序表：9，6
　　6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，2，3，4，5，7，9；无序表：6
　　7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序
　　 有序表：1，2，3，4，5，6，7，9；无序表：（空）

/*
 * @Author liuhaidong
 * @Description  直接插入排序
 * @Date 16:31 2019/9/15 0015
 * @Param
 * @return
 **/
public static void InsertSort(long[] arr){
    long tmp = 0;
    int i ,j;
     //从第二个元素开始遍历即可
    for(i = 1; i < arr.length; i++) {
        /**
         * temp为本次循环待插入有序列表中的数
         */
        tmp = arr[i];
     //从参考值前面一个元素开始从后往前查找
        for(j = i-1;j >=0 && arr[j] > tmp;j--)
        {
            /**
             * 元素后移，为插入temp做准备
             */
            arr[j+1] = arr[j];
        }
        /**
         * 插入temp
         */
        arr[j+1] = tmp;
    }
}