C语言常见排序算法之交换排序(冒泡排序,快速排序)

交换排序主要有两种：冒泡排序和快速排序。下面我将分别详细介绍这两种排序算法的原理、过程和示例。

冒泡排序

原理

冒泡排序是一种基本的排序方法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复操作直到排序完成。

过程

冒泡排序的过程可以被描述如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始的一对到结尾的最后一对。在这一步执行完后，最后的元素是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 重复步骤1~3，直到排序完成。

示例

下面是一个冒泡排序的例子：

int a[] = {56, 12, 78, 23, 99, 43, 21, 10};
int len = sizeof(a) / sizeof(int);
for (int i = 0; i < len - 1; i++)
{
    for (int j = 0; j < len - 1 - i; j++)
    {
        if (a[j] > a[j + 1])
        {
            int tmp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = tmp;
        }
    }
}

在上面的例子中，我们先定义一个待排序的数组a，然后通过两层循环遍历数组，若前面的数大于后面的数，则交换两个数的位置。最后得到的数组为{10, 12, 21, 23, 43, 56, 78, 99}，也就是一个从小到大排列的有序数组。

快速排序

原理

快速排序是目前使用最广泛的排序算法之一。它采用的是分治法的思想，基本思路是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均小于另一部分记录的关键字，分别对这两部分继续进行排序，以达到整个序列有序的目的。

过程

快速排序的过程可以被描述如下：

1. 从数列中挑出一个元素，称为“基准”。
2. 重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以放到任一边）。在这个分区结束后，该基准就处于数列的中间位置。称之为分区操作。
3. 递归地（recursive）把小于基准值的子数列和大于基准值的子数列排序。

示例

下面是一个快速排序的例子：

void quickSort(int a[], int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int left = start;
    int right = end;
    int pivot = a[left];
    while (left < right)
    {
        while (left < right && a[right] >= pivot)
        {
            right--;
        }
        a[left] = a[right];
        while (left < right && a[left] <= pivot)
        {
            left++;
        }
        a[right] = a[left];
    }
    a[left] = pivot;
    quickSort(a, start, left - 1);
    quickSort(a, left + 1, end);
}

在上面的例子中，我们定义了一个快速排序函数quickSort，并传入待排序的数组a以及排序的起始和结束位置start和end。在函数内部，我们先确定一个基准pivot为数组的第一个元素a[start]，然后通过两个指针left和right，不断向中间移动，在移动的过程中不断比较left和right指针所指的数和基准pivot的大小，直到left和right指针重合。这个过程可以视为一个“分区”的过程，被分成基准左边的数和右边的数。接着我们对左右两个分区分别递归执行这个过程即可。