注：因论坛发帖字数限制，所以本文分为上、下两篇，请读者注意，本篇为（下）


5、冒泡排序

[Java] 纯文本查看 复制代码

/*
 * 冒泡排序基本概念是：
 * 依次比较相邻的两个数，将小数放在前面，大数放在后面。
 * 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
 * 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，
 * 直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，
 * 将最大的数放到了最后。在第二趟：仍从第一对数开始比较
 * （因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），
 * 将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），
 * 第二趟结束，在倒数第二的位置上得到一个新的最大数
 * （其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 
 */
public class BubbleSort {
    public static void sort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    SortTest.swap(data, j, j + 1);
                }
            }
        }
    }
}

6、希尔排序

[Java] 纯文本查看 复制代码

/*
 * 希尔排序：先取一个小于n的整数d1作为第一个增量，
 * 把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。
 * 先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，
 * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 
 */
public class ShellSort {
    public static void sort(int[] data) {
        for (int i = data.length / 2; i > 2; i /= 2) {
            for (int j = 0; j < i; j++) {
                insertSort(data, j, i);
            }
        }
        insertSort(data, 0, 1);
    }
    /**
     * @param data
     * @param j
     * @param i
     */
    private static void insertSort(int[] data, int start, int inc) {
        for (int i = start + inc; i < data.length; i += inc) {
            for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
                SortTest.swap(data, j, j - inc);
            }
        }
    }
}
/*
 * 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序 　　 
 * 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，
 * 组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1， 即所有记录放进一个组中排序为止 　　 
 * 初始：d=5 　　49 38 65 97 76 13 27 49 55 04 　　 
 * 49 13 　　|-------------------| 　　 
 * 38 27     |-------------------| 　　 
 * 65 49 　　|-------------------| 　　 
 * 97 55     |-------------------| 　　 
 * 76 04 　　|-------------------| 　　 
 * 一趟结果 　　13 27 49 55 04 49 38 65 97 76 　　 
 * d=3 　　 13 27 49  55 04 49 38 65 97 76 　　 
 * 13 55 38 76 |------------|------------|------------| 　　 
 * 27 04 65 |------------|------------| 　　 
 * 49 49 97 |------------|------------| 　　
 * 二趟结果  13 04 49* 38 27 49 55 65 97 76 　　 
 * d=1 　　13 04 49 38 27 49 55 65 97 76
 * 　　 |----|----|----|----|----|----|----|----|----| 　　 三趟结果 　　
 * 04 13 27 38 49 49 55 65 76 97
 */

7、选择排序

[Java] 纯文本查看 复制代码

/*
 * 选择排序基本思路：
 * 把第一个元素依次和后面的所有元素进行比较。
 * 第一次结束后，就会有最小值出现在最前面。
 * 依次类推
 */
public class SelectionSort {
    public static void sort(int[] data) {
        for (int x = 0; x < data.length - 1; x++) {
            for (int y = x + 1; y < data.length; y++) {
                if (data[y] < data[x]) {
                    SortTest.swap(data, x, y);
                }
            }
        }
    }
}

8、SortTest

[Java] 纯文本查看 复制代码

import java.util.Arrays;
public class SortTest {
    public static void main(String[] args) {
        int[] arr = { 2, 5, 3, 1, 4 };
        System.out.println("排序前：" + Arrays.toString(arr));
        // InsertSort.sort(arr);
        // BubbleSort.sort(arr);
        // SelectionSort.sort(arr);
        // ShellSort.sort(arr);
        // QuickSort.sort(arr);
        // MergeSort.sort(arr);
        // HeapSort.sort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
    /*
     * 交换数组中的两个元素
     */
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

我来占层楼啊