十大排序算法(代码+图解)

比眉伴天荒 2024-04-01 10:58 158阅读 0赞

在这里插入图片描述

算法中稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序，这是我们不愿意看到的。我们在使用排序算法或者选择排序算法时，更希望这个次序不会改变，更加稳定，所以排序算法的稳定性，是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样，有时候甚至比时间复杂度、空间复杂度更重要一些。所以往往评价一个排序算法的好坏往往可以从下边几个方面入手：

（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。

（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

（3）使用场景：排序算法有很多，不同种类的排序算法适合不同种类的情景，可能有时候需要节省空间对时间要求没那么多，反之，有时候则是希望多考虑一些时间，对空间要求没那么高，总之一般都会必须从某一方面做出抉择。

（4）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素。

1.冒泡排序

图解

在这里插入图片描述

算法步骤

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

参考代码

  1. // Java 代码实现
  2. public class BubbleSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          for (int i = 1; i < arr.length; i++) {
  13.             // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
  14.             boolean flag = true;
  16.             for (int j = 0; j < arr.length - i; j++) {
  18.                 if (arr[j] > arr[j + 1]) {
  20.                     int tmp = arr[j];
  21.                     arr[j] = arr[j + 1];
  22.                     arr[j + 1] = tmp;
  24.                     flag = false;
  25.                 }
  26.             }
  28.             if (flag) {
  30.                 break;
  31.             }
  32.         }
  33.         return arr;
  34.     }
  35. }

2.选择排序

图解

在这里插入图片描述

算法步骤

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  • 重复第二步，直到所有元素均排序完毕。

参考代码

  1. //Java 代码实现
  2.  public class SelectionSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  10.          // 总共要经过 N-1 轮比较
  11.          for (int i = 0; i < arr.length - 1; i++) {
  13.             int min = i;
  15.             // 每轮需要比较的次数 N-i
  16.             for (int j = i + 1; j < arr.length; j++) {
  18.                 if (arr[j] < arr[min]) {
  20.                     // 记录目前能找到的最小值元素的下标
  21.                     min = j;
  22.                 }
  23.             }
  25.             // 将找到的最小值和i位置所在的值进行交换
  26.             if (i != min) {
  28.                 int tmp = arr[i];
  29.                 arr[i] = arr[min];
  30.                 arr[min] = tmp;
  31.             }
  33.         }
  34.         return arr;
  35.     }
  36. }

3.插入排序

图解

插入排序

算法步骤

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

参考代码

  1. //Java 代码实现
  2.  public class InsertSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
  12.         for (int i = 1; i < arr.length; i++) {
  15.             // 记录要插入的数据
  16.             int tmp = arr[i];
  18.             // 从已经排序的序列最右边的开始比较，找到比其小的数
  19.             int j = i;
  20.             while (j > 0 && tmp < arr[j - 1]) {
  22.                 arr[j] = arr[j - 1];
  23.                 j--;
  24.             }
  26.             // 存在比其小的数，插入
  27.             if (j != i) {
  29.                 arr[j] = tmp;
  30.             }
  32.         }
  33.         return arr;
  34.     }
  35. }

4.希尔排序

图解

在这里插入图片描述

算法步骤

  • 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  • 按增量序列个数 k，对序列进行 k 趟排序；
  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

参考代码

  1. //Java 代码实现
  2.  public class ShellSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          int gap = 1;
  12.         while (gap < arr.length) {
  14.             gap = gap * 3 + 1;
  15.         }
  17.         while (gap > 0) {
  19.             for (int i = gap; i < arr.length; i++) {
  21.                 int tmp = arr[i];
  22.                 int j = i - gap;
  23.                 while (j >= 0 && arr[j] > tmp) {
  25.                     arr[j + gap] = arr[j];
  26.                     j -= gap;
  27.                 }
  28.                 arr[j + gap] = tmp;
  29.             }
  30.             gap = (int) Math.floor(gap / 3);
  31.         }
  33.         return arr;
  34.     }
  35. }

5.归并排序

图解

在这里插入图片描述

算法步骤

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  • 重复步骤 3 直到某一指针达到序列尾；
  • 将另一序列剩下的所有元素直接复制到合并序列尾

参考代码

  1. public class MergeSort implements IArraySort {
  4.      @Override
  5.      public int[] sort(int[] sourceArray) throws Exception {
  7.          // 对 arr 进行拷贝，不改变参数内容
  8.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  10.          if (arr.length < 2) {
  12.              return arr;
  13.         }
  14.         int middle = (int) Math.floor(arr.length / 2);
  16.         int[] left = Arrays.copyOfRange(arr, 0, middle);
  17.         int[] right = Arrays.copyOfRange(arr, middle, arr.length);
  19.         return merge(sort(left), sort(right));
  20.     }
  22.     protected int[] merge(int[] left, int[] right) {
  24.         int[] result = new int[left.length + right.length];
  25.         int i = 0;
  26.         while (left.length > 0 && right.length > 0) {
  28.             if (left[0] <= right[0]) {
  30.                 result[i++] = left[0];
  31.                 left = Arrays.copyOfRange(left, 1, left.length);
  32.             } else {
  34.                 result[i++] = right[0];
  35.                 right = Arrays.copyOfRange(right, 1, right.length);
  36.             }
  37.         }
  39.         while (left.length > 0) {
  41.             result[i++] = left[0];
  42.             left = Arrays.copyOfRange(left, 1, left.length);
  43.         }
  45.         while (right.length > 0) {
  47.             result[i++] = right[0];
  48.             right = Arrays.copyOfRange(right, 1, right.length);
  49.         }
  51.         return result;
  52.     }
  54. }

6.快速排序

图解

在这里插入图片描述

算法步骤

  • 从数列中挑出一个元素，称为 “基准”（pivot）;
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

参考代码

  1. //Java 代码实现
  2.  public class QuickSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          return quickSort(arr, 0, arr.length - 1);
  12.     }
  14.     private int[] quickSort(int[] arr, int left, int right) {
  16.         if (left < right) {
  18.             int partitionIndex = partition(arr, left, right);
  19.             quickSort(arr, left, partitionIndex - 1);
  20.             quickSort(arr, partitionIndex + 1, right);
  21.         }
  22.         return arr;
  23.     }
  25.     private int partition(int[] arr, int left, int right) {
  27.         // 设定基准值（pivot）
  28.         int pivot = left;
  29.         int index = pivot + 1;
  30.         for (int i = index; i <= right; i++) {
  32.             if (arr[i] < arr[pivot]) {
  34.                 swap(arr, i, index);
  35.                 index++;
  36.             }
  37.         }
  38.         swap(arr, pivot, index - 1);
  39.         return index - 1;
  40.     }
  42.     private void swap(int[] arr, int i, int j) {
  44.         int temp = arr[i];
  45.         arr[i] = arr[j];
  46.         arr[j] = temp;
  47.     }
  49. }

7.堆排序

图解

在这里插入图片描述

算法步骤

  • 创建一个堆 H[0……n-1]；
  • 把堆首（最大值）和堆尾互换；
  • 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  • 重复步骤 2，直到堆的尺寸为 1。

参考代码

  1. //Java 代码实现
  2.  public class HeapSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          int len = arr.length;
  13.         buildMaxHeap(arr, len);
  15.         for (int i = len - 1; i > 0; i--) {
  17.             swap(arr, 0, i);
  18.             len--;
  19.             heapify(arr, 0, len);
  20.         }
  21.         return arr;
  22.     }
  24.     private void buildMaxHeap(int[] arr, int len) {
  26.         for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
  28.             heapify(arr, i, len);
  29.         }
  30.     }
  32.     private void heapify(int[] arr, int i, int len) {
  34.         int left = 2 * i + 1;
  35.         int right = 2 * i + 2;
  36.         int largest = i;
  38.         if (left < len && arr[left] > arr[largest]) {
  40.             largest = left;
  41.         }
  43.        if (right < len && arr[right] > arr[largest]) {
  45.             largest = right;
  46.         }
  48.         if (largest != i) {
  50.             swap(arr, i, largest);
  51.             heapify(arr, largest, len);
  52.         }
  53.     }
  55.     private void swap(int[] arr, int i, int j) {
  57.         int temp = arr[i];
  58.         arr[i] = arr[j];
  59.         arr[j] = temp;
  60.     }
  62. }

8.计数排序

图解

在这里插入图片描述

算法步骤

  • 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
  • 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)
  • 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
  • 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

参考代码

  1. //Java 代码实现
  2.  public class CountingSort implements IArraySort {
  5.      @Override
  6.      public int[] sort(int[] sourceArray) throws Exception {
  8.          // 对 arr 进行拷贝，不改变参数内容
  9.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  11.          int maxValue = getMaxValue(arr);
  13.         return countingSort(arr, maxValue);
  14.     }
  16.     private int[] countingSort(int[] arr, int maxValue) {
  18.         int bucketLen = maxValue + 1;
  19.         int[] bucket = new int[bucketLen];
  21.         for (int value : arr) {
  23.             bucket[value]++;
  24.         }
  26.         int sortedIndex = 0;
  27.         for (int j = 0; j < bucketLen; j++) {
  29.             while (bucket[j] > 0) {
  31.                 arr[sortedIndex++] = j;
  32.                 bucket[j]--;
  33.             }
  34.         }
  35.         return arr;    
  36.         }
  38.     private int getMaxValue(int[] arr) {
  40.         int maxValue = arr[0];
  41.         for (int value : arr) {
  43.             if (maxValue < value) {
  45.                 maxValue = value;
  46.             }
  47.         }
  48.         return maxValue;
  49.     }
  51. }

9.桶排序

图解

在这里插入图片描述

算法步骤

  • 设置固定数量的空桶。
  • 把数据放到对应的桶中。
  • 对每个不为空的桶中数据进行排序。
  • 拼接不为空的桶中数据，得到结果

参考代码

  1. //Java 代码实现
  2.  public class BucketSort implements IArraySort {
  5.      private static final InsertSort insertSort = new InsertSort();
  7.      @Override
  8.      public int[] sort(int[] sourceArray) throws Exception {
  10.          // 对 arr 进行拷贝，不改变参数内容
  11.          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  13.         return bucketSort(arr, 5);
  14.     }
  16.     private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
  18.         if (arr.length == 0) {
  20.             return arr;
  21.         }
  23.         int minValue = arr[0];
  24.         int maxValue = arr[0];
  25.         for (int value : arr) {
  27.             if (value < minValue) {
  29.                 minValue = value;
  30.             } else if (value > maxValue) {
  32.                 maxValue = value;
  33.             }
  34.         }
  36.         int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
  37.         int[][] buckets = new int[bucketCount][0];
  39.         // 利用映射函数将数据分配到各个桶中
  40.         for (int i = 0; i < arr.length; i++) {
  42.             int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
  43.             buckets[index] = arrAppend(buckets[index], arr[i]);
  44.         }
  46.         int arrIndex = 0;
  47.         for (int[] bucket : buckets) {
  49.             if (bucket.length <= 0) {
  51.                 continue;
  52.             }
  53.             // 对每个桶进行排序，这里使用了插入排序
  54.             bucket = insertSort.sort(bucket);
  55.             for (int value : bucket) {
  57.                 arr[arrIndex++] = value;
  58.             }
  59.         }
  61.         return arr;
  62.     }
  64.     /**
  65.      * 自动扩容，并保存数据
  66.      *
  67.      * @param arr
  68.      * @param value
  69.      */
  70.     private int[] arrAppend(int[] arr, int value) {
  72.         arr = Arrays.copyOf(arr, arr.length + 1);
  73.         arr[arr.length - 1] = value;
  74.         return arr;
  75.     }
  77. }

10.基数排序

图解

在这里插入图片描述

算法步骤

  • 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
  • 从最低位开始，依次进行一次排序
  • 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

参考代码

  1. //Java 代码实现
  2. public class RadixSort implements IArraySort {
  4.    @Override
  5.    public int[] sort(int[] sourceArray) throws Exception {
  7.        // 对 arr 进行拷贝，不改变参数内容
  8.        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  9.        int maxDigit = getMaxDigit(arr);
  10.        return radixSort(arr, maxDigit);
  11.    }
  12.    /**
  13.     * 获取最高位数
  14.     */
  15.    private int getMaxDigit(int[] arr) {
  17.        int maxValue = getMaxValue(arr);
  18.        return getNumLenght(maxValue);
  19.    }
  20.    private int getMaxValue(int[] arr) {
  22.        int maxValue = arr[0];
  23.        for (int value : arr) {
  25.            if (maxValue < value) {
  27.                maxValue = value;
  28.            }
  29.        }
  30.        return maxValue;
  31.    }
  32.    protected int getNumLenght(long num) {
  34.        if (num == 0) {
  36.            return 1;
  37.        }
  38.        int lenght = 0;
  39.        for (long temp = num; temp != 0; temp /= 10) {
  41.            lenght++;
  42.        }
  43.        return lenght;
  44.    }
  45.    private int[] radixSort(int[] arr, int maxDigit) {
  47.        int mod = 10;
  48.        int dev = 1;
  49.        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  51.        // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
  52.                   int[][] counter = new int[mod * 2][0];
  53.            for (int j = 0; j < arr.length; j++) {
  55.                int bucket = ((arr[j] % mod) / dev) + mod;
  56.                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  57.            }
  58.            int pos = 0;
  59.            for (int[] bucket : counter) {
  61.                for (int value : bucket) {
  63.                    arr[pos++] = value;
  64.                }
  65.            }
  66.        }
  67.        return arr;
  68.    }
  69.    private int[] arrayAppend(int[] arr, int value) {
  71.        arr = Arrays.copyOf(arr, arr.length + 1);
  72.        arr[arr.length - 1] = value;
  73.        return arr;
  74.    }

发表评论

表情：
评论列表 （有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读