排序算法

前言

稳定性：如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的

不稳定算法：如选择排序，希尔排序，快速排序和堆排序

算法	是否稳定	是否为原地排序	时间复杂度	空间复杂度	备注
选择排序	否	是	N2	1	取决于元素的排列情况
插入排序	是	是	N~N2	1	取决于元素的排列情况
希尔排序	否	是	NlogN? N1.2?	1	取决于元素的排列情况
快速排序	否	是	NlogN	lgN	运行效率由概率提供保证
三向快速排序	否	是	N~NlogN	lgN	运行效率由概率提供保证，同时也取决于输入元素的分布情况
归并排序	是	否	NlogN	N
堆排序	否	是	NlogN	１

选择排序

运行时间和输入无关 对于长度为n的数组，选择排序需要大约n2/2次比较和n次交换 稳定 时间复杂度O(n2)

for(int i = 0; i < n; i++) {
  int minIdx = i;
  for(int j = i+1; j < n; j++) {
    if(nums[j] < nums[minIdx]) {
      minIdx = j;
    }
  }
  swap(nums,i,minIdx);
}

插入排序

运行时间与输入状态有关 对于长度为n的数组，平均情况下需要n2/4次比较，n2/4次交换 最坏情况下需要n2/2次比较，n2/2次交换 最好情况下需要n-1次比较和0次交换

对于部分有序的数组十分高效

for(int i = 1; i < n; i++) {
  for(int j = i; j > 0 && nums[j] < nums[j-1]; j--) {
      swap(nums,j,j-1);
  }
}

希尔排序

int h = 1;
while(h < n/3) h = h*3 + 1;
while(h >= 1) {
  for(int i = h; i < n; i++) {
    for(int j = i; j >= h && nums[j] < nums[j-h]; j -= h) {
      swap(nums,j,j-h);
    }
  }
  h = h/3;
}

归并排序

自顶向下的归并排序

public class MergeSort {
  private static int[] aux;
  public static void sort(int[] nums) {
    aux = new int[nums.length];
    sort(nums,0,nums.length-1);
  }
  private static void sort(int[] nums,int lo,int hi) {
    if(lo >= hi) return;
    int mid = (lo + hi)/2;
    sort(nums,lo,mid);
    sort(nums,mid+1,hi);
    merge(nums,lo,mid,hi);
  }
  private static void merge(int[] nums,int lo,int mid,int hi) {
    for(int i = lo; i <= hi; i++) {
      aux[i] = nums[i];
    }
    int left = lo;
    int right = mid+1;
    for(int i = lo; i <= hi; i++) {
      if(left > mid) nums[i] = aux[right++];
      else if(right > hi) nums[i] = aux[left++];
      else if(aux[left] <= aux[right]) nums[i] = aux[left++];
      else nums[i] = aux[right++];
    }
  }
}

自底向上的归并排序

public class MergeSort {
  private int[] aux;
  public static void sort(int[] nums) {
    int len = nums.length;
    aux = new int[len];
    for(int sz = 1; sz < len; sz += sz) {
      for(int lo = 0; lo < len - sz; lo += sz + sz) {
        merge(nums,lo,lo+sz-1,Math.min(lo+sz+sz-1,len-1));
      }
    }
  }
}

快速排序

public class QuickSort {
  public static void sort(int[] nums) {
    sort(nums,0,a.length-1);
  }
  private static void sort(int[] nums,int lo,int hi) {
    if(lo >= hi) return;
    int j = partition(nums,lo,hi);
    sort(nums,lo,j-1);
    sort(nums,j+1,hi);
  }
  private static int partition(int[] nums,int lo,int hi) {
    int i = lo,j = hi+1;
    int key = a[lo];
    while(true){
      while(a[++i] < key && i < hi);
      while(a[--j] > key && j > lo);
      if(i >= j) break;
      exch(nums,i,j);
    }
    exch(nums,lo,j);
    return j;
  }
}

三向切分的快速排序

对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高得多

private static void sort(int[] nums,int lo,int hi) {
  if(hi <= lo) return;
  int lt = lo,i = lo + 1,gt = hi;
  int key = nums[lo];
  while(i <= gt) {
    if(nums[i] < key) exch(nums,lt++,i++);
    else if(nums[i] > key) exch(nums,i,gt--);
    else i++;
  }
  sort(nums,lo,lt-1);
  sort(nums,gt+1,hi);
}

堆排序

public class DumpSort {

  // 上浮
  private void swim(int[] nums, int k) {
    while(k > 1 && nums[k/2] < nums[k]) {
      exch(nums, k, k/2);
      k /= 2;
    }
  }
  // 下沉
  private void sink(int[] nums, int k, int N) {
    while(2 * k <= N) {
      int j = 2 * k;
      if(j < N && nums[j] < nums[j+1]) j++;
      if(nums[k] >= nums[j]) break;
      exch(nums, k, j);
      k = j;
    }
  }

  public static void sort(int[] nums) {
    int N = nums.length;
    for(int k = N/2; k >= 1; k--) {
      sink(nums, k, N);
    }

    while(N > 1) {
      exch(nums, 1, N--);
      sink(nums, 1, N);
    }
  }
}