排序

排序算法有很多，常见的有选择排序，插入排序，冒泡排序，快速排序等。gcc的标准库也提供了一个快速排序的标准函数

 

void qsort (void* base, size_t num, size_t size,

            int (*compar)(const void*,const void*));

 

快速排序

void qsortr(int a[], int len)
{
  int l, h, x;

  if (len <= 1)
  {
    return;
  }
  l = 0;
  h = len - 1;
  x = a[l];

  while (l < h)
  {
    while (l < h && a[h] > x)
    {
      h--;
    }
    if (l < h)
    {
      a[l++] = a[h];
    }
    while (l < h && a[l] < x)
    {
      l++;
    }
    if (l < h)
    {
      a[h--] = a[l];
    }
  }
  a[l] = x;

  qsortr(a, l);
  qsortr(a + l + 1, len - l - 1);
}

下面这种实现更灵活些

void qsortr_range(int a[], int low, int high)
{
  int l, h, x;
  if (low < high)
  {
    l = low;
    h = high;
    x = a[l];
    while (l < h)
    {
      while (l < h && a[h] > x)
      {
        h--;
      }
      if (l < h)
      {
        a[l++] = a[h];
      }
      while (l < h && a[l] < x)
      {
        l++;
      }
      if (l < h)
      {
        a[h--] = a[l];
      }
    }
    a[l] = x;

    qsortr_range(a, low, l - 1);
    qsortr_range(a, l + 1, high);
  }
}

上面两种都采用的递归实现

 

void qsort_range(int a[], int low, int high)
{
  int l, h, x;

  int size = 2;
  int *stack = malloc(size * sizeof(int));
  int top = -1;
  *(stack + (++top)) = low;
  *(stack + (++top)) = high;


  while (top >= 0)
  {
    high = *(stack + (top--));
    low = *(stack + (top--));

    l = low;
    h = high;
    x = a[l];

    if (l < h)
    {
      while (l < h)
      {
        while (l < h && a[h] > x)
        {
          h--;
        }
        if (l < h)
        {
          a[l++] = a[h];
        }
        while (l < h && a[l] < x)
        {
          l++;
        }
        if (l < h)
        {
          a[h--] = a[l];
        }
      }
      a[l] = x;

      if (top + 4 > size - 1)
      {
        size += 4;
        stack = realloc(stack, size * sizeof(int));
      }
      *(stack + (++top)) = low;
      *(stack + (++top)) = l - 1;

      *(stack + (++top)) = l + 1;
      *(stack + (++top)) = high;
    }
  }
  free(stack);
}

 

 

 

除了上面的排序算法，还有很多，比如堆排序。

 

堆排序

 

 

没办法从word中直接粘贴进来，截的图。
 

1、堆排序中的堆

2、堆排序－如何构造初始堆