排序算法

2024 年 4 月 18 日 星期四(已编辑)
21
这篇文章上次修改于 2024 年 7 月 30 日 星期二，可能部分内容已经不适用，如有疑问可询问作者。

排序算法

O(n^2)排序

选择排序

//选择排序
public static void selectionSort(int[] arr) {
    // 选最小的放第一个
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int mindex = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[mindex] > arr[j]) {
                mindex = j;
            }
        }
        swap(arr, mindex, i);
    }
}

冒泡排序

//冒泡排序
public static void bubbleSort(int[] arr) {
    // 大的往后冒
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j + 1, j);
            }
        }
    }
}

插入排序

//插入排序
public static void insertionSort(int[] arr) {
    // 往前面有序序列插入
    // 最好情况O(N)
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i; j >= 0 && arr[j + 1] < arr[j]; j--) {
            swap(arr, j + 1, j);
        }
    }
}

对数器

用来测试算法是否正确，将自己写的算法与正确的算法对比结果

public static int[] generaRandomArray(int maxSize, int maxValue) {
    // Math.random()->[0,1)所有的小数，等概率返回一个
    // Math.random()*N->[0,N)所有小数，等概率返回一个
    // (int)(Math.random()*N)->[0,N-1]所有的整数，等概率返回一个
    int[] arr = new int[(int) (Math.random() * (maxSize + 1))]; // 长度随机
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * (maxValue + 1));
        // arr[i] = (int)(Math.random()*(maxValue+1)) -
        // (int)(Math.random()*(maxValue));//需要负数用这个
    }
    return arr;
}
public static void main(String[] args) {

    //对数器
    int testTime = 5000;
    int maxSize = 100;
    int maxValue = 100;
    String info = "true";
    for (int i=0;i<testTime;i++){
        int[] arr1 = generaRandomArray(maxSize, maxValue);
        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        bubbleSort(arr1);
        insertionSort(arr2);
        if(!Arrays.equals(arr1,arr2)){
            info = "false";
            break;
        }
    }
    System.out.println(info);


}

完整代码及测试用例

import java.util.Arrays;

public class n2 {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //选择排序
    public static void selectionSort(int[] arr) {
        // 选最小的放第一个
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int mindex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[mindex] > arr[j]) {
                    mindex = j;
                }
            }
            swap(arr, mindex, i);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arr) {
        // 大的往后冒
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j + 1, j);
                }
            }
        }
    }

    //插入排序
    public static void insertionSort(int[] arr) {
        // 往前面有序序列插入
        // 最好情况O(N)
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0 && arr[j + 1] < arr[j]; j--) {
                swap(arr, j + 1, j);
            }
        }
    }

    public static int[] generaRandomArray(int maxSize, int maxValue) {
        // Math.random()->[0,1)所有的小数，等概率返回一个
        // Math.random()*N->[0,N)所有小数，等概率返回一个
        // (int)(Math.random()*N)->[0,N-1]所有的整数，等概率返回一个
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))]; // 长度随机
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
            // arr[i] = (int)(Math.random()*(maxValue+1)) -
            // (int)(Math.random()*(maxValue));//需要负数用这个
        }
        return arr;
    }

    public static void main(String[] args) {
        // // 选择冒泡插入排序测试
        // int[] arr = { 4, 5, 7, 3, 2, 1, 6, 9, 8, 1, 1, 10 };
        // // selectionSort(arr);
        // // bubbleSort(arr);
        // // insertionSort(arr);
        // for (int i : arr) {
        //     System.out.println(i);
        // }

        //对数器
        int testTime = 5000;
        int maxSize = 100;
        int maxValue = 100;
        String info = "true";
        for (int i=0;i<testTime;i++){
            int[] arr1 = generaRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            bubbleSort(arr1);
            insertionSort(arr2);
            if(!Arrays.equals(arr1,arr2)){
                info = "false";
                break;
            }
        }
        System.out.println(info);


    }

}

O(nlogn)排序

归并排序

// 归并排序
public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right || arr == null) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    while (p1 <= mid && p2 <= right) { // 取小的合并
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }
    for (int j = 0; j < temp.length; j++) {
        arr[left + j] = temp[j];
    }
}

快速排序

// 快速排序
public static void quikSort(int[] arr, int L, int R) {
    if (L < R) {
        int randIndex = L + (int) (Math.random() * (R - L + 1));// 选取随机位置作为枢纽
        swap(arr, R, randIndex);
        int p = partition2(arr, L, R);
        quikSort(arr, L, p - 1);
        quikSort(arr, p + 1, R);
    }
}

// 单边循环划分
public static int partition1(int[] arr, int L, int R) {
    int less = L - 1; // 小于区边界
    for (int i = L; i < R; i++) {
        if (arr[i] < arr[R]) { // 当前数小于枢纽
            swap(arr, ++less, i);
        }
    }
    swap(arr, R, less + 1);
    return less + 1;
}

// 双边循环划分
public static int partition2(int[] arr, int L, int R) {
    int less = L - 1;// 小于区域边界
    int more = R;// 大于区域边界
    int i = L;// 工作指针
    while (i < more) {
        if (arr[i] < arr[R]) { // 当前数<枢纽
            swap(arr, ++less, i++);
        } else if (arr[i] > arr[R]) { // 当前数>枢纽
            swap(arr, --more, i);// i不动，因为还没有比较过
        } else {
            i++;
        }
    }
    swap(arr, R, less + 1);
    return less + 1;
}

堆排序

// 堆排序
public static void heapSort(int[] arr) {
    buildMaxHeap1(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, 0, i);
    }
}


// 向下调整，小元素下坠
public static void maxHeapify(int[] arr, int root, int heapSize) {
    int largest = root;// 初始化最大元素的位置为根节点
    while (true) {
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        // 找到左、右子节点中值最大的节点的位置
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大元素的位置不是根节点，交换它们，并更新当前节点位置
        if (largest != root) {
            swap(arr, largest, root);
            root = largest;
        } else {
            break;
        }
    }
}

// 向上调整，大元素上升
public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) { // index/2-1作为父节点的话，在0时可能为负数
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// 建大根堆方法1
public static void buildMaxHeap1(int[] arr) {
    // 从最后一个非叶子节点开始，依次向上调整每个节点，使得每个子树都是最大堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}
// 建大根堆方法2
public static void buildMaxHeap2(int[] arr) {
    //依次插入变成大根堆
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
}

排序思想应用

归并排序思想应用

求小和

// 归并排序思想求小和
// 小和：[1,3,4,2,5] 左边比它小的数相加 1+3+1+1+10
public static int getSmallSum(int[] arr, int l, int r) {
    if (l >= r || arr == null) {
        return 0;
    }
    int m = l + ((r - l) >> 1);
    int a = getSmallSum(arr, l, m);
    int b = getSmallSum(arr, m + 1, r);
    int c = sumMerge(arr, l, m, r);
    return a + b + c;
}

public static int sumMerge(int[] arr, int l, int m, int r) {
    int[] temp = new int[r - l + 1];
    int sum = 0;
    int p1 = l;
    int p2 = m + 1;
    int i = 0;
    while (p1 <= m && p2 <= r) {
        if (arr[p1] < arr[p2]) {
            sum += arr[p1] * (r - p2 + 1); // 计算每次归并的小和，归并排序比较 所在的地方
            temp[i++] = arr[p1++];
        } else {
            temp[i++] = arr[p2++];
        }
    }
    /*
         * 越界后不计算小和，因为这个算法本质是利用归并排序不浪费比较次数的特点（排序必定最少要来两两比较一次）
         * 比较过的信息保存下来，所以只在每次比较的时候计算小和，这样就不会多算也不会少算
         */
    while (p1 <= m) {
        temp[i++] = arr[p1++];
    }
    while (p2 <= r) {
        temp[i++] = arr[p2++];
    }
    for (int j = 0; j < temp.length; j++) {
        arr[l + j] = temp[j];
    }
    return sum;
}

堆排序思想应用

相对有序排序

//相对有序的序列排序
//一个数离他正确顺序位置不超过k为相对有序
public static void distanceLessKSort(int []arr,int k){
    //优先级队列就是堆，默认小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    //建大小为k的堆
    for(int i=0;i<= Math.min(arr.length-1, k);i++){
        heap.add(arr[i]);
    }
    //出堆一定依次有序
    int index = 0;
    for(int j = k+1;j<arr.length;index++,j++){
        heap.add(arr[j]);
        arr[index] = heap.poll();
    }
    while (!heap.isEmpty()) {
        arr[index++] = heap.poll();
    }
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...