排序算法

笔者埋坑后面再来分析总结

1. 插入排序

直接插入排序：O(n^2)

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

二分插入排序：O(n^2)

public static int[] binaryInsertSort(int[] arr){
    int i,j,low,high,mid,temp;
    for(i = 1; i < arr.length; i++){
        temp = arr[i];
        low = 0;
        high = i - 1;
        while(low <= high){     //最后一个也要比较，比完就知道具体位置了
            mid = (low + high) / 2;
            if(temp < arr[mid]){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        for(j = i; j > high+1; j--){
            arr[j] = arr[j-1];
        }
        arr[high+1] = temp;
    }
    return arr;
}

希尔排序：O(nlog n)

public static int[] shellSort(int[] arr){
    int i,j,d,temp;
    for(d = arr.length/2; d > 0; d /= 2){
        for(i = d; i < arr.length; i++){
            temp = arr[i];
            for(j = i; j > 0 && arr[j-d] > temp; j -=d){
                arr[j] = arr[j-d];
            }
            arr[j] = temp;
        }
    }
    return arr;
}

2. 交换排序

冒泡排序：O(n^2)

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

快速排序：O(nlog2 n)

public static int partition(int[] arr,int i,int j){
    
    int temp = arr[i];  //基准
    while(i < j){
        while(i < j && temp <= arr[j]){
            j--;
        }
        arr[i] = arr[j];
        while(i < j && arr[i] < temp ){
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = temp;
    return i;
}

public static void quickSort(int[] arr,int i,int j){
    int mid;
    if(i < j){
        mid = partition(arr,i,j);
        quickSort(arr, i, mid-1);
        quickSort(arr, mid+1, j);
    }
}

3. 选择排序

简单选择排序：O(n^2)

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

堆排序：O(nlog2 n)

public static void sift(int[] arr,int low,int high){
    int i = low;    //父结点
    int j = i * 2;  //左子结点
    int temp = arr[i];  //临时保存根结点
    
    while(j <= high){
        if(j < high && arr[j] < arr[j+1]){
            j++;    //指向右子结点
        }
        if(temp < arr[j]){
            arr[i] = arr[j];  //较大子节点放入根节点
            i = j;
            j = i * 2;
        }else{
            break;  //默认左右子树是大根堆，若不用交换，当前结点的下面都是大根堆
        }
    }
    arr[i] = temp;      //最后筛选完成才将根节点与最后交换的结点互换
}

public static void heapSort(int[] arr){
    
    //建立初始堆
    int i,temp;
    int length = arr.length-1;
    for(i = length/2; i >= 0; i--){
        sift(arr,i,length);
    }
    
    // 走 n-1躺
    for(i = length; i >= 1; i--){
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;      //交换arr[1],arr[i]
        sift(arr,0,i-1);
    }
}

4. 归并排序

二路查找：O(nlog2 n)

public static void merge(int[] arr,int left,int mid,int right){
    int[] leftArr = new int[mid - left];
    int[] rightArr = new int[right - mid + 1];
    
    for(int i = left; i < mid; i++){
        leftArr[i - left] = arr[i];
    }
    for(int i = mid; i <= right; i++){
        rightArr[i - mid] = arr[i];
    }
    
    int i = 0, j = 0;
    int index = left;
    
    while(i < leftArr.length && j < rightArr.length){
        
        if(leftArr[i] < rightArr[j]){
            arr[index] = leftArr[i];
            i++;
            index++;
        }else{
            arr[index] = rightArr[j];
            j++;
            index++;
        }
    }
    
    while(i < leftArr.length){
        arr[index] = leftArr[i];
        i++;
        index++;
    }
    while(j < rightArr.length){
        arr[index] = rightArr[j];
        j++;
        index++;
    }
}

public static void mergeSort(int[] arr, int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid+1, right);
    }
}

5. 基数排序(桶排序，非计数排序)

// 返回最大值
private static int findMax(int[] arr){
    int temp = arr[0];
    for(int value : arr){
        if(temp < value){
            temp = value;
        }
    }
    return temp;
}

public static void radixSort(int[] arr){
    
    int max = findMax(arr);
    
    // 比较次数由最大值的位数决定
    for(int i = 1; max / i > 0; i *= 10){
        int[][] buckets = new int[arr.length][10];
        // 将每一个值根据当前比较的位数放入桶中
        for(int j = 0; j < arr.length; j++){
            int num = (arr[j] / i) % 10;
            buckets[j][num] = arr[j];
        }
        int k = 0;
        for(int m = 0; m < 10; m++){
            for(int n = 0; n < arr.length; n++){
                if(buckets[n][m] != 0){
                    arr[k++] = buckets[n][m];
                }
            }
        }
    }
}