八大排序终结者之一

直接插入排序

---

基本思想
从第二个数开始依次和前面的数进行比较，若大于则不管，若小于则后移。

java代码

//1插入排序
public static void InsertSort(int[] arr){
    for(int i = 1; i < arr.length; i++){
        int j = i - 1;
        int work = arr[i];
        while(j >= 0 && work < arr[j]){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j +1] = work;
        
        //以下打印每步的结果，不属于算法的思想
        System.out.print("第"+i+"次: ");
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k]+" ");
        }
        System.out.println();
    }
}

1.jpg

希尔排序##

基本思想：
使数组分成若干个序列，将数组进行直接插入排序，变为基本有序后，最后增长序列为1的时候

简单选择排序

基本思想：
第i次选择最小的元素和arr[i]进行交换

代码实现如下

//3简单选择排序
public static void SelectSort(int[] arr){
    for(int i = 0; i < arr.length; i++){
        int minIndex = i;
        for(int j = i+1; j < arr.length; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j;
            }
        }

        //交换
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;

        //打印每次的结果
        System.out.print("第"+i+"次: ");
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
        System.out.println();
    }
}

截图 初始状态 3 1 5 7 2 4 9 6

2.jpg

快速排序

//快排
public static void QuickSort(int[] arr, int low, int hight){

    int middle = getMiddle(arr, low , hight);
    QuickSort(arr, low, middle - 1);
    QuickSort(arr, middle + 1, hight);
}

public static int getMiddle(int[] arr, int low, int hight){
    int work = arr[low];
    while (low < hight){
        while (low < hight && work < arr[hight]) hight--;
        arr[low] = arr[hight];
        while (low < hight && work > arr[low]) low++;
        arr[hight] = arr[low];
    }
    arr[low] = work;
    return low;
}