排序算法

算法 排序

冒泡排序

参考资料：
冒泡排序_百度百科

冒泡排序可以说是最简单的排序算法。原理就是从数组的最后让最小的数依次排到数组的最前面，时间复杂度为$O(n^2)$。

算法代码

// BubleSort: a most simple way to sort a series of numbers.
// but not so efficient.
// @Param numbers: the array pointer storing the numbers
// @Param beginning, tail: show the range we need to sort.(begin <= i < end)
void BubleSort(int *numbers, int beginning, int tail) {
  for (int i = beginning; i < tail; i++) {
    for (int j = tail - 1; j > i; j--) {
      if (numbers[j] < numbers[j - 1]) {
        int tmp = numbers[j - 1];
        numbers[j - 1] = numbers[j];
        numbers[j] = tmp;
      }
    }
  }
}

选择排序

参考资料：选择排序_百度百科

把数列无序区中最小的一个放到无序区的最前面，从而使无序区的元素逐渐变得有序。时间复杂度也是$O(n^2)$。

算法代码:

// SelectionSort: a unstable sorting algorithm.
// @Param numbers: the array pointer storing the numbers
// @Param beginning, tail: show the range we need to sort.(beginning <= i < tail)
void SelectionSort(int* numbers, int beginning, int tail) {
  for (int i = beginning; i < tail; i++) {
    // suppose the index of the number is i, and the left of i is sorted.
    // then find the mininum of the rest and exchange it with numbers[i].
    int min = i;
    for (int j = i + 1; j < tail; j++) {
      if (numbers[j] < numbers[min]) min = j;
    }
    // exchange. when a smaller number than nubmers[i] is found, exchange them.
    if (i != min) {
      int temp = numbers[min];
      numbers[min] = numbers[i];
      numbers[i] = temp;
    }
  }
}

插入排序

参考资料: 插入败絮_百度百科

将数组中无序的元素插入到有序的元素队列中已完成排序。

算法代码：

// InsertionSort: a stable sorting algorithm that insert a number to the sorted
// sequence till all numbers are sorted.
// @Param numbers: the array pointer storing the numbers
// @Param beginning, tail: show the range we need to sort.(beginning <= i < tail)
void InsertionSort(int* numbers, int beginning, int tail) {
  for (int i = beginning, i < tail; i++) {
    // insert numbers[j] to certain position
    int temp = numbers[i+1];
    for (int j = i+1; j > beginning; j--) {
      if (numbers[temp] < numbers[j-1]) {
        // if j is not the position, move temp to the index before j
        // and store the data.
        numbers[j] = numbers[j-1];
      } else {
        numbers[j] = temp;      // if j is the position, insert it
        break;                  // and go to insert the next number.
      }
    }
  }
}

快速排序

参考资料：快速排序_百度百科

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法代码：

// QuickSort.Just to put the numbers smaller than x on the left
// and the bigger on the right.
// @Param numbers: the array pointer storing the numbers
// @Param beginning, tail: show the range we need to sort.(beginning <= i < tail)
void QuickSort(int *numbers, int head, int tail) {
  int t, i = head, j = tail, x = numbers[(i + j) / 2];
  do {
    while (x > numbers[i]) i++;
    while (x < numbers[j]) j--;
    if (i <= j) {
      temp = numbers[i];
      numbers[i] = numbers[j];
      numbers[j] = temp;
      i++; j--;
    }
  } while (i <= j);
  if (i < tail) quick_sort(numbers, i, tail);     // sort the left
  if (head < j) quick_sort(numbers, head, j);   // sort the right
}

堆排序

参考资料：
堆排序_百度百科
堆排序_维基百科

堆排序是和快排、归并排序一样常见的复杂度为$O(nlog_2n)$的算法，速度比较快。
那么，要进行堆排序，首先要把n个数据进行最大堆化(也就是把整个数据整理成一个最大堆)这样子首元素就是数组最大的元素了。把它和最后的元素进行交换，那么就可以得到最后的元素是最大的。如此类推，由于最后一个元素已经是有序的，对前面n-1个元素再进行堆调整。

inline void sort_branch(int nums[], int start, int end) {
  // sorts a branch making the maxinum in the brach to the root
  // @Param |nums|: the data array regarded as a heap
  // @|start|: the beginning index of |nums|
  // @|end|: the non-include end index of |nums|
  int larger_child;  // find the larger child and record the node
  // from node(|root|)
  // each time we search the larger child for the next step
  // loop until we have moved all larger child nodes to the upper node
  for (int root = start;
       2 * root + 1 < end;
       root = larger_child) {
    larger_child = 2 * root + 1;  // first dim larger_child as the left_child
    if (larger_child < end - 1 && nums[larger_child + 1] > nums[larger_child])
      larger_child++;
    if (nums[root] < nums[larger_child])
      swap(nums[root], nums[larger_child]);
    else
      break;
  }
}
inline void heap_sort(int nums[], int start, int end) {
  // sort with a maxinum heap.
  // @Param |nums|: the data array regarded as a heap
  // @|start|: the beginning index of |nums|
  // @|end|: the non-include end index of |nums|
  // build up a maxinum heap for the first time
  for (int i = end / 2; i >= start; i--) sort_branch(nums, i, end);
  // Now, the max number of |nums| between |start| and |end|-1 is |nums[start]|
  // for we have built up a maxinum heap. Then swap it with the last number
  // so the last number will be the largest.
  // Then sort the branch from the root to find the next maxinum number and
  // do the same again. Loop until there is only an element left, which means
  // we have sorted all elements
  for (int j = end - 1; j > start; j--) {
    swap(nums[0], nums[j]);
    sort_branch(nums, start, j);
  }
}