Question

介绍两种经典的交换排序——冒泡排序和快速排序。

一、冒泡排序

冒泡排序是一种交换排序，它的主要过程是：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。比较一趟之后，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 冒泡排序
 */
void BubbleSort(int *array)
{
  int i, j, temp;
  for (i = 0; i < n - 1; i++)
  {
    for (j = 0; j < n - 1 - i; j++)
    {
      if (array[j] > array[j + 1])
      {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

int main()
{
  int i;
  int *array;
  printf("请输入数组的大小：");
  scanf("%d", &n);
  array = (int*) malloc(sizeof(int) * n);
  printf("请输入数据（用空格分隔）：");
  for (i = 0; i < n; i++)
  {
    scanf("%d", &array[i]);
  }
  BubbleSort(array);
  printf("排序后为：");
  for (i = 0; i < n; i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

二、快速排序

快速排序是对冒泡排序的改进，它的基本思想是通过一趟排序将数据分成两部分，一部分中的数据都比另一部分中的数据小，再对这两部分中的数据再排序，直到整个序列有序，如下图所示。

快速排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 分割使枢轴记录的左边元素比右边元素小
 */
int Partition(int *array, int low, int high)
{
  int pivotkey = array[low];
  array[0] = array[low];
  while (low < high)
  {
    while (low < high && array[high] >= pivotkey)
    {
      high--;
    }
    array[low] = array[high];
    while (low < high && array[low] <= pivotkey)
    {
      low++;
    }
    array[high] = array[low];
  }
  array[low] = array[0];
  return low;
}

/*
 * 快速排序递归实现
 */
void QuickSort(int *array, int low, int high)
{
  if (low < high)
  {
    int pivotloc = Partition(array, low, high);
    QuickSort(array, low, pivotloc - 1);
    QuickSort(array, pivotloc + 1, high);
  }
}

int main()
{
  int i;
  int *array;
  printf("请输入数组的大小：");
  scanf("%d", &n);
  array = (int*) malloc(sizeof(int) * (n + 1));
  printf("请输入数据（用空格分隔）：");
  for (i = 1; i <= n; i++)
  {
    scanf("%d", &array[i]);
  }
  QuickSort(array, 1, n);
  printf("排序后为：");
  for (i = 1; i <= n; i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

三、小结

这一章讲了交换排序的两个经典算法，冒泡排序和快速排序。冒泡排序就像水中的气泡一样，小的数据往上浮，它是稳定的排序，它的时间复杂度是 O(n^2)。快速排序是对冒泡排序的改进，它的主要思想是通过一趟排序将数据分成两部分，一部分中的数据都比另一部分中的数据小，再对这两部分中的数据再排序，直到整个序列有序，它是不稳定的排序，它的时间复杂度是 O(nlogn)。

作业

我们这里的快速排序是用递归实现的，那么怎么用非递归实现呢？

实验中有任何问题欢迎到 实验楼问答 提问。