文章目录

1.冒泡排序（Bubble Sort）

每轮比较最大的数字冒泡/交换到末位，下一轮遍历前n-1、遍历n-2

  • 重复遍历数组，依次比较相邻元素，若顺序错误则交换。每一轮遍历都会将当前未排序部分的最大元素“冒泡”到末尾。
  • 时间复杂度（平均/最坏）：数组倒序排序成正序 O(n²)
  • 时间复杂度（最好）：数组本来正序，遍历一次发现已经排好O(n)
  • 空间复杂度：O(1)
//从小至大排序
    public static void Bubble_Sort(int[] arr){
        int n = arr.length;
        for(int i=0;i<n;i++){
        //标识是否进行了交换遍历
            boolean flag = false;
            for(int j=0;j<n-i-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            //如果内循环遍历时发现每个j数<j+1数字，证明已经有序，直接break
            if(!flag) break;
        }
        System.out.println(Arrays.toString(arr));
    }

2.选择排序（Selection Sort）

每次从未排序部分选出最大/最小元素，放到已排序部分的末尾

  • 时间复杂度：O(n²)（始终）每次都要走遍内层循环
  • 空间复杂度：O(1)
//每次选出最大的，放到末尾n-i-1处，每次遍历前面一堆
public static void Selection_Sort(int[] arr){
    int n = arr.length;
    for(int i=0;i<n-1;i++){
        int max = 0;
        for(int j=0;j<n-i;j++){
            if(arr[j]>arr[max]){
                max = j;
            }
        }
        int temp = arr[n-i-1];
        arr[n-i-1] = arr[max];
        arr[max] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

//每次选出最小的，放到首位i处，每次遍历后面一堆
public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 将最小值交换到 i 位置
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

3.插入排序（Insertion Sort）

数组分为已排序和未排序两部分，将未排序的部分插入到已经有序的数组中

  • 将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。类似于打扑克牌时整理手牌的过程。
//数组{16,5,1,9,10,23,66};
//初始已排序{16}，未排序{5,1,9,10,23,66},待排序为5
{16}和5从右至左进行对比，比5大就右侧覆盖，直至到首位或者下一个数组比5小
//已排序{5，16}，未排序{1,9,10,23,66},待排序为1
{5，16}和1进行对比j=1，16>1,则{5，16，16}，j--,j=0，
此时5>1,则{5，5，16}，j--,j=-1，
j=-1,则{1，5，16}
//已排序{1，5，16}，未排序{9,10,23,66},待排序为9
第一次对比后为{1，5，16，16}
第二次对比后为{1，5，16，16}，j=1,，则设置arr[j+1]=arr[2]=9
  • 平均/最坏时间复杂度：O(n²)，数组倒序，排序为正序每次比较都比较到0位置
  • 最好时间复杂度 O(n)，本来有序，每次只需一次
  • 空间复杂度：O(1)
public static void InsertionSort(int[] arr) {
    int n = arr.length;
    //初始已排序的为1，未排序的为{arr[2]-arr[n-1]}
    for (int i = 1; i < n; i++) {
        int key = arr[i];//带比较数字
        int j = i - 1;//第一个比较的数字
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    System.out.println(Arrays.toString(arr));
}

4.快速排序（Quick Sort）

分治策略，每次选取基准，大于基准在右侧小于基准在左侧，依次分治选基准

  • 分治策略，选取基准值，将小于基准和大于基准的元素分别排到两侧，递归处理。
  • 平均时间复杂度：O(n log n)
  • 最坏时间复杂度：O(n²)（基准选取不当）
  • 空间复杂度：O(log n)（递归栈）
    在这里插入图片描述
private static void QuickSort(int[] arr,int left,int right) {
    if(arr.length<=1) return;
    if(left<right) {
        int pivot = partition(arr,left,right);//分区
        QuickSort(arr,0,pivot-1);//左子数组
        QuickSort(arr,pivot+1,right);//右子数组
    }
}
private static int partition(int[] arr,int left,int right) {
    int pivot = arr[left];//第一个元素作为基准,即左端元素
    int i = left;
    int j = right;
    while(i<j) {
        //先从右端开始,首次左侧的arr[i]就是基准值
        while( i<j && arr[j]>=pivot) j--;//从右端开始,找到第一个小于基准的元素
        if(i<j) {//交换i和j指向的元素,将小于基准的元素交换到左端
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
        }
        while(i<j&&arr[i]<=pivot) i++;//从左端开始,找到第一个大于基准的元素
        if(i<j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            j--;
        }
    }
    return i;
}
  • 也可以使用下面的顺序遍历的方式，比pivot大的放在位置不变，比pivot小的放在左侧，i位置记录当前（比pivot大的序列值的第一位的前一位），发现后续序列小于pivot时则进行交换，依次遍历完成排序。

在这里插入图片描述

private static void QuickSort(int[] arr,int left,int right) {
    if(left<right) {
        int pivot = partition(arr,left,right);//分区
        QuickSort(arr,0,pivot-1);//左子数组
        QuickSort(arr,pivot+1,right);//右子数组
    }
}
private static int partition(int[] arr,int left,int right) {
    //单向扫描
    int pivot = arr[right];//右侧作为基准
    int i = left-1;
    for(int j=left;j<=right;j++) {
        if(arr[j]<=pivot) {
            i++;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    return i;
}
public static void main(String[] args) {
    int[] arr = {16,5,1,9,10,4,7};
    QuickSort(arr,0,arr.length-1);
    System.out.println(Arrays.toString(arr));
}

5.归并排序（Merge Sort）

先按照左右平均分割数组，然后合并的时候进行排序

  • 同样采用分治思想，将数组递归分为两半，分别排序后合并。
  • 时间复杂度：O(n log n)（始终）
  • 空间复杂度：O(n)

在这里插入图片描述

//归并排序
private static void MergeSort(int[] arr,int left,int right) {
    if(left<right) {
        //int mid = (left+right)/2;
        int mid = left+(right-left)/2;
        MergeSort(arr,left,mid);//左子数组
        MergeSort(arr,mid+1,right);//右子数组
        Merge(arr,left,mid,right);//合并
    }
}
private static void Merge(int[] arr,int left,int mid,int right) {
    int[] temp = new int[right-left+1];//临时数组
    int i = left;//左子数组指针
    int j = mid+1;//右子数组指针
    int k = 0;//临时数组指针
    while(i<=mid && j<=right) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    //左子数组剩余元素（如果有）直接拷贝到 temp
    while(j<=right) {
        temp[k++] = arr[j++];
    }
    //右子数组剩余元素（如果有）直接拷贝到 temp
    while(i<=mid) {
        temp[k++] = arr[i++];
    }
    for (k = 0; k < temp.length; k++) {
        arr[left+k] = temp[k];
    }
}
  • 不使用 int mid = (left+right)/2 而采用 int mid = left+(right-left)/2 的原因：int 类型的最大值是 2,147,483,647。如果 left 和 right 都非常大，计算 (left + right) 可能会超过了 int 的最大值。

6.堆排序（Heap Sort）

每次构建大顶堆，将堆顶元素与最后一位互换，剩余的小堆再构建大顶堆

  • 构建大顶堆，将堆顶（最大值）与末尾交换，缩小堆范围并调整。
  • 时间复杂度：O(n log n)（始终）
  • 空间复杂度：O(1)

堆构建过程
在这里插入图片描述

堆排序过程
在这里插入图片描述

//先建堆，再排序
private static void HeapSort(int[] arr) {
    //建堆，从下往上，从右往左，建大根堆
    if(arr.length<=1) {return;}
    for (int i = arr.length/2-1; i >= 0; i--) {
        AdjustHeap(arr,arr.length-1,i);
    }
    //排序：每次把堆顶（最大值）换到最后，缩小堆，再调整
    for (int i = arr.length-1; i > 0; i--) {
        //将堆顶元素（最大值）交换到数组末尾
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //调整堆顶元素（最大值），保持堆的性质
        AdjustHeap(arr,i-1,0);
    }
}

private static void AdjustHeap(int[] arr, int n, int i) {
    int max = i;
    int left = 2*i+1;
    int right = 2*i+2;
    //判断左子树是否大于父节点
    if(left<=n && arr[left]>arr[max]) {
        max = left;
    }
    //判断右子树是否大于父节点
    if(right<=n && arr[right]>arr[max]) {
        max = right;
    }
    //最大值交换到父节点位置
    if(max!=i) {
        int temp = arr[max];
        arr[max] = arr[i];
        arr[i] = temp;
        //因为交换了父节点，所以子树可能被破坏，所以需要递归调整子树
        AdjustHeap(arr,n,max);
    }
}

7.计数排序（Counting Sort）

按照值统计出现的次数，最后再倒序拷贝到新数组上

  • 先数清楚每个数字出现了几次，再算出每个数字应该占据的位置区间，最后直接把所有数字放到正确的位置上。适用于数据范围较小（如 0~1000）的非负整数。
  • 时间复杂度：O(n + k)（k 为数据范围）
  • 空间复杂度：O(n + k)
arr = {14,7,8,6,4,2,8,6,10,10};
count ={1,0,1,0,2,1,2,0,2,0,0,0,1}
//count从左至右/从右至左进行遍历赋值到arr中

//计数排序
private static void CountingSort(int[] arr) {
    //找出min和max确定数据范围
    int min = arr[0];
    int max = arr[0];
    //min=2，max=14
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    //构建count数组,统计每个元素出现的次数,数组长度为max-min+1=13
    int[] count = new int[max-min+1];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i]-min]++;//索引 = 实际值 - 偏移量
    }
    //将count数组转换为arr数组
    int index = arr.length-1;
    for (int i = count.length-1; i >= 0; i--) {
        while (count[i] > 0) {
            arr[index--] = i+min;
            count[i]--;
        }
    }
    System.out.println(Arrays.toString(arr));
}
  • 上面的这种解法可以实现宏观上的排序，但会有不稳定的问题，例如原始arr数组中A（2分）、B（1分） C（2分），最终得到的结果可能变成 [B, C, A]，而不是[B, A, C]，此时可以使用前缀和，倒序遍历原数组进行填充。如下所示，
arr = {14,7,8,6,4,2,8,6,10,10};
count ={1,0,1,0,2,1,2,0,2,0,0,0,1}
//累加后的count,表示小于等于该值的数字有几个
count = {1,1,2,2,4,5,7,7,9,9,9,9,10 }
value = 10 index = count[value-min]-1=8表示value=10这个值在arr中放置的位置，因为count[value-min]=9表示小于等于10的数字有9个，不管前面有几个10，因为是从右至左因此，优先放在右侧放置在位置index=8，这个位置放置好后count[value-min]--
......
下一次又是value = 10,此时count[value-min]=8表示小于等于10的数字有8个，index = count[value-min]-1=7，则放在位置7处。这样从右至左保证有序。

在这里插入图片描述

//计数排序(稳定版)
private static void CountingSort(int[] arr) {
    //找出min和max确定数据范围
    int min = arr[0];
    int max = arr[0];
    //min=2，max=14
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }
    //构建count数组,统计每个元素出现的次数,数组长度为max-min+1=13
    int[] count = new int[max-min+1];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i]-min]++;//索引 = 实际值 - 偏移量
    }
    //前缀和
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i-1];
    }
    //创建输出数组，倒序遍历
    int[] output = new int[arr.length];
    for (int i = arr.length-1; i >= 0; i--) {
        int val = arr[i];
        int index = count[val-min] - 1;
        output[index] = val;
        count[val-min]--;
    }
    System.arraycopy(output,0,arr,0,output.length);
    System.out.println(Arrays.toString(arr));
}

8.桶排序（Bucket Sort）

类似计数排序，将元素分配到固定范围的桶内，桶内排序后，再合并到原数组

  • 根据数值范围将元素分散到多个有序桶中，各桶独立排序后再按顺序合并，利用数据的均匀分布来达到线性时间效率。适用于数据均匀分布如 [0, 1, 2, 100, 101, 102]）且数据范围已知的场景
  • 平均时间复杂度：O(n + k)
  • 最坏时间复杂度 O(n²)（所有元素落入一桶）
  • 空间复杂度：O(n + k)

在这里插入图片描述

private static void BucketSort(int[] arr,int bucketSize) {
    //找出min和max确定数据范围
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min,arr[i]);
        max = Math.max(max,arr[i]);
    }
    if(min == max) return;
    //创建桶
    int bucketNum = (max - min)/bucketSize + 1;
    List<List<Integer>> bucket = new ArrayList<>();
    for (int i = 0; i < bucketNum; i++) {
        bucket.add(new ArrayList<>());
    }
    //将元素放入桶中
    for (int i = 0; i < arr.length; i++) {
        int index = (arr[i] - min)/bucketSize;
        bucket.get(index).add(arr[i]);
    }
    int index = 0;
    //对每个桶中的元素进行排序,并合并到原数组中
    for (int i = 0; i < bucketNum; i++) {
        bucket.get(i).sort(null);//也可Collections.sort(bucket.get(i));
        //合并桶中的元素到原数组中
        for (int j: bucket.get(i)) {
            arr[index++] = j;
        }
    }
    System.out.println(Arrays.toString(arr));
}

9.基数排序（Radix Sort）

按照个位->十位->百位依次排序，每次排序为计数排序（稳定性），最终得到的数字天然有序

  • 不直接比较数字整体大小，而是从低位到高位/高位到低位逐位分配，利用稳定排序（如计数排序）确保每次排序后相对顺序保留，经过所有位数的处理后自然有序。
  • 时间复杂度：O(k × n)（k 为最大位数）
  • 空间复杂度：O(n + k)

在这里插入图片描述

private static void RadixSort(int[] arr) {
    //找出最大数的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    //最大数有几位
    int maxDigit = 0;
    while (max != 0) {
        max /= 10;
        maxDigit++;
    }
    //根据位数进行排序
    for (int i = 0; i < maxDigit; i++) {
        //根据当前位数进行计数排序
        CountingSort(arr,i);
    }
}
//根据当前位数进行计数排序
private static void CountingSort(int[] arr,int digit) {
    //digit位组成的数组（也可直接用arr[i] % 10获取，减少空间复杂度）
    int[] digitArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        digitArr[i]=arr[i] / (int) Math.pow(10,digit) % 10;
    }

    //下面是计数排序的逻辑(注意此时的digitArr范围是[0,9],因此可以不用找最大最小值，可直接进行存储)
    //创建计数数组
    int[] count = new int[10];
    for (int i = 0; i < arr.length; i++) {
        count[digitArr[i]]++;
    }
    //将count数组转换为累加数组
    for (int i = 1; i < 10; i++) {
        count[i] += count[i-1];
    }
    int[] temp = new int[arr.length];
    for (int i = arr.length-1; i >= 0; i--) {
        temp[count[digitArr[i]]-1] = arr[i];
        count[digitArr[i]]--;
    }
    //temp拷贝到原数组
    System.arraycopy(temp,0,arr,0,arr.length);
}
  • digit位组成的数组（也可直接用arr[i] % 10获取，减少空间复杂度）
private static void CountingSort(int[] arr,int digit) {
    //下面是计数排序的逻辑(注意此时的digitArr范围是[0,9],因此可以不用找最大最小值，可直接进行存储)
    //创建计数数组
    int digitCount = (int) Math.pow(10,digit);
    int[] count = new int[10];
    for (int i = 0; i < arr.length; i++) {
        count[(arr[i] / digitCount) % 10]++;
    }
    //将count数组转换为累加数组
    for (int i = 1; i < 10; i++) {
        count[i] += count[i-1];
    }
    int[] temp = new int[arr.length];
    for (int i = arr.length-1; i >= 0; i--) {
        int index = (arr[i] / digitCount) % 10;
        temp[count[index]-1] = arr[i];
        count[index]--;
    }
    //temp拷贝到原数组
    System.arraycopy(temp,0,arr,0,arr.length);
}
# 排序算法 # 算法 # 数据结构
Logo
乐奇 Rokid 开放社区

更多推荐

cover

微安级唤醒、2节干电池直供：CI3422如何重新定义电池供电设备的语音交互

avatar 乐奇 Rokid 开放社区
cover

基于 Rokid AIUI：从一句咒语到一副眼镜，我做了款 AR 寻宝游戏《寻宝猎手》

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区