java进阶 - 经典排序

业余时间学习java，回顾经典算法。

插入排序

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 —— [ 百度百科 ]

代码

 /**
  * 插入排序
  */
 public void insertSort(int[] array) {
    System.out.println("-----Start 插入排序-----");
    System.out.println(Arrays.toString(array));
    for (int i = 0; i < array.length; i++) {
        int j = i - 1;
        int temp = array[i];
        while (j > -1 && temp < array[j]) {
            array[j + 1] = array[j];
            j--;
        }
        if (temp == array[i]) {
            continue;
        }
        array[j + 1] = temp;
    }
    System.out.println(Arrays.toString(array));
    System.out.println("-----End 插入排序-----");
}

运行结果

-----Start 插入排序-----
[14, 21, 12, 5, 7]
[5, 7, 12, 14, 21]
-----End 插入排序-----

冒泡排序

冒泡排序算法的运作如下：（从后往前）
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 —— [ 百度百科 ]

代码

  /**
     * 冒泡排序（Bubble Sort）
     */
public void bubbleSort(int[] array) {

    System.out.println("-----Start 冒泡排序-----");
    System.out.println(Arrays.toString(array));

    int temp = 0;
    for (int i = array.length - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (array[j + 1] < array[j]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    System.out.println(Arrays.toString(array));
    System.out.println("-----End 冒泡排序-----");
}

运行结果

-----Start 冒泡排序-----
[5, 7, 12, 14, 21]
[5, 7, 12, 14, 21]
-----End 冒泡排序-----

快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 —— [ 百度百科 ]

代码

private int count = 0;
/**
    * 快速排序（Bubble Sort）
    * @param array
    * @param l
    * @param r
    */
public void quickSort(int[] array, int l, int r) {
    if (l < r)
    {
        int i = l, j = r, x = array[l];
        while (i < j)
        {
            // 从右向左找第一个小于x的数
            while(i < j && array[j] >= x)
                j--;
            if(i < j)
                array[i++] = array[j];

            // 从左向右找第一个大于等于x的数
            while(i < j && array[i] < x)
                i++;
            if(i < j)
                array[j--] = array[i];
        }
        array[i] = x;
        count ++;
        System.out.println("-----第"+count+"次快速排序-----");
        System.out.println(Arrays.toString(array));
        // 递归调用
        quickSort(array, l, i - 1);
        quickSort(array, i + 1, r);
    }
}

运行结果

int[] outOrder = {14, 21, 12, 5, 7,9,55,77,33,12,65,6};

运行结果：
-----第1次快速排序-----
[6, 12, 12, 5, 7, 9, 14, 77, 33, 55, 65, 21]
-----第2次快速排序-----
[5, 6, 12, 12, 7, 9, 14, 77, 33, 55, 65, 21]
-----第3次快速排序-----
[5, 6, 9, 7, 12, 12, 14, 77, 33, 55, 65, 21]
-----第4次快速排序-----
[5, 6, 7, 9, 12, 12, 14, 77, 33, 55, 65, 21]
-----第5次快速排序-----
[5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
-----第6次快速排序-----
[5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
-----第7次快速排序-----
[5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]
-----第8次快速排序-----
[5, 6, 7, 9, 12, 12, 14, 21, 33, 55, 65, 77]

Process finished with exit code 0

待更新