常用的排序算法

算法复杂度及稳定性

排序方法	最好时间	平均时间	最坏时间	辅助空间	稳定性
直接插入	O(n)	O(n^2)	O(n^2)	O(1)	稳定
二分插入	O(n)	O(n^2)	O(n^2)	O(1)	稳定
希尔		O(n^1.25)		O(1)	不稳定
冒泡	O(n)	O(n^2)	O(n^2)	O(1)	稳定
快速	O(nlgn)	O(nlgn)	O(n^2)	O(lgn)	不稳定
直接选择	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
堆	O(nlgn)	O(nlgn)	O(nlgn)		不稳定
归并	O(nlgn)	O(nlgn)	O(nlgn)	O(n)	稳定
基数	O(d(rd+n))	O(d(rd+n))	O(d(rd+n))	O(rd+n)	稳定

算法实现

直接插入

算法步骤

1. 将序列的第一个元素作为有序序列，第二个元素直至最后一个元素作为待排序序列;
2. 从前往后依次扫描待排序序列，将扫描的元素依次插入到有序序列的适当位置。

原理示意

程序实现

void insertsort(int array[], int length)
{
  if (array == NULL || length <= 0)
    return;

  int index, temp;
  for (int i = 1; i<length; i++)
  {
    // 保存 array[i] 至中间变量
    temp = array[i];
    index = i;

    // 寻找插入位置, index = 1,2,...,i
    while (index>0 && temp<array[index - 1])
    {
      array[index] = array[index - 1];
      index--;
    }

    // 插入数据
    array[index] = temp;
  }
}

// 使用实例
int main()
{
  int array[] = { 23,34,22,67,87,56,15,62,74,46 };
  int length = sizeof(array) / sizeof(int);
  insertsort(array, length);
  return 0;
}

二分查找插入

二分思想

二分查找插入是在直接插入的基础上进行优化，由于在插入前需要查找插入位置，而插入位置处于有序序列中，所以可以使用二分查找替代原先的逐个扫描，提高查找效率。

二分实现

void binaryInsertsort(int array[], int length)
{
  if (array == NULL || length <= 0)
    return;

  int index, temp, left, right, middle;
  for (int i = 1; i < length; i++)
  {
    temp = array[i];      // 将本次待插入数据存入temp
    left = 0;
    right = i - 1;

    if (array[i] >= array[0])
    {
      // 二分查找
      while (left<=right)
      {
        middle = (left + right) / 2;
        if (temp < array[middle])
          right = middle - 1;
        else
          left = middle + 1;
      }
    }

    // 移动数据，left即为查找到的插入位置
    for (int j = i - 1; j >= left; j--)
      array[j + 1] = array[j];

    array[left] = temp;      // 插入temp到指定位置
  }
}