排序算法

排序算法对比

算法	时间复杂度	是稳定排序？	是原地排序？
冒泡排序	o(n^2)	✅	✅
插入排序	o(n^2)	✅	✅
选择排序	o(n^2)	❌	✅
快速排序	o(nlog(n))	❌	✅
归并排序	o(nlog(n))	✅	❌
桶排序	o(n+k) k是数据范围	✅	❌
计数排序	o(n)	✅	❌
基数排序	o(dn) d是维度	✅	❌
堆排序	O(nlogn)	❌	✅

jdk排序算法

插入排序

class InsertionSort implements SortAlgorithm {

    /**
     * This method implements the Generic Insertion Sort
     * Sorts the array in increasing order
     *
     * @param array The array to be sorted
     **/

    //算法导论
    public int[] sort(int[] array) {
        for (int j = 1; j < array.length; j++) {

            // Picking up the key(Card)
            int key = array[j];
            int i = j - 1;

            while (i >= 0 && key < array[i]) {
                array[i + 1] = array[i];
                i--;
            }
            // Placing the key (Card) at its correct position in the sorted subarray
            array[i + 1] = key;
        }
        return array;
    }

    // Driver Program
    public static void main(String[] args) {
        // Integer Input
        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};

        InsertionSort sort = new InsertionSort();

        sort.sort(integers);

        // Output => 1 4 6 9 12 23 54 78 231
        Arrays.stream(a).forEach(System.out::println);
    }
}

快速排序

public class QuickSort {

  public int[] sort(int[] array) {
    doSort(array, 0, array.length - 1);
    return array;
  }

  private void doSort(int[] array, int left, int right) {
    if (left >= right) {
      return;
    }
    int pivot = partition(array, left, right);
    doSort(array, left, pivot - 1);
    doSort(array, pivot, right);
  }

  //算法导论
  private int partition(int[] array, int left, int right) {
    int key = array[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++) {
      if (array[j] <= key) {
        i++;
        swap(array, i, j);
      }
    }
    swap(array, i + 1, right);
    return i + 1;
  }

  static boolean swap(int[] array, int idx, int idy) {
    int swap = array[idx];
    array[idx] = array[idy];
    array[idy] = swap;
    return true;
  }

  public static void main(String[] args) {
    int[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

    QuickSort quickSort = new QuickSort();
    quickSort.sort(array);

    Arrays.stream(array).forEach(System.out::println);

  }
}

归并排序

public class MergeSort {

  public void doSort(int[] arr, int left, int right) {
    //递归终止条件
    if (left >= right) {
      return;
    }
    int mid = (left + right) / 2;
    //分治递归
    doSort(arr, left, mid);
    doSort(arr, mid + 1, right);
    //合并
    merge(arr, left, mid, right);
  }

  //算法导论
  private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] leftArr = new int[n1 + 1];
    int[] rightArr = new int[n2 + 1];
    for (int i = 0; i < n1; i++) {
      leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
      rightArr[j] = arr[mid + j + 1];
    }
    leftArr[n1] = Integer.MAX_VALUE;
    rightArr[n2] = Integer.MAX_VALUE;

    int i = 0, j = 0;
    for (int k = left; k <= right; k++) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k] = leftArr[i];
        i++;
      } else {
        arr[k] = rightArr[j];
        j++;
      }
    }
  }

  public static void main(String[] args) {
    int[] arr = {4, 23, 6, 78, 1, 54, 231, 9, 12};
    MergeSort mergeSort = new MergeSort();
    mergeSort.sort(arr);
    Arrays.stream(arr).forEach(System.out::println);
  }

  public int[] sort(int[] unsorted) {
    doSort(unsorted, 0, unsorted.length - 1);
    return unsorted;
  }
}

堆排序

public class HeapSort {


  public static void main(String[] args) {
    int[] heap = {0, 4, 23, 6, 78, 1, 54, 231, 9, 12};
    sort(heap, 9);
    for (int i = heap.length - 1; i >= 1; i--) {
      System.out.println(heap[i]);
    }
  }

  private static void buildHeap(int[] a, int n) {
    for (int i = n / 2; i >= 1; i--) {
      heapify(a, n, i);
    }
  }

  private static void heapify(int[] a, int n, int i) {
    while (true) {
      int maxPos = i;
      if (i * 2 <= n && a[i] < a[i * 2]) {
        maxPos = i * 2;
      }
      if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
        maxPos = i * 2 + 1;
      }
      if (maxPos == i) {
        break;
      }
      swap(a, i, maxPos);
      i = maxPos;
    }
  }

  // n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
  public static void sort(int[] a, int n) {
    //建堆
    buildHeap(a, n);
    int k = n;
    //排序
    while (k > 1) {
      swap(a, 1, k);
      --k;
      heapify(a, k, 1);
    }
  }

  static boolean swap(int[] array, int idx, int idy) {
    int swap = array[idx];
    array[idx] = array[idy];
    array[idy] = swap;
    return true;
  }
}