排序算法 - 图1

概述

排序方法 时间复杂度 空间复杂度 稳定性
选择排序 O(N^2) O(1) ×
冒泡排序 O(N^2) O(1) √
插入排序 O(N^2) O(1) √
归并排序 O(N^logN) O(N) √
随机快排 O(N^logN) O(logN) ×
堆排序 O(N^logN) O(1) ×
希尔排序 O(N^3/2) O(1) ×
基数排序 O(N) O(M) √
计数排序 O(N) O(N) √
  • 不基于比较的排序，对样本数据有严格要求，不易改写
  • 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
  • 基于比较的排序，时间复杂度的极限是O(N^logN)
  • 时间复杂度O(N^logN)、空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
  • 为了绝对的速度选快排，为了省空间选堆排，为了稳定选归并排序

常见的坑：
1、归并排序的额外空间复杂度可以变成O(1)，使用“归并排序内部缓存法”，但是将变得不再稳定。如果是这样，可直接使用堆排序。
2、“原地归并排序”不需要了解，会让时间复杂度变成O(N^2)。如果是这样，可直接使用冒泡或者插入排序。
3、快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多。如果是这样，可直接使用基数排序。
4、在整形数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对顺序不变，所有偶数之间原始相对顺序不变，时间复杂度做到O(N)，空间复杂度做到O(1)。该问题使用快速排序，但快速排序partition过程无法做到稳定性。除非整形数组中元素严格要求，才能做到。

选择排序

从左往右遍历数组，将i和i+1位置的数进行比较，每次遍历的范围-1，每次遍历可以确定最后一个位置上的数。

  1. public class SelectionSort implements InplaceSort {
  3.   @Override
  4.   public void sort(int[] values) {
  5.     SelectionSort.selectionSort(values);
  6.   }
  8.   public static void selectionSort(int[] array) {
  9.     if (array == null) return;
  10.     final int N = array.length;
  12.     for (int i = 0; i < N; i++) {
  13.       // Find the index beyond i with a lower value than i
  14.       int swapIndex = i;
  15.       for (int j = i + 1; j < N; j++) {
  16.         if (array[j] < array[swapIndex]) {
  17.           swapIndex = j;
  18.         }
  19.       }
  20.       swap(array, i, swapIndex);
  21.     }
  22.   }
  24.   private static void swap(int[] ar, int i, int j) {
  25.     int tmp = ar[i];
  26.     ar[i] = ar[j];
  27.     ar[j] = tmp;
  28.   }
  30.   public static void main(String[] args) {
  31.     InplaceSort sorter = new SelectionSort();
  32.     int[] array = {10, 4, 6, 8, 13, 2, 3};
  33.     sorter.sort(array);
  34.     // Prints:
  35.     // [2, 3, 4, 6, 8, 10, 13]
  36.     System.out.println(java.util.Arrays.toString(array));
  37.   }
  38. }

冒泡排序

从右往左遍历数组，在内循环中从左往右遍历，比较相邻的两个数并根据大小做交换。

  1. public class BubbleSort implements InplaceSort {
  3.   @Override
  4.   public void sort(int[] values) {
  5.     BubbleSort.bubbleSort(values);
  6.   }
  8.   // Sort the array using bubble sort. The idea behind
  9.   // bubble sort is to look for adjacent indexes which
  10.   // are out of place and interchange their elements
  11.   // until the entire array is sorted.
  12.   private static void bubbleSort(int[] ar) {
  13.     if (ar == null) {
  14.       return;
  15.     }
  17.     boolean sorted;
  18.     do {
  19.       sorted = true;
  20.       for (int i = 1; i < ar.length; i++) {
  21.         if (ar[i] < ar[i - 1]) {
  22.           swap(ar, i - 1, i);
  23.           sorted = false;
  24.         }
  25.       }
  26.     } while (!sorted);
  27.   }
  29.   private static void swap(int[] ar, int i, int j) {
  30.     int tmp = ar[i];
  31.     ar[i] = ar[j];
  32.     ar[j] = tmp;
  33.   }
  35.   public static void main(String[] args) {
  36.     int[] array = {10, 4, 6, 8, 13, 2, 3};
  37.     BubbleSort sorter = new BubbleSort();
  38.     sorter.sort(array);
  39.     // Prints:
  40.     // [2, 3, 4, 6, 8, 10, 13]
  41.     System.out.println(java.util.Arrays.toString(array));
  42.   }
  43. }

插入排序

从左往右遍历数组，根据要求进行比较，当发现需要交换位置时，依次往左比较交换直到不需要交换，再向右继续比较。保证0~i位置左边的数有序。

  1. public class InsertionSort implements InplaceSort {
  3.   @Override
  4.   public void sort(int[] values) {
  5.     InsertionSort.insertionSort(values);
  6.   }
  8.   // Sort the given array using insertion sort. The idea behind
  9.   // insertion sort is that at the array is already sorted from
  10.   // [0, i] and you want to add the element at position i+1, so
  11.   // you 'insert' it at the appropriate location.
  12.   private static void insertionSort(int[] ar) {
  13.     if (ar == null) {
  14.       return;
  15.     }
  17.     for (int i = 1; i < ar.length; i++) {
  18.       for (int j = i; j > 0 && ar[j] < ar[j - 1]; j--) {
  19.         swap(ar, j - 1, j);
  20.       }
  21.     }
  22.   }
  24.   private static void swap(int[] ar, int i, int j) {
  25.     int tmp = ar[i];
  26.     ar[i] = ar[j];
  27.     ar[j] = tmp;
  28.   }
  30.   public static void main(String[] args) {
  31.     InplaceSort sorter = new InsertionSort();
  32.     int[] array = {10, 4, 6, 8, 13, 2, 3};
  33.     sorter.sort(array);
  34.     // Prints:
  35.     // [2, 3, 4, 6, 8, 10, 13]
  36.     System.out.println(java.util.Arrays.toString(array));
  37.   }
  38. }

归并排序

整体就是一个递归，左边排好序、右边排好序、让整体有序。

  1. public class MergeSort implements InplaceSort {
  3.   @Override
  4.   public void sort(int[] values) {
  5.     int[] sortedValues = MergeSort.mergesort(values);
  6.     for (int i = 0; i < values.length; i++) {
  7.       values[i] = sortedValues[i];
  8.     }
  9.   }
  11.   public static int[] mergesort(int[] ar) {
  12.     // Base case is when a single element (which is already sorted)
  13.     int n = ar.length;
  14.     if (n <= 1) return ar;
  16.     // Split array into two parts and recursively sort them
  17.     int[] left = mergesort(Arrays.copyOfRange(ar, 0, n / 2));
  18.     int[] right = mergesort(Arrays.copyOfRange(ar, n / 2, n));
  20.     // Combine the two arrays into one larger array
  21.     return merge(left, right);
  22.   }
  24.   // Merge two sorted arrays into a larger sorted array
  25.   private static int[] merge(int[] ar1, int[] ar2) {
  26.     int n1 = ar1.length, n2 = ar2.length;
  27.     int n = n1 + n2, i1 = 0, i2 = 0;
  28.     int[] ar = new int[n];
  30.     for (int i = 0; i < n; i++) {
  31.       if (i1 == n1) {
  32.         ar[i] = ar2[i2++];
  33.       } else if (i2 == n2) {
  34.         ar[i] = ar1[i1++];
  35.       } else {
  36.         if (ar1[i1] < ar2[i2]) {
  37.           ar[i] = ar1[i1++];
  38.         } else {
  39.           ar[i] = ar2[i2++];
  40.         }
  41.       }
  42.     }
  43.     return ar;
  44.   }
  46.   public static void main(String[] args) {
  47.     int[] array = {10, 4, 6, 4, 8, -13, 2, 3};
  48.     array = MergeSort.mergesort(array);
  49.     // Prints:
  50.     // [-13, 2, 3, 4, 4, 6, 8, 10]
  51.     System.out.println(java.util.Arrays.toString(array));
  52.   }
  53. }

快速排序

public class QuickSelect {

  public Integer quickSelect(int[] ar, int k) {
    if (ar == null) return null;
    if (k > ar.length) return null;
    if (k < 1) return null;
    return quickSelect(ar, k, 0, ar.length - 1);
  }

  // Sort interval [lo, hi] inplace recursively, returns value when splitPoint == k - 1
  private static Integer quickSelect(int[] ar, int k, int lo, int hi) {
    int index = k - 1;
    if (lo < hi) {
      int splitPoint = partition(ar, lo, hi);
      if (splitPoint == index) {
        return ar[splitPoint];
      } else if (splitPoint > index) {
        return quickSelect(ar, k, lo, splitPoint);
      }
      return quickSelect(ar, k, splitPoint + 1, hi);
    }
    return ar[lo];
  }

  // Performs Hoare partition algorithm for quick select, taken from QuickSelect implementation
  private static int partition(int[] ar, int lo, int hi) {
    int pivot = ar[lo];
    int i = lo - 1, j = hi + 1;
    while (true) {
      do {
        i++;
      } while (ar[i] < pivot);
      do {
        j--;
      } while (ar[j] > pivot);
      if (i < j) swap(ar, i, j);
      else return j;
    }
  }

  // Swap two elements
  private static void swap(int[] ar, int i, int j) {
    int tmp = ar[i];
    ar[i] = ar[j];
    ar[j] = tmp;
  }

  public static void main(String[] args) {
    QuickSelect quickSelect = new QuickSelect();
    int[] array = {-10, 4, 6, 4, 8, -13, 1, 3};
    int kthLargestElement = quickSelect.quickSelect(array, 3);
    // Prints: 1
    System.out.println(kthLargestElement);
  }
}

堆排序

public class Heapsort implements InplaceSort {

  @Override
  public void sort(int[] values) {
    Heapsort.heapsort(values);
  }

  private static void heapsort(int[] ar) {
    if (ar == null) return;
    int n = ar.length;

    // Heapify, converts array into binary heap O(n), see:
    // http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
    for (int i = Math.max(0, (n / 2) - 1); i >= 0; i--) {
      sink(ar, n, i);
    }

    // Sorting bit
    for (int i = n - 1; i >= 0; i--) {
      swap(ar, 0, i);
      sink(ar, i, 0);
    }
  }

  private static void sink(int[] ar, int n, int i) {
    while (true) {
      int left = 2 * i + 1; // Left  node
      int right = 2 * i + 2; // Right node
      int largest = i;

      // Right child is larger than parent
      if (right < n && ar[right] > ar[largest]) largest = right;

      // Left child is larger than parent
      if (left < n && ar[left] > ar[largest]) largest = left;

      // Move down the tree following the largest node
      if (largest != i) {
        swap(ar, largest, i);
        i = largest;
      } else break;
    }
  }

  private static void swap(int[] ar, int i, int j) {
    int tmp = ar[i];
    ar[i] = ar[j];
    ar[j] = tmp;
  }

  /* TESTING */

  public static void main(String[] args) {
    Heapsort sorter = new Heapsort();
    int[] array = {10, 4, 6, 4, 8, -13, 2, 3};
    sorter.sort(array);
    // Prints:
    // [-13, 2, 3, 4, 4, 6, 8, 10]
    System.out.println(java.util.Arrays.toString(array));
  }
}

希尔排序

public class ShellSort {
    public static void main(String []args){
        int []arr ={1,4,2,7,9,8,3,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        int []arr1 ={1,4,2,7,9,8,3,6};
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static void sort(int []arr){
        //增量gap，并逐步缩小增量
       for(int gap=arr.length/2;gap>0;gap/=2){
           //从第gap个元素，逐个对其所在组进行直接插入排序操作
           for(int i=gap;i<arr.length;i++){
               int j = i;
               while(j-gap>=0 && arr[j]<arr[j-gap]){
                   //插入排序采用交换法
                   swap(arr,j,j-gap);
                   j-=gap;
               }
           }
       }
    }

    /**
     * 希尔排序 针对有序序列在插入时采用移动法。
     * @param arr
     */
    public static void sort1(int []arr){
        //增量gap，并逐步缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0 && temp<arr[j-gap]){
                        //移动法
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    /**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }
}

桶排序

public class BucketSort implements InplaceSort {

  @Override
  public void sort(int[] values) {
    int minValue = Integer.MAX_VALUE;
    int maxValue = Integer.MIN_VALUE;
    for (int i = 0; i < values.length; i++) {
      if (values[i] < minValue) minValue = values[i];
      if (values[i] > maxValue) maxValue = values[i];
    }
    BucketSort.bucketSort(values, minValue, maxValue);
  }

  // Performs a bucket sort of an array in which all the elements are
  // bounded in the range [minValue, maxValue]. For bucket sort to give linear
  // performance the elements need to be uniformly distributed
  private static void bucketSort(int[] ar, int minValue, int maxValue) {
    if (ar == null || ar.length == 0 || minValue == maxValue) return;

    // N is number elements and M is the range of values
    final int N = ar.length, M = maxValue - minValue + 1, numBuckets = M / N + 1;
    List<List<Integer>> buckets = new ArrayList<>(numBuckets);
    for (int i = 0; i < numBuckets; i++) buckets.add(new ArrayList<>());

    // Place each element in a bucket
    for (int i = 0; i < N; i++) {
      int bi = (ar[i] - minValue) / M;
      List<Integer> bucket = buckets.get(bi);
      bucket.add(ar[i]);
    }

    // Sort buckets and stitch together answer
    for (int bi = 0, j = 0; bi < numBuckets; bi++) {
      List<Integer> bucket = buckets.get(bi);
      if (bucket != null) {
        Collections.sort(bucket);
        for (int k = 0; k < bucket.size(); k++) {
          ar[j++] = bucket.get(k);
        }
      }
    }
  }

  public static void main(String[] args) {
    BucketSort sorter = new BucketSort();

    int[] array = {10, 4, 6, 8, 13, 2, 3};
    sorter.sort(array);
    // Prints:
    // [2, 3, 4, 6, 8, 10, 13]
    System.out.println(java.util.Arrays.toString(array));

    array = new int[] {10, 10, 10, 10, 10};
    sorter.sort(array);
    // Prints:
    // [10, 10, 10, 10, 10]
    System.out.println(java.util.Arrays.toString(array));
  }
}

基数排序

public class RadixSort implements InplaceSort {

  @Override
  public void sort(int[] values) {
    RadixSort.radixSort(values);
  }

  static int getMax(int[] array) {
    int max = array[0];
    for (int i = 0; i < array.length; i++) {
      if (array[i] > max) {
        max = array[i];
      }
    }
    return max;
  }

  static int calculateNumberOfDigits(int number) {
    return (int) Math.log10(number) + 1;
  }

  // Requires all numbers to be greater than or equal to 1
  public static void radixSort(int[] numbers) {
    if (numbers == null || numbers.length <= 1) {
      return;
    }
    int maximum = getMax(numbers);
    int numberOfDigits = calculateNumberOfDigits(maximum);
    int placeValue = 1;
    while (numberOfDigits-- > 0) {
      countSort(numbers, placeValue);
      placeValue *= 10;
    }
  }

  private static void countSort(int[] numbers, int placeValue) {
    int range = 10;

    int[] frequency = new int[range];
    int[] sortedValues = new int[numbers.length];

    for (int i = 0; i < numbers.length; i++) {
      int digit = (numbers[i] / placeValue) % range;
      frequency[digit]++;
    }

    for (int i = 1; i < range; i++) {
      frequency[i] += frequency[i - 1];
    }

    for (int i = numbers.length - 1; i >= 0; i--) {
      int digit = (numbers[i] / placeValue) % range;
      sortedValues[frequency[digit] - 1] = numbers[i];
      frequency[digit]--;
    }

    System.arraycopy(sortedValues, 0, numbers, 0, numbers.length);
  }

  public static void main(String[] args) {
    InplaceSort sorter = new RadixSort();
    int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7, 890, 1, 587};
    sorter.sort(numbers);
    // Prints:
    // [1, 7, 37, 68, 123, 134, 221, 387, 468, 587, 769, 890]
    System.out.println(java.util.Arrays.toString(numbers));
  }
}

计数排序

public class CountingSort implements InplaceSort {

  @Override
  public void sort(int[] values) {
    int minValue = Integer.MAX_VALUE;
    int maxValue = Integer.MIN_VALUE;
    for (int i = 0; i < values.length; i++) {
      if (values[i] < minValue) minValue = values[i];
      if (values[i] > maxValue) maxValue = values[i];
    }
    CountingSort.countingSort(values, minValue, maxValue);
  }

  // Sorts values in the range of [minVal, maxVal] in O(n+maxVal-maxVal)
  private static void countingSort(int[] ar, int minVal, int maxVal) {
    int sz = maxVal - minVal + 1;
    int[] b = new int[sz];
    for (int i = 0; i < ar.length; i++) b[ar[i] - minVal]++;
    for (int i = 0, k = 0; i < sz; i++) {
      while (b[i]-- > 0) ar[k++] = i + minVal;
    }
  }

  public static void main(String[] args) {
    CountingSort sorter = new CountingSort();
    int[] nums = {+4, -10, +0, +6, +1, -5, -5, +1, +1, -2, 0, +6, +8, -7, +10};
    sorter.sort(nums);

    // Prints:
    // [-10, -7, -5, -5, -2, 0, 0, 1, 1, 1, 4, 6, 6, 8, 10]
    System.out.println(java.util.Arrays.toString(nums));
  }
}