常规的排序算法

小半 • 2022年5月27日下午5:06 • 后端开发 • 阅读 98

在此列举常用简单的排序算法，冒泡、插入、归并和快排，后边有机会再添加其他排序方法。

冒泡排序

思想：每次交换相邻元素，时间复杂度为O(N^2)

private static void bubbleSort(int[] n) {
        //相邻元素交换位置，时间复杂度为O（N^2）
        for(int i = 0; i < n.length; i++) {
            for(int j = 0; j < n.length-1; j++) {
                if(n[j] > n[j+1]) {
                    int tmp = n[j];
                    n[j] = n[j+1];
                    n[j+1] = tmp;
                }
            }
        }
    }

插入排序

思想：每次从后边获取一个元素，与前边已排好序的元素比较，时间复杂度O(N^2)

private static void insertSort(int[] n) {
        //插入排序：每次从后边获取一个元素，与前边已排好序的元素比较，时间复杂度O(N^2)
        for(int i = 1; i < n.length; i++) {
            //与前边已排序的元素比较
            for(int j = i; j > 0; j--) {
                if(n[j-1] > n[j]) {
                    int tmp = n[j-1];
                    n[j-1] = n[j];
                    n[j] = tmp;
                }else {
                    break;
                }
            }
        }
    }

归并排序

/**
     * 归并排序：分治思想，将数组分成两部分，两部分排好序后，进行合并
     * 从下往上，即从短有序数组到长有序数组
     * @param n
     */
    private static void mergeSort(int[] n) {
        merge(n, 0, n.length-1);
    }
    
    private static void merge(int[] n, int start, int end) {
        if(start == end) return;
        
        //分
        int mid = (start + end)/2;
        merge(n, start, mid);
        merge(n, mid+1, end);
        
        //治，合并
        int[] tmp = new int[end-start+1];
        int i = 0;
        int p = start;
        int q = mid+1;
        while(p <= mid && q <= end) {
            if(n[p] > n[q]) {
                tmp[i++] = n[q++];
            } else {
                tmp[i++] = n[p++];
            }
        }
        if(p == mid+1) {
            while(q <= end) tmp[i++] = n[q++];
        }
        if(q == end+1) {
            while(p <= mid) tmp[i++] = n[p++];
        }
        for(int t : tmp) {
            n[start++] = t;
        }
    }

快速排序

private static void quickSort1(int[] n) {
        quick1(n, 0, n.length-1);
    }
    
    //挖坑思想，先挖low的元素，从右往左遍历到小于基准的，移到low坑；被移的高位变成坑，用于从左往右大于基准的填。
    //知道前后指针相遇
    private static void quick1(int[] n, int start, int end) {
        if(start >= end) return;
        
        int tmp = n[start];//参照
        int p = start;
        int q = end;
        while(p < q) {
            //从右往左遍历小于基准的
            while(p < q && n[q] > tmp) q--;
            if(p < q) {
                n[p] = n[q];
                p++;
            }
            //从左往右遍历大于基准的
            while(p < q && n[p] < tmp) p++;
            if(p < q) {
                n[q] = n[p];
                q--;
            }
        }
        //结束循环时，p=q
        n[p] = tmp;
        
        quick1(n, start, p-1);
        quick1(n, p+1, end);
    }