排序算法

韩冬作业题

排序

插入排序

pubulic static void insertSort()(int[] arr){
    for(int i = 1; i < arr.length; i++){
        int insertVal = arr[i];
        int insertIndex = i - 1;
        //循环插入
        while(insertIndex >= 0 && insertVal < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex --;
        }
        arr[insertIndex+1] = insertVal
    }
}

希尔排序-斐波那契数列

public static void shellSortArray(int[] arr){
    //用斐波那契的希尔排序
    int temp = 0;
    int fb = 1;
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    //确定间隔数据量
    while(fbii(bi)< 10000/2){
        arrayList.add(fbii(fb));
        fb++;
    }
    for(int span = arrayList.size()-1; span > 0; span--){
        int spaner = arrayList.get(span);
        for(int i = spaner; i < arr.length; i++){
            for(int j = i - spaner; j >= 0; j--){
                if(arr[j] > arr[j + spaner]){
                    //交换
                    temp = arr[j];
                    arr[j] = arr[j + spaner];
                    arr[j + spaner] = temp;
                }
            }
        }
    }
}
public static void fbii(int n){
    if(n == 1 || n == 2){
        return 1;
    }
    else{
        return fbii(n-1) + fbii(n-2)
    }
}

冒泡排序

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

选择

for (int time = 0; time < array.length-1; time++) {
    int Arraysmallest = array[indexCurr+1];
    int recodSmallIndex = indexCurr+1;
    for(int index = indexCurr + 1; index < array.length; index++) {
        if(Arraysmallest > array[index]) {
            Arraysmallest = array[index];
            recodSmallest = index;
        }
    }
    if(array[indexCurr] >= array[recodSmallest]) {
        int temp = array[indexCurr];
        array[indexCurr] = array[recodSmallIndex];
        array[recodSmallIndex] = temp;
    }
    if(indexCurr < array.length-2){
        indexCurr++;
    }
}

归并

public static void mergeSort(int[] arr, int left, int right, int[] temp){
    if(left < right){
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, right, mid+1, temp);
        merge(arr, left, mid, right, temp);
    }
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;
    int j = mid +1;
    int t = 0;
    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            temp[t] = arr[i];
            t++;
            i++;
        }
        else{
            temp[t] arr[j];
            t++;
            j++;
        }
    }
    while(i <= mid){
        temp[t] = arr[i]
        t++;
        i++;
    }
    while(j <= right){
        temp[t] = arr[j];
        t++;
        j++;
    }
    t = 0;
    int tempLeft = left;
    while(tempLeft <= right){
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

快速

QWQ

基数

public static int findIndex(int number, int index){
    return number / index % 10;
}
public static int[] blackSort(int[] arr){
    int sortTime = findMaxDigit(arr);
    int blanketLength = arr.length;
    int[][] blanketArr = new int[blanketLength][blanketLength];
    int[] bucketElementCounts = new int[arr.length];
    
    for(int time = 0; findN = 1; time < sortTime; time++, findN *= 10){
        for (int index = 0; index < arr.length; index++) {
            int indexNumber = findIndex(arr[index], findN);
            blanketArr[indexNumber][bucketElementCounts[indexNumber]] = arr[index];
            bucketElementCounts[indexNumber]++;
        }
        int k = 0;
        for (int index = 0; index < blanketLength; index++) {
            if (bucketElementCounts[index] != 0) {
                for(int l = 0; l < bucketElementCounts[index]; l++){
                    arr[k++] = blanketArr[index][l];
                }
            }
            bucketElementCounts[index] = 0;
        }
    }
    ret
}