排序（一）

快速排序（ qsort ）

在c的函数库stdlib中提供了一个叫qsort的函数，这个函数能够提供快速排序的功能。它共有四个参数：

第一个是void *base，是要被排序的数组的基地址，即数组的首地址，亦即第一个元素的地址。
第二个是数组元素的个数size_t num。
第三个则是size_t size，表示的是数组中每个元素所占的字节数。
最后一个参数是int (* comparator) (const void *, const void *)，是一个函数，首先，从这个参数有两个括号可以看出这是一个函数，其次，最开始的int表示其函数的返回值类型必须是int，最后，此函数对参数的要求是在第二个括号中的，即两个const void *。

使用qsort的代码如下：

int compare(const void *a, const void *b)
{
  return *(int *) a - *(int *) b;
}

//...
    int a[100];
//...
    qsort(a, 100, sizeof(int), compare);
//...

在此处，我们使用qsort的原因是为了程序提供一个对拍程序，以提供正确的数据，为下面的排序算法实现提供一个对比的对象。

为了生成大量的随机数据，可以使用python的random库，如下：

import random

i = 0
while i < (1<<15):
  print random.randint(1, 1000000),
  i += 1
print

在上面的代码里面，1<<15表示的是二进制的左移操作，相当于2的15次方，在C/C++语言里可以同样如此使用，非常方便。

上述代码可以在屏幕上打出1<<15个1到1000000之间的随机数，我们可以通过>将其重定向到文件中，如python gen_random.py > random.data

冒泡排序与选择排序

冒泡排序

每次把前n个进行比较，把这n个中最大的数放在最后面，再比较剩下n-1个，选出最大的，以此类推。

其代码如下：

for (int i = n-1; i > -1; i--) {
  int loc = 0;
  for (int j = 1; j < i+1; j++) {
    if (a[j] > a[loc])
      loc = j;
  }
  int temp = a[i];
  a[i] = a[loc];
  a[loc] = temp;
}

在上述的代码中，我们使用了loc，而没有使用max之类的变量，可以避免对max的初始化（例如将其初始化为0是不好的，为什么？），也可以避免提供多个变量（如max与loc）后要保证变量间的一致性，实际上，在最开始实现程序的时候，笔者就犯了这种错误。

选择排序

选择排序与冒泡排序正好相反，它是从n个中选取最小的，把它排在最前头，再从剩下n-1个中比较出最小的，排在这n-1个的最前面，以此类推

其代码如下：

  for (int i = 0; i < n; i++) {
    int loc = n-1;
    for (int j = n-2; j > i-1; j--) {
      if (a[j] < a[loc])
        loc = j;
    }
    int temp = a[i];
    a[i] = a[loc];
    a[loc] = temp;
  }

插入排序

插入排序是每次把前n个进行排序，之后再排前n+1个，以此类推，拍完所有的数。

其代码如下：

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