数据结构--冒泡排序、归并排序、快速排序、选择排序、插入排序(Java版)-蒲公英云

一、冒泡排序

1、思路

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
针对所有的元素重复以上的步骤，直到没有任何一对元素需要比较。

2、实现

/** * 排序算法的接口 * @author hoaven */
public interface ISort { 
    /** * 对数组array进行升序排序 * @param array */
    public void sort(int[] array);
}
/** * 冒泡排序 * 时间复杂度: 平均情况与最差情况都是O(n^2) * 空间复杂度: O(1) * * @author hoaven * @see ISort */
public class BubbleSort implements ISort { 
    public void sort(int[] array) {
        int temp = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

二、归并排序

1、思路

初始状态：无序区为R[1..n]，有序区为空。
第1趟排序: 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
第i趟排序: 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

2、实现

/** * 归并排序<br> * 时间复杂度: 平均情况与最差情况都是O(nlog(n))<br> * 空间复杂度: It Depends * @author hoaven * @see ISort */
public class MergeSort implements ISort { 
    public void sort(int[] array) {
        int[] auxArray = new int[array.length];
        mergeSort(array, auxArray, 0, array.length - 1);
    }
    /** * 基于分治思想，执行归并排序 * @param low 待排序数组下标下界 * @param high 待排序数组下标上界 */
    private void mergeSort(int[] array, int[] auxArray, int low, int high) {
        int dividedIndex = 0; // 分治位置索引变量
        if (low < high) {
            dividedIndex = (low + high) / 2; // 计算分治位置(采用简单的二分思想)
            mergeSort(array, auxArray, low, dividedIndex); // 左侧递归归并排序
            mergeSort(array, auxArray, dividedIndex + 1, high); // 右侧递归归并排序
            merge(array, auxArray, low, dividedIndex, high); // 合并分治结果
        }
    }
    private void merge(int[] array, int[] auxArray, int low, int dividedIndex, int high) {
        int i = low; // 指向左半分区数组的指针
        int j = dividedIndex + 1; // 指向右半分区数组的指针
        int auxPtr = 0; // 指向辅助区数组的指针
        // 合并两个有序数组：array[low..dividedIndex]与array[dividedIndex+1..high]。
        while (i <= dividedIndex && j <= high) { // 将两个有序的数组合并，排序到辅助数组auxArray中
            if (array[i] > array[j]) { // 左侧数组array[low..dividedIndex]中的array[i]大于右侧数组array[dividedIndex+1..high]中的array[j]
                auxArray[auxPtr++] = array[j++];
            } else {
                auxArray[auxPtr++] = array[i++];
            }
        }
        // 如果array[low..dividedIndex].length>array[dividedIndex+1..high].length，经过上面合并
        // array[low..dividedIndex]没有合并完，则直接将array[low..dividedIndex]中没有合并的元素复制到辅助数组auxArray中去
        while (i <= dividedIndex) {
            auxArray[auxPtr++] = array[i++];
        }
        // 如果array[low..dividedIndex].length<array[dividedIndex+1..high].length，经过上面合并
        // array[dividedIndex+1..high]没有合并完，则直接将array[dividedIndex+1..high]中没有合并的元素复制到辅助数组auxArray中去
        while (j <= high) {
            auxArray[auxPtr++] = array[j++];
        }
        // 最后把辅助数组auxArray的元素复制到原来的数组中去，归并排序结束
        for (auxPtr = 0, i = low; i <= high; i++, auxPtr++) {
            array[i] = auxArray[auxPtr];
        }
    }
}
//假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20，我们以该数组为例，执行归并排序的具体过程：
            [94,12,34,76,26,9,0,37,55,76,    37,5,68,83,90,37,12,65,76,49]
            [94,12,34,76,26,    9,0,37,55,76]
            [94,12,34,    76,26]
            [94,12,    34]
            [94,    12]
            {
   12,    94}
            {
   12,34,    94}
            [76,    26]
            {
   26,    76}
            {
   12,26,34,    76,94}
            [9,0,37,    55,76]
            [9,0,    37]
            [9,    0]
            {
   0,    9}
            {
   0,9,    37}
            [55,    76]
            {
   55,    76}
            {
   0,9,37,    55,76}
            {
   0,9,12,26,34,    37,55,76,76,94}
            [37,5,68,83,90,    37,12,65,76,49]
            [37,5,68,    83,90]
            [37,5,    68]
            [37,    5]
            {
   5,    37}
            {
   5,37,    68}
            [83,    90]
            {
   83,    90}
            {
   5,37,68,    83,90}
            [37,12,65,    76,49]
            [37,12,    65]
            [37,    12 ]
            {
   12,    37 }
            {
   12,37,    65 }
            [76,    49 ]
            {
   49,    76}
            {
   12,37,49,    65,76}
            {
   5,12,37,37,49,    65,68,76,83,90}
            {
   0,5,9,12,12,26,34,37,37,37,    49,55,65,68,76,76,76,83,90,94}
//上面示例的排序过程中，方括号表示“分解”操作过程中，将原始数组进行递归分解，直到不能再继续分割为止；
//花括号表示“归并”的过程，将上一步分解后的数组进行归并排序。
//因为采用递归分治的策略，所以从上面的排序过程可以看到，“分解”和“归并”交叉出现。

三、快速排序

1、思路

在R[low..high]中任选一个记录作为基准Pivot；
使左边子区间中所有记录的关键字均小于等于基准；
右边的子区间中所有记录的关键字均大于等于基准；

2、实现

/** * 快速排序<br> * 时间复杂度: 平均情况是O(nlog(n)),最差情况是O(n^2)<br> * 空间复杂度: O(nlog(n)) * @author hoaven * @see ISort */
public class QuickSort implements ISort { 
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }
    /** * 通过划分，基于分治思想，递归执行子任务排序最后合并 * @param low 数组首位置索引 * @param high 数组末位置索引 */
    private void quickSort(int[] array, int low, int high) {
        int pivotPos; // 划分基准元素索引
        if (low < high) {
            pivotPos = partition(array, low, high);
            quickSort(array, low, pivotPos - 1); // 左划分递归快速排序
            quickSort(array, pivotPos + 1, high); // 右划分递归快速排序
        }
    }
    /** * 简单划分方法:排列数组array左边的都小于它，右边的都大于它 * @param i * @param j * @return */
    private int partition(int[] array, int i, int j) {
        Integer pivot = array[i]; // 初始基准元素，如果quickSort方法第一次调用，pivot初始为数组第一个元素
        while (i < j) { // 两个指针从两边向中间靠拢，不能相交
            // 右侧指针向左移动
            while (j > i && array[j] >= pivot) {
                j--;
            }
            if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[j] >= 基准元素pivot
                array[i] = array[j]; // 基准元素放到了j指针处
                i++; // 左侧i指针需要向右移动一个位置
            }
            // 左侧指针向右移动
            while (i < j && array[i] <= pivot) {
                i++;
            }
            if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[i] <= 基准元素pivot
                array[j] = array[i]; // 基准元素放到了i指针处
                j--; // 右侧j指针需要向左移动一个位置
            }
        }
        array[i] = pivot; // 将基准元素放到正确的排序位置上
        return i;
    }
}

四、选择排序

1、思路

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2、实现

/** * 选择排序<br> * 时间复杂度: 平均情况与最差情况都是O(n^2)<br> * 空间复杂度: O(1) * @author hoaven * @see ISort */
public class SelectionSort implements ISort { 
    public void sort(int[] array) {
        int temp = 0;
        for(int i = 0; i < array.length; i++){
            temp = array[i];
            for(int j = i; j < array.length; j++){
                if(temp > array[j]){
                    temp = array[j];
                }
            }
            if(temp != array[i]){
                array[i] = temp;
            }
        }
    }
}

五、插入排序

1、思路

要求在一个已排好序的数据序列中插入一个数，但要求插入后此数据序列仍然有序。

2、实现

/** * 插入排序实现 * @author hoaven * */
public class InsertSort implements ISort { 
    public void sort(int[] array) {
        for(int i = 1; i < array.length; i++){
            int temp = array[i];
            int j = i - 1;
            while(j >= 0 && array[j] > temp){
                array[j + 1] = array[j];
                j--;
            }
            if(j != i - 1){
                array[j + 1] = temp;
            }
        }
    }
}