排序的实现


排序

直接插入排序

简单方法

首先在当前有序区 R[1..i-1]中查找R[i]的正确插入位置 k(1≤k≤i-1);然后将 R[k..i-1]中的记录均后移一个位置,腾出 k 位置上的空间插入 R[i]。

    public static void insertSort(int[] arrays) {
        int j;
        for (int i = 1; i < arrays.length; i++) {
            int temp = arrays[i];
            for (j = i - 1; j >= 0 && arrays[j] > temp; j--) {
                arrays[j + 1] = arrays[j];
            }
            arrays[j+1] = temp;
        }
    }

带有哨兵的排序

    //由于有第一个哨兵所以只能排序从1到n,0不能作为有效的排序
    public static void insertSortWithGuard(int[] arrays){
        int j;
        for (int i = 1; i <arrays.length ; i++) {
            arrays[0] = arrays[i];
            for ( j = i-1; arrays[j]>arrays[0] ; j--) {
                arrays[j+1] =arrays[j];
            }
            arrays[j+1] =arrays[0];
        }
    }

冒泡排序

基本思路

就是最多进行n-1次循环,每次n-1次比较,每一次外层循环找出相对最大的元素

实现

    public static void bubbleSort(int[] arrays) {
        int temp;
        for (int i = 1; i < arrays.length; i++) {
            for (int j = 0; j < arrays.length - 1; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
    }

快速排序

基本思路

每次排序完成能够把支点放到正确的位置上

实现

    //一次快排
    public static int Partition(int i, int j) {
        int pivot = arrays[i];
        while (i < j) {
            while (i < j && pivot <= arrays[j]) {
                j--;
            }
            if (i < j) {
                arrays[i] = arrays[j];
                i++;
            }
            while (i < j && pivot > arrays[i]) {
                i++;
            }
            if (i < j) {
                arrays[j] = arrays[i];
                j--;
            }
        }
        arrays[i] = pivot;
        return i;
    }
    //递归的实现方式
    public static void qSort(int low, int high) {
        if (low < high) {
            int pivotloc = Partition(low, high);
            qSort(low, pivotloc - 1);
            qSort(pivotloc + 1, high);
​
        }
    }

一次快排之后就把排序分成两个部分,返回的是支点的位置

直接选择排序

基本思路

每一次循环找出最小的元素放在第一个

实现

    public static void selectSort(int[] arrays){
        int temp;
        for (int i = 0; i < arrays.length - 1; i++) {
            int min  = i;
            for (int j = i+1; j < arrays.length; j++) {
                if (arrays[j]<arrays[min]){
                    min = j;
                }
            }
            if (min!=i){
                temp = arrays[i];
                arrays[i] = arrays[min];
                arrays[min] = temp;
            }
        }
    }

It's time for you to begin thinking out of the box