1.快排

时间复杂度退化情况

  • 基本有序的序列对于快速排序是最坏的场景，也是上文中面试官提到的其中一个优化点。因为每次只分割出一个基准点，需要N次分割，时间复杂度为O（N^2）

    1.  public static void shuffle(int[] nums) {
    2.       int n = nums.length;
    3.       Random rand = new Random();
    4.       for (int i = 0 ; i < n; i++) {
    5.           // 从 i 到最后随机选一个元素
    6.           int r = i + rand.nextInt(n - i);
    7.           swap(nums, i, r);
    8.   }
    9.   public static void quickSort(int[] list, int startIndex, int endIndex) {
    10.       if (startIndex >= endIndex) return;
    12.       int base = partition(list, startIndex, endIndex);
    13.       quickSort(list, startIndex, base - 1);
    14.       quickSort(list, base + 1, endIndex); 
    15.   }
    17.   public static int partition(int[] list, int startIndex, int endIndex) {
    18.       int pivot = list[startIndex];
    19.       int left = startIndex;
    20.       int right = endIndex;
    21.       while (left < right) {
    22.           //            保证右指针先向左移动，使左右指针重合时，一定指向比基准数小的数
    23.           while (left < right && list[right] > pivot) {
    24.               right--;
    25.           }
    26.           while (left < right && list[left] <= pivot) {
    27.               left++;
    28.           }
    29.           if (left < right) {
    30.               swap(list, left, right);
    31.           }
    32.       }
    33.       swap(list, startIndex, left);
    34.       return left;
    35.   }
    37.   private static void swap(int[] list, int a, int b) {
    38.       int temp;
    39.       temp = list[a];
    40.       list[a] = list[b];
    41.       list[b] = temp;
    42.   }

    2.归并

需额外数组

  1.     public void mergeSort(int array[], int first, int last, int temp[]) {
  2.         if (first < last) {
  3.             int mid = (first + last) / 2;
  4.             mergeSort(array, first, mid, temp); // 递归归并左边元素
  5.             mergeSort(array, mid + 1, last, temp); // 递归归并右边元素
  6.             merge(array, first, mid, last, temp); // 再将二个有序数列合并
  7.         }
  8.     }
  10.     private void merge(int list[], int first, int mid, int last, int temp[]) {
  11.         int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点
  12.         int k = 0; // k用于指向temp数组当前放到哪个位置
  14.         while (i <= mid && j <= last) { // 将两个有序序列循环比较, 填入数组temp
  15.             if (list[i] <= list[j])
  16.                 temp[k++] = list[i++];
  17.             else
  18.                 temp[k++] = list[j++];
  19.         }
  20.         while (i <= mid) { // 如果比较完毕, 第一组还有数剩下, 则全部填入temp
  21.             temp[k++] = list[i++];
  22.         }
  23.         while (j <= last) {// 如果比较完毕, 第二组还有数剩下, 则全部填入temp
  24.             temp[k++] = list[j++];
  25.         }
  26.         for (i = 0; i < k; i++) {// 将排好序的数填回到array数组的对应位置
  27.             list[first + i] = temp[i];
  28.         }
  29.     }

3.堆排

上浮 下沉

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int cap) {
        pq = (Key[]) new Comparable[cap + 1];
    }

    public Key max() {
        return pq[1];
    }

    public void insert(Key e) {
        N++;
        // 先把新元素加到最后
        pq[N] = e;
        // 然后让它上浮到正确的位置
        swim(N);
    }

    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];
        // 把这个最大元素换到最后，删除之
        exchange(1, N);
        pq[N] = null;
        N--;
        // 让 pq[1] 下沉到正确位置
        sink(1);
        return max;

    }

    private void swim(int k) {
        while (k > 1 && less(parent(k), k)) {
            exchange(parent(k), k);
            k = parent(k);
        }
    }

    private void sink(int k) {
        while (left(k) <= N) {
            int older = left(k);
            if (right(k) <= N && less(older, right(k))) {
                older = right(k);
            }

            if(less(older,k)) break;
            exchange(k,older);
            k = older;
        }
    }

    private void exchange(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    // 父节点的索引
    int parent(int root) {
        return root / 2;
    }

    // 左孩子的索引
    int left(int root) {
        return root * 2;
    }

    // 右孩子的索引
    int right(int root) {
        return root * 2 + 1;
    }

}