常见排序算法

2025-02-12

总结常见的10中排序模型

本文主要汇总下常见的10中排序模型，用一张图概括如下：

时间复杂度与空间复杂度

排序稳定性：相同元素的排序后顺序是否是固定的

冒泡排序

两次循环，每个都和后面的数进行比较，如果当前数大于后面的数则交换位置。
每循环一次，当前的最后的一个数为当次循环的最大数。

public static void sort(int[] ints){
        for (int i = 0; i < ints.length-1; i++) {
            for (int j = 0; j < ints.length-i-1; j++) {
                if(ints[j]>ints[j+1]){
                    swap(ints,j,j+1);
                }
            }
        }
    }

选择排序

找到数组（0 - n）中的最大值，放到数组最后。
在循环找到数组（0 - n-1）中的最大值，放到n-1的位置，如此循环知道最后完成。

private static void sort(int[] ints){
    for (int i = 0; i < ints.length; i++) {
        int minNum = ints[i];
        int index = i;
        for (int j = i + 1; j < ints.length; j++) {
            if(ints[j] < minNum){
                minNum = ints[j];
                index = j;
            }
        }
        if(i!=index){
            swap(ints,i,index);
        }
    }
}

插入排序

两层遍历，二层遍历遍历当前index前面的值，如果当前值小于前面的值，则交换位置
知道前面的值小于等于当前值

private static void sort(int[] ints){
    for (int i = 0; i < ints.length; i++) {
        int index = i;
        for (int j = i - 1; j >= 0 ; j--) {
            if(ints[index] < ints[j]){
                swap(ints,index,j);
                index--;
            }else {
                break;
            }
        }
    }
}

计数排序

将当前数组中的值转化为一个新数组的下标。
新数组的值为当前下标在目标数组中的个数，新数组的大小为最大值 - 最小值 + 1。
最后将新数组中的值按顺序重新复制到老数组中。
如果最大值和最小值相差太多的，会存在空间浪费的情况。

private static void sort(int[] ints){
    // 找最大最小值
    int max = ints[0];
    int min = ints[0];
    for (int i = 1; i < ints.length; i++) {
        if(ints[i]>max){
            max = ints[i];
        }
        if(ints[i]<min){
            min = ints[i];
        }
    }
    // 创建新数组 大小为 max - min + 1
    int[] temp = new int[max - min + 1];
    // 将当前数组中的值存入到新数组中
    for (int i : ints) {
        temp[i-min]++;
    }
    // 新数组的值又重新赋值回去
    int index = 0;
    for (int i = 0; i < temp.length; i++) {
        int i1 = temp[i];
        if(i1>0){
            for (int i2 = 0; i2 < i1; i2++) {
                ints[index] = i+min;
                index++;
            }
        }
    }
}

桶排序

将数组中的值按照大小分到固定几个桶中。
将每个桶中的数据都分别进行排序(使用其它的排序算法，如插入排序)。
最后将每个桶中的数据重新复制到原数组中。

// num 为桶的个数
private static void bucketSort(int[] ints,int num){
    // 查找数组中的最大最小值
    int max = ints[0];
    int min = ints[0];
    for (int i = 1; i < ints.length; i++) {
        if(ints[i]>max){
            max = ints[i];
        }
        if(ints[i]<min){
            min = ints[i];
        }
    }
    // 不是根据个数，是根据数组中值的大小 计算桶的容量
    int count =  (max - min) / num + 1;
    int[][] bucket = new int[num][0];
    // 根据值的大小放到不同的桶中去
    for (int anInt : ints) {
        int index = (anInt - min) / count;
        bucket[index] = appendBucket(bucket[index],anInt);
    }
    int mainIndex = 0;
    // 将每个桶进行排序 并赋值到原来的数组中
    for (int[] ints1 : bucket) {
        if(ints1.length<=0){
            continue;
        }
        // 排序 此处使用插入排序 也可以用其它的排序方式
        for (int i = 0; i < ints1.length; i++) {
            int index = i;
            for (int j = i-1; j >= 0; j--) {
                if(ints1[j]>ints1[index]){
                    swap(ints1,index,j);
                    index--;
                }
            }
        }
        for (int i : ints1) {
            ints[mainIndex] = i;
            mainIndex++;
        }
    }
}

// 向数组中添加元素
public static int[] appendBucket(int[] bucket , int anInt){
    int[] ints = Arrays.copyOf(bucket, bucket.length + 1);
    ints[ints.length-1] = anInt;
    return ints;
}

基数排序

按照数据的位数来排序，方式类型桶排序，只是桶中的数据不用再排序了。
固定10个桶，编号0-9。
从个、十、百…位开始遍历，位数比较小的补0。
每次遍历将值放到对应位数的数字对应桶中，然后合并。


private static void sort(int[] ints){
    // 获取最大的数的长度
    int maxLength = getMaxLength(ints);
    // 从个位开始遍历
    for (int i = maxLength-1; i >= 0; i--) {
        baseSort(ints,i,maxLength);
    }

}


private static void baseSort(int[] ints,int index,int maxLength){
    // 固定10个桶
    int[][] base = new int[10][0];
    for (int i = 0; i < ints.length; i++) {
        // 获取当前值在第几位上的数
        int intIndex = getIntIndex(ints[i], index, maxLength);
        // 放到对应的桶里去
        base[intIndex] = appendBucket(base[intIndex],ints[i]);
    }
    // 再合并起来 此时不用再排序
    int mainIndex = 0;
    for (int[] ints1 : base) {
        if(ints1.length<=0){
            continue;
        }
        for (int i : ints1) {
            ints[mainIndex] = i;
            mainIndex++;
        }
    }
}

// 获取第几位的数
private static int getIntIndex(int i,int index,int maxLength){
    String s = String.valueOf(i);
    int length = s.length();
    if(length + index < maxLength){
        return 0;
    }
    char c = s.charAt(index - maxLength + length);
    return Integer.parseInt(String.valueOf(c));
}

// 获取最大数的长度
private static int getMaxLength(int[] ints){
    int max = ints[0];
    for (int anInt : ints) {
        if(anInt>max){
            max = anInt;
        }
    }
    return String.valueOf(max).length();
}

// 向数组中添加一个元素
public static int[] appendBucket(int[] bucket , int anInt){
    int[] ints = Arrays.copyOf(bucket, bucket.length + 1);
    ints[ints.length-1] = anInt;
    return ints;
}

希尔排序

拆分 -> 每组插入排序 -> 拆分 -> 每组插入排序 …
只到最终拆分成每组的间隔只有1

private static void sort(int[] ints){
    // 首先要进行分组 然后进行插入排序 间隔为长度 / 2 ... 一直到长度为1
    for (int step = ints.length/2; step > 0 ; step /= 2) {
        // 每次都进行一次插入排序
        for (int i = step; i < ints.length; i++) {
            // 当前值
            int index = i;
            for (int j = i-step; j >= 0 ; j-=step) {
                if(ints[j]>ints[index]){
                    swap(ints,index,j);
                    index = j;
                }else {
                    break;
                }
            }
        }
    }
}

快速排序

找到一个基准值然后设置左右两个指针，当左边的大于基准值、右边的小于基准值，则交换位置
当左指针>=右指针时与基准值交换位置
再分别重复基准值左边的部分和右边的部分，知道里面的拆分里面的元素只有一个

private static void sort(int[] param,int left ,int right){
    // 里面元素只有一个的时候结束递归
    if(left>=right){
        return;
    }
    // 找到基准值的位置
    int partition = partition(param, left, right);
    // 继续递归左边的数据
    sort(param,left,partition-1);
    // 继续递归右边的数据
    sort(param,partition+1,right);
}

// 找基准值
private static int partition(int[] param,int left ,int right){
    // 直接以第一个为基准值
    int pivot = param[left];
    int index = left;
    while (left<right){
        while (right>left){
            // 如果右边有值小于基准值 则交换位置
            if(param[right] < pivot){
                swap(right,index,param);
                index = right;
                left++;
                break;
            }
            right--;
        }
        // 如果左边有值大于基准值 则与基准值交换位置
        while (right>left){
            if(param[left] > pivot){
                swap(left,index,param);
                index = left;
                right--;
                break;

            }
            left++;
        }
    }
    // 返回基准值的位置
    return index;
}

归并排序

先将数组进行拆分，一直拆到只有一个元素
再将数组进行合并，合并的时候进行排序


// 先用递归进行拆分 知道里面只有一个元素为止
public static void sort(int[] ints,int left,int right){
    int mid = (right+left) / 2;
    if(left<right){
        sort( ints, left, mid);
        sort( ints, mid+1, right);
        merge(ints ,left,mid,right);
    }
}

// 开始进行合并
public static void merge(int[] ints,int left,int mid,int right){

    // 构建一个临时数组 并记录左边的下标和右边的下标
    int[] temp = new int[right-left+1];
    int k = 0;
    int i = left;
    int j = mid+1;

    // 左边和右边都有值的时候 直接比较 按顺序赋值
    while (i<=mid && j<=right){
        if(ints[i]<ints[j]){
            temp[k] = ints[i];
            i++;
        }else {
            temp[k] = ints[j];
            j++;
        }
        k++;
    }

    // 只有左边有值 直接将左边的赋值过去
    while (i<=mid){
        temp[k] = ints[i];
        i++;
        k++;
    }
    // 只有右边有值 直接将右边的赋值过去
    while (j<=right){
        temp[k] = ints[j];
        j++;
        k++;
    }

    // 临时数组重新赋值回去
    for (int i1 = 0; i1 < temp.length; i1++) {
        ints[left+i1] = temp[i1];
    }
}