0%

数据结构与算法之美(四):十大经典排序算法

1. 算法分类

2. 算法总结

排序算法 时间复杂度(最好) 时间复杂度(最坏) 时间复杂度(平均) 空间复杂度 稳定性
冒泡排序 O(n) O(n^2) O(n^2) O(1) ✔️
选择排序 O(n^2) O(n^2) O(n^2) O(1)
插入排序 O(n) O(n^2) O(n^2) O(1) ✔️
希尔排序 O(nlogn) O(nlog^2 n) O(nlog^2 n) O(1)
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) ✔️
快速排序 O(nlogn) O(n^2) O(nlogn) O(logn)
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1)
桶排序 O(n) O(n^2) O(n) O(n*k) ✔️
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) ✔️
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) ✔️

3. 算法实现

  • 冒泡排序

    • 动图

      冒泡排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      public static void bubbleSort(int [] a) {
      if(a.length <= 1) {
      return;
      }
      for(int i = 0; i < a.length; i++) {
      boolean flag = true; // 提前结束循环标志位
      for(int j = 0; j < a.length-1-i; j++) {
      if(a[j] > a[j+1]) {
      int temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp;
      flag = false; // 此次冒泡有数据交换
      }
      }
      if(flag) {
      break;
      }
      }
      }
  • 选择排序

    • 动图

      选择排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      public static void selectionSort(int [] a) {
      if(a.length <= 1) {
      return;
      }
      for(int i=0; i<n-1; i++) {
      // 查找最小值
      int minIndex = i;
      for(int j = i+1; j < n; j++) {
      if(a[j] < a[minIndex]) {
      minIndex = j;
      }
      }

      // 交换
      if(minIndex != i) {
      int temp = a[i];
      a[i] = a[minIndex];
      a[minIndex] = temp;
      }
      }
      }
  • 插入排序

    • 动图

      插入排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      public static void insertionSort(int [] a) {
      if(a.length <= 1) {
      return;
      }

      for (int i = 1; i < arr.length; i++) {
      int value = a[i];
      int j = i - 1;
      // 查找要插入的位置并移动数据
      for (; j >= 0; j--) {
      if (a[j] > value) {
      a[j+1] = a[j];
      } else {
      break;
      }
      }

      if(j+1 != i) {
      a[j+1] = value;
      }
      }
  • 希尔排序

    • 动图

      希尔排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      public static void shellSort(int [] arr) {
      if(arr.length <= 1) {
      return;
      }

      int gap = 1;
      while (gap < arr.length) {
      gap = gap * 3 + 1;
      }

      while (gap > 0) {
      for (int i = gap; i < arr.length; i++) {
      int tmp = arr[i];
      int j = i - gap;
      while (j >= 0 && arr[j] > tmp) {
      arr[j + gap] = arr[j];
      j -= gap;
      }
      arr[j + gap] = tmp;
      }
      gap = (int) Math.floor(gap / 3);
      }
      }
  • 归并排序

    • 动图

      归并排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      // 归并排序算法, a是数组,n表示数组大小
      public static void mergeSort(int[] a, int n) {
      mergeSortInternally(a, 0, n-1);
      }

      // 递归调用函数
      private static void mergeSortInternally(int[] a, int p, int r) {
      // 递归终止条件
      if (p >= r) return;

      // 取p到r之间的中间位置q,防止(p+r)的和超过int类型最大值
      int q = p + (r - p)/2;
      // 分治递归
      mergeSortInternally(a, p, q);
      mergeSortInternally(a, q+1, r);

      // 将A[p...q]和A[q+1...r]合并为A[p...r]
      merge(a, p, q, r);
      }

      private static void merge(int[] a, int p, int q, int r) {
      int i = p;
      int j = q+1;
      int k = 0; // 初始化变量i, j, k
      int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
      while (i<=q && j<=r) {
      if (a[i] <= a[j]) {
      tmp[k++] = a[i++]; // i++等于i:=i+1
      } else {
      tmp[k++] = a[j++];
      }
      }

      // 判断哪个子数组中有剩余的数据
      int start = i;
      int end = q;
      if (j <= r) {
      start = j;
      end = r;
      }

      // 将剩余的数据拷贝到临时数组tmp
      while (start <= end) {
      tmp[k++] = a[start++];
      }

      // 将tmp中的数组拷贝回a[p...r]
      for (i = 0; i <= r-p; ++i) {
      a[p+i] = tmp[i];
      }
      }
  • 快速排序

    • 动图

      快速排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      // 快速排序,a是数组,n表示数组的大小
      public static void quickSort(int[] a, int n) {
      quickSortInternally(a, 0, n-1);
      }

      // 快速排序递归函数,p,r为下标
      private static void quickSortInternally(int[] a, int p, int r) {
      if (p >= r) return;

      int q = partition(a, p, r); // 获取分区点
      quickSortInternally(a, p, q-1);
      quickSortInternally(a, q+1, r);
      }

      private static int partition(int[] a, int p, int r) {
      int pivot = a[r];
      int i = p;
      for(int j = p; j < r; ++j) {
      if (a[j] < pivot) {
      if (i == j) {
      ++i;
      } else {
      int tmp = a[i];
      a[i++] = a[j];
      a[j] = tmp;
      }
      }
      }

      int tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;

      System.out.println("i=" + i);
      return i;
      }
  • 堆排序

    • 动图

      堆排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      public class HeapSort implements IArraySort {

      @Override
      public int[] sort(int[] sourceArray) throws Exception {
      // 对 arr 进行拷贝,不改变参数内容
      int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

      int len = arr.length;

      buildMaxHeap(arr, len);

      for (int i = len - 1; i > 0; i--) {
      swap(arr, 0, i);
      len--;
      heapify(arr, 0, len);
      }
      return arr;
      }

      private void buildMaxHeap(int[] arr, int len) {
      for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
      heapify(arr, i, len);
      }
      }

      private void heapify(int[] arr, int i, int len) {
      int left = 2 * i + 1;
      int right = 2 * i + 2;
      int largest = i;

      if (left < len && arr[left] > arr[largest]) {
      largest = left;
      }

      if (right < len && arr[right] > arr[largest]) {
      largest = right;
      }

      if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, largest, len);
      }
      }

      private void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      }
      }
  • 桶排序

    • 动图

      桶排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
       public class BucketSort implements IArraySort {

      private static final InsertSort insertSort = new InsertSort();

      @Override
      public int[] sort(int[] sourceArray) throws Exception {
      // 对 arr 进行拷贝,不改变参数内容
      int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

      return bucketSort(arr, 5);
      }

      private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
      if (arr.length == 0) {
      return arr;
      }

      int minValue = arr[0];
      int maxValue = arr[0];
      for (int value : arr) {
      if (value < minValue) {
      minValue = value;
      } else if (value > maxValue) {
      maxValue = value;
      }
      }

      int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
      int[][] buckets = new int[bucketCount][0];

      // 利用映射函数将数据分配到各个桶中
      for (int i = 0; i < arr.length; i++) {
      int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
      buckets[index] = arrAppend(buckets[index], arr[i]);
      }

      int arrIndex = 0;
      for (int[] bucket : buckets) {
      if (bucket.length <= 0) {
      continue;
      }
      // 对每个桶进行排序,这里使用了插入排序
      bucket = insertSort.sort(bucket);
      for (int value : bucket) {
      arr[arrIndex++] = value;
      }
      }

      return arr;
      }

      // 自动扩容,并保存数据
      private int[] arrAppend(int[] arr, int value) {
      arr = Arrays.copyOf(arr, arr.length + 1);
      arr[arr.length - 1] = value;
      return arr;
      }
      }
  • 计数排序

    • 动图

      计数排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      public class CountingSort {

      // 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
      public static void countingSort(int[] a, int n) {
      if (n <= 1) return;

      // 查找数组中数据的范围
      int max = a[0];
      for (int i = 1; i < n; ++i) {
      if (max < a[i]) {
      max = a[i];
      }
      }

      // 申请一个计数数组c,下标大小[0,max]
      int[] c = new int[max + 1];
      for (int i = 0; i < max + 1; ++i) {
      c[i] = 0;
      }

      // 计算每个元素的个数,放入c中
      for (int i = 0; i < n; ++i) {
      c[a[i]]++;
      }

      // 依次累加
      for (int i = 1; i < max + 1; ++i) {
      c[i] = c[i-1] + c[i];
      }

      // 临时数组r,存储排序之后的结果
      int[] r = new int[n];
      // 计算排序的关键步骤了,有点难理解
      for (int i = n - 1; i >= 0; --i) {
      int index = c[a[i]]-1;
      r[index] = a[i];
      c[a[i]]--;
      }

      // 将结果拷贝会a数组
      for (int i = 0; i < n; ++i) {
      a[i] = r[i];
      }
      }
      }
  • 基数排序

    • 动图

      基数排序

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
       public class RadixSort implements IArraySort {

      @Override
      public int[] sort(int[] sourceArray) throws Exception {
      // 对 arr 进行拷贝,不改变参数内容
      int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

      int maxDigit = getMaxDigit(arr);
      return radixSort(arr, maxDigit);
      }

      // 获取最高位数
      private int getMaxDigit(int[] arr) {
      int maxValue = getMaxValue(arr);
      return getNumLenght(maxValue);
      }

      private int getMaxValue(int[] arr) {
      int maxValue = arr[0];
      for (int value : arr) {
      if (maxValue < value) {
      maxValue = value;
      }
      }
      return maxValue;
      }

      protected int getNumLenght(long num) {
      if (num == 0) {
      return 1;
      }
      int lenght = 0;
      for (long temp = num; temp != 0; temp /= 10) {
      lenght++;
      }
      return lenght;
      }

      private int[] radixSort(int[] arr, int maxDigit) {
      int mod = 10;
      int dev = 1;

      for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
      // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
      int[][] counter = new int[mod * 2][0];

      for (int j = 0; j < arr.length; j++) {
      int bucket = ((arr[j] % mod) / dev) + mod;
      counter[bucket] = arrayAppend(counter[bucket], arr[j]);
      }

      int pos = 0;
      for (int[] bucket : counter) {
      for (int value : bucket) {
      arr[pos++] = value;
      }
      }
      }

      return arr;
      }
      private int[] arrayAppend(int[] arr, int value) {
      arr = Arrays.copyOf(arr, arr.length + 1);
      arr[arr.length - 1] = value;
      return arr;
      }
      }
-------------------- 本文结束感谢您的阅读 --------------------