Java 中三种常用的排序方法

今天重新学习类三种排序方法，按照排序速度依次是冒泡排序，选择排序和插入排序。 以下示例皆为从小到大的排序

1.冒泡排序

每一次比较都可能要交换元素。 冒泡排序的思想是： 每一轮开始的时候，将第一个元素（a）开始与其后的元素（b）依次进行比较，将较大的元素（设为 m）放到后面，并将 m 与其后的另外一个元素继续进行比较，直到最后一个没有排好序的元素。 在接下来一轮的排序中，刚才以及之前选出来的、已经排好顺序的最大值不用参与排序。 依次类推，总共遍历 n-1 轮，即可完成排序。 具体代码如下：

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

    System.out.println("\n--bubble :");
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}

2.选择排序

每次比较的时候不交换 选择排序的思想： 每次比较的时候找到的两个数中的较大值并记下其位置，等到当前一轮的遍历完成之后，将最后一个未排序元素与这一轮遍历找到的最大值交换 最多交换 n-1 次 代码如下：

   void select(int[] arr){

    for (int i = 0; i < arr.length; i++) {
        int maxIndex = 0;
        int temp = 0;

        for (int j = 1; j < arr.length - i; j++) {
            if (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }

        temp = arr[maxIndex];
        arr[maxIndex] = arr[arr.length - i - 1];
        arr[arr.length - i - 1] = temp;
    }


    System.out.println("\n--select :");

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}

3.插入排序法

插入排序法思想： 将待排序的元素分为有序和无序两种，刚开始排序的时候假设只有第一个元素是有序的，其余 n-1 个元素都是无序的； 排序开始的时，将无序部分的一个元素（a）与有序部分的最后一个元素（b）进行比较，如果 a<b，则将 a 与 b 交换，再将 a 与下一个有序元素进行比较；否则，将 a 加到 b 后面，作为有序部分的最后一个元素。 接着再从无序部分取出一个元素与有序部分的元素依次比较，直达所有元素都为有序元素。 遍历 n-1 次 代码如下：

    void insertSort(int[] arr){

    for (int i = 1; i < arr.length; i++) {
        int instertValue = arr[i];

        for (int j = i - 1; j >= 0; j--) {
            if (instertValue < arr[j]) {
                arr[j+1] = arr[j];
                arr[j] = instertValue;
            }else {
                break;
            }
        }
    }

    /* 第二种表示形式
    for (int i = 1; i < arr.length; i++) {
        int instertVal = arr[i];
        int index = i - 1;

        while (index >= 0 && instertVal < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = instertVal;
    }
    */

    System.out.println("\n--insertSort :");
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}