Java基础——冒泡、选择和插入排序算法

---

1. 冒泡排序算法。

   工作原理：比较相邻的元素，如果第一个比第二个大，就交换它们的位置。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。最后的元素应该会是最大的数，然后针对除了最后一个元素以外的所有元素重复以上的步骤，直到没有任何一对数字需要比较。

上代码：

 public static void main(String[] args) {
        int[] array = {2, 1, 8, 17, 32, 16, 19, 21, 18, 6, 22};
        //i为数组的长度，则比较的轮数为i-1
        for (int i = 0; i < array.length - 1; i++) {
            //每一轮比较的次数为length - i - 1
            for (int j = 0; j < array.length - i - 1; j++) {
                //比较相邻两个元素的大小，第一个比第二个大，则交换位置
                if (array[j] > array[j + 1]) {
                    //通过临时变量交换两个元素的位置
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        //打印排好序的数组
        for (int i : array) {
            System.out.print(i + "  ");
        }
    }

上面代码的打印结果为：1  2  6  8  16  17  19  21  22  32  

---

2. 选择排序法：

   工作原理：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，知道所有元素均排序完毕。
   如下：

 /**
     * 选择排序
     *
     * @param array
     */
    private static void SelectSort(int[] array) {
        int min = 0;//最小数的小标 默认是0

        //i为数组的长度，则比较的轮数为i-1
        for (int i = 0; i < array.length - 1; i++) {
            min = i;
            //查找最小数的下标，并保存到min
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            //如果i不是最小元素，则交换最小元素与i的位置
            if (i != min) {
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
        //打印排序后的数组
        for (int i : array) {
            System.out.print(i + "  ");
        }
    }

我们在main方法里调用SelectSort方法：

 public static void main(String[] args) {
        int[] array = {2, 1, 8, 17, 32, 16, 19, 21, 18, 6, 22};
        SelectSort(array);
 }

得到的打印结果为：1  2  6  8  16  17  18  19  21  22  32  

---

3. 插入排序法：
   工作原理：它是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。从后向前扫描过程中，需要反复把自己已排序元素逐步向后挪位，为最新的元素提供插入控件。

还是看代码吧：

 /**
     * 插入排序
     *
     * @param array
     */
    private static void InsertSort(int[] array) {
        /**
         * 从1 开始 取出来与前面的数作比较
         */
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i;//讲下标保存起来
            //temp 和i前面的每一个数据进行比较，如果比前面的小 则插入到前面的位置
            while (j > 0 && temp < array[j- 1]) {
                array[j] = array[j - 1];//
                j--;
            }
            array[j] = temp;//插入数据
        }
        //打印排序后的数组
        for (int i : array) {
            System.out.print(i + "  ");
        }
    }

同样我们在main方法里调用InsertSort方法：

 public static void main(String[] args) {
        int[] array = {2, 1, 8, 17, 32, 16, 19, 21, 18, 6, 22};
        InsertSort(array);
 }

得到的打印结果为：1  2  6  8  16  17  18  19  21  22  32  

这就是常用的三种数组排序算法。