排序

选择排序

选择排序是每次从剩下的元素中挑出最小的一个来，放到已经排序好的队列的尾部。它的特点是：已经排好序的部分是最终结果，比较次数固定，移动次数少；

void selection_sort(a, from , to ) {
    if (from == to) return;
    var index = getMinIndex(a, from, to);
    if (index != from) {
        exchange(a, from, index)
   }
   selection_sort(a, from +1, to);
}

int getMinIndex(a, from, to) {
    assert(from < to);
    min = a[from];
   for (index = from +1; index < to; index ++) {
       if (a[from] > a[index] )  min = index;
   }
  return min;
}

插入排序

插入排序典型的应用就是抓牌时的做法，每抓一张牌，都会把它插入到有序的位置。所以虽然手上的牌已经是有序的，却不是最终位置。与选择排序的区别在于：比较次数会少一些，移动次数会多一些。

void insertion_sort(a, from, to ) {
  for (index =from +1; index < to; index ++) {
     pos = getInsertionPosition(a, from, index);
     insertInto(a, pos, index);
   }
}
void insertInto(a, pos, index) {
   if (pos == index) return
   temp = a[index];
   for (in = index;index > pos; --in) a[in] = a[in -1];
   a[pos] = temp;
}

int getInsertionPosition(a, from, index) {
   for (pos = from; pos < index; ++pos) {
     if (a[pos] > a[index]) return pos;
  }
  return pos; /* same as index*/
}

另外一种实现是反向比较，或者边比较边交换的做法。但是我有种如果那样做，逻辑就没有那么清晰的感觉。

希尔排序

谁把shell排序起了这个名字，到底想要谁来猜！

Shell排序是插入排序的一种进货，它的思想是每次移动的时候，能够多移动一点，这对于混乱程序具有某种一致性（够随机）的数据来说，会有更好的结果，而且每次在较小的规模上进行排序，而且一轮之后也会比较有效。

void shellsort(a, from, to) {
      step = (from - to ) / 3; /* shell排序的步长选择是一门艺术，有高手给出过证明*/
     while (step >= 1)  {
        for (i = 0; i <step; i++) { /* for each step */
             insertion_sort(a, from + i, to, step);
        }
        step = step /3;
     }
}

上面的算法偷了一点懒，直接把插入排序进行了扩展，增加一个step参数。

归并排序

归并排序是把两个已经排好充的序列，归并是一个序列的过程。所以每次比较，只需要对两个序列最上面的元素进行归并。不费话，直接上伪代码

void mergesort(a, low, hi) {
   if (low >= hi ) return;
   mid = (hi+low)/2 ;
   mergesort(a, lo, mid) ;
   mergesort(a, mid + 1, hi);
  aux = array_new(a, low, hi);
  index = low;
  for (p1 = low, p2 = mid + 1; p1 < mid && p2 < hi; ) {
     if (aux[p1] < aux[p2]) a[index ++] = aux[p1++]
     else a[index++] = aux[p2++] ;
  }
  if (p1 == mid) array_copy(a, index, hi - p2) ;
  if (p2 == hi) array_copy(a, index, mid - p1);
}

也可以不用递归，从小往大归并。那么就是两两归并，然后四四归并，然后八八归并。伪代码走起：

void mergeup(a, low, hi) {
  len = hi -low;
  for (step = 1; step < len ; step *=2 ) {
    for (index = 0; index < len; index += 2*step) {
          merge(a, low + index, step);
  }
}

void merge(a, from, len) {
  aux = array_new(a, from, from +2*len);
  index = from;
  for (p1 = from, p2 = from + len; p1 < from +len && p2 < from + 2*len) {
     if (aux[p1] < aux[p2]) a[index ++] = aux[p1++]
     else a[index++] = aux[p2++] ;
  }
  if (p1 == from + len) array_copy(a, index, from + 2*len - p2) ;
  if (p2 == hi) array_copy(a,  index, from + len - p1);
}

最后编辑于：2020.03.23 20:05:05