排序算法☞冒泡排序，插入排序，选择排序

排序算法有很多，这里简单谈谈冒泡，插入，选择排序算法：
1、冒泡排序：这个应该是比较常见，而且面试经常会考的。该排序思路是 相邻两个比较，不符合目标排序的则调换两个元素位置，经过一轮比较，可以将最大或最小值放到头部或尾部。 以此类推，第二轮对剩下的n-1个元素进行该操作。n轮之后排序完成。
2、插入排序：插入排序是将目标序列分成两部分，已排序部分和未排序部分。以升序来举例子：做右边未排序部分取第一个元素，从右到左一次跟已排序元素进行比较，遇到更大的就将被比较元素后移一位，直到遇到较小元素，将该元素放在被比较元素后面。
3、选择排序：也是将元素分为已排序部分和未排序部分。循环未排序部分，找到最小元素，并将该元素与第一个元素交换位置。一次类推，将剩下的未排序部分按照这个规律经行处理即可。

java 数组实现代码如下：（仅供参考，欢迎大家指出其中可以优化的地方）

package com.jdwa;

import java.util.Arrays;

public class TestSort {
    public static void main(String[] args) {
        int n = 10000;
        int[] bubble = new int[n];
        int[] insert = new int[n];
        int[] select = new int[n];

        for (int k = 0 ; k< n;k++){
            int l = (int)(n*Math.random());    //随机生成0-100的数
            bubble[k] = l;
            insert[k] = l;
            select[k] = l;
        }
        bubbleSort(bubble);
        System.out.println(Arrays.toString(bubble));
        System.out.println("==================");
        insertSort(insert);
        System.out.println(Arrays.toString(insert));
        System.out.println("+++++++++++++++++++++");
        selectSort(select);
        System.out.println(Arrays.toString(select));


    }

    /**
     * 冒泡排序:
     * 思路：第一轮将最大或最小元素通过比较与交换，送到头部或尾部，剩余元素以此类推，一次从到正或倒数第二，三，四。。。等位置
     * @param arr
     * @return
     */
    public static void bubbleSort(int[] arr){
        Long beg = System.currentTimeMillis();
        int n = arr.length;
        if ( n <= 1 ) {
            return;
        }
        for ( int i = 0 ;i < n ; i ++) {
            // 用于标记本次循环有没有数据交换，如有没有说明已排序完成，直接退出
            boolean flg = false;
            //n-i个元素，没两个元素进行比较，故需要 n - i -1比较
            for ( int j = 0 ; j < n - i -1 ; j++ ) {
                if (arr[j] > arr[j+1]) {
                    flg = true;
                    //升序排列，如果前面的数据大则交换
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

            if (!flg) {
                break;
            }

        }
        System.out.println(System.currentTimeMillis() - beg);
    }

    /**
     * 升序排列
     * 选择第i个元素value，跟前面的元素做对比，升序则需要从后往前，所以内循环的下标依次递减
     *
     * 思路：将数组分为两部分左边是已排序部分  右边是未排序部分
     * 以第二个元素为例， 先将arr[1]（未排序最左边元素）取出暂存，并将其值依次从右向左跟已排序部分比较，遇到更大的则将元素后移一位（因为未排序最左边位置元素已暂存，不用担心覆盖）
     * 直到遇到更小的元素，跳出循环。将暂存的第二个元素 存到 跳出循环时 比较的元素arr[j]的右边位置，即arr[j+1]
     * @param arr
     */
    public static void insertSort(int[] arr){
        Long beg = System.currentTimeMillis();
        int n = arr.length;
        if ( n <= 1 ) {
            return;
        }

        for (int i = 0 ; i < n ; i ++){
            int value = arr[i];
            int j = i-1;
            for ( ; j >= 0 ; j--) {
                if (arr[j] > value){
                    arr[j+1] = arr[j];  //依次移动数据
                } else {
                    break;
                }
            }
            arr[j+1] = value;
        }
        System.out.println(System.currentTimeMillis() - beg);
    }


    public static void selectSort(int[] arr) {
        Long beg = System.currentTimeMillis();
        int n = arr.length;
        if ( n <= 1 ) {
            return;
        }

        for (int i = 0 ; i < n ; i ++){
            int value = arr[i];
            int j = i+1;
            //循环，最小值在最后一个元素
            for ( ; j < n-1 ; j++) {
                if (arr[j] < arr[j+1]) {
                    //升序排列，如果前面的数据大则交换
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            //arr[i]与arr[n-1]交换
            int tmp = arr[i];
            arr[i] = arr[n-1];
            arr[n-1] = tmp;
        }
        System.out.println(System.currentTimeMillis() - beg);
    }

}

某次运行结构如下：

143
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]
==================
33
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]
+++++++++++++++++++++
153
[3, 4, 4, 5, 7, 7, 8, 9, 10, 12, 13, 16, 18, 19, 21, 22, 22, 22, 23, 23, 23, 25, 25, 25, 26, 26, 26, 26, 28, 28, 29, 29, 30, 31, 31, 32, 35, 37, 38, 38, 38, 38, 39, 42, 42, 42... ... ... 9970, 9972, 9973, 9975, 9975, 9975, 9978, 9980, 9980, 9980, 9981, 9981, 9981, 9981, 9984, 9986, 9987, 9987, 9988, 9988, 9989, 9989, 9990, 9992, 9995, 9995, 9995, 9999, 9999, 9999, 9999]

Process finished with exit code 0