基础排序算法

---

• 插入排序
  从空集合开始，不断把记录插入到合适位置的排序方法
• 交换排序
  交换元素的位置进行排序

---

插入排序

直接插入排序

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

时间复杂度
最好：已经有序的情况下，只需要遍历数列一次，为O(n)。
最坏：反序情况下比较次数依次是1 + 2 + 3 + ... + (N - 1)，即(1/2)n(n-1)次。O(n^2)。
平均：O(n^2)
空间复杂度：只有一个额外变量，所以为O(1)

折半插入算法

public static void binaryInsertSort(int[] array) {
        int temp;
        int low = 0;
        int high;
        int middle;
        for (int i = 1; i <= array.length - 1; i++) {
            temp = array[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                middle = (low + high) / 2;
                if (temp < array[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            int j;
            for (j = i - 1; j >= high + 1; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
        }
    }

• 希尔排序

public static void shellSort(int[] array, int[] numbers) {

        int i, j, temp, m, k, span;
        for (m = 0; m < numbers.length; m++) {
            span = numbers[m];
            for (k = 0; k < span; k++) {
                for (i = k + span; i < array.length; i = i + span) {
                    temp = array[i];
                    j = i - span;
                    while (j > -1 && temp < array[j]) {
                        array[j + span] = array[j];
                        j = j - span;
                    }
                    array[j + span] = temp;
                }
            }


        }

    }

交换排序

冒泡排序

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

快速排序

public static int partition(int[] array,int low,int high) {
        int temp = array[low];
        while(low < high){
            while(low < high && temp <= array[high])
                high--;
            if(low < high)
            array[low++] = array[high];
            while(low < high && temp >= array[low])
                low++;
            if(low < high)
            array[high--] = array[low];
        }
        array[low] = temp;
        return low;
    }

    public static void quickSort(int[] array,int low,int high) {
        int standardLoc;
        if(low<high) {
            standardLoc = partition(array,low,high);
            quickSort(array,low,standardLoc-1);
            quickSort(array,standardLoc+1,high);
        }
    }

    public static int[] oldArray = {4,786,24,65,76,23,15,97,34,48,92,44};
//on call
quickSort(oldArray,0,oldArray.length-1);

选择排序

不断从待排序序列中选择最小的记录放到已经排序的记录后面

public static void swapSort(int[] oldArray){
        int smallIndex;
        int temp;
        int i,j;
        for(i = 0;i<oldArray.length - 1;i++){
            smallIndex = i;
            for(j = i+1;j<oldArray.length;j++){
                if(oldArray[smallIndex] >= oldArray[j]){
                    smallIndex = j;
                }
            }
            if(smallIndex != i){
                temp = oldArray[i];
                oldArray[i] = oldArray[smallIndex];
                oldArray[smallIndex] = temp;
            }
        }
}

比较次数依次为(n-1)、(n-2)、、、1，故时间复杂度 O(n²)，空间复杂度O(1);

堆排序：https://blog.csdn.net/qq_36186690/article/details/82505569