交换排序：冒泡排序和快速排序的实现

冒泡排序

冒泡排序的定义：冒泡排序(Bubble Sort)是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上 “漂浮”(左移), 或者说使关键字大的记录如石块一样逐渐向下 “坠落”(右移)。

冒泡排序的代码

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

void bubble_sort(int serice[], int length)
{
    int flag = 1; // 用来标记某一趟排序是否发生交换
    int m = length - 1;

    while ((m > 0) && (flag == 1))
    {
        flag = 0; // flag置为0，如果本趟排序没有发生交换，则不会进行下一趟排序
        for (int j = 0; j <= m; j++)
        {
            if (serice[j] > serice[j+1])
            {
                flag = 1;
                /* 交换位置 */
                int temp = serice[j];
                serice[j] = serice[j+1];
                serice[j+1] = temp;
            }
        }
        m--;
    }
}

void print_series(const int series[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", series[i]);
    }
    printf("\n");
}

int main(void)
{
    int series[] = {5, 7, 6, 8, 9, 2, 1, 4, 3};
    int len = sizeof(series) / sizeof(series[0]);

    // 排序前，打印
    printf("排序前，打印\n");
    print_series(series, len);

    // 冒泡排序
    bubble_sort(series, len);

    // 排序后，打印
    printf("排序后，打印\n");
    print_series(series, len);

    return 0;
}

每一轮循环下来，每一个最大值都会排到最右侧，然后最大值不再参与下一轮的排序。

快速排序

快速排序的定义：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列

快速排序的代码实现：

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

/* 
 * @param series表示一个一维整型数组
 * @param low表示数组下标
 * @param high表示数组下标
 * 对于传入的形参low和high来说，要求满足low < high
 */

void quick_sort(int series[], int low, int high)
{
   if (low < high)
   {
        int i = low;
        int j = high; 
        int x = series[low];

        while (i < j)
        {
            while (i < j && series[j] >= x) // 从右往左
                j--;
            if (i < j)
                series[i++] = series[j];
            while (i < j && series[i] < x) // 从左往右
                i++;
            if (i < j)
                series[j--] = series[i];
        }
        series[i] = x;
        quick_sort(series, low, i - 1);
        quick_sort(series, i + 1, high);
   }
}

void print_series(const int series[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", series[i]);
    }
    printf("\n");
}

int main(void)
{
    int series[] = {5, 7, 6, 8, 9, 2, 1, 4, 3};
    int len = sizeof(series) / sizeof(series[0]);

    // 排序前，打印
    printf("排序前，打印\n");
    print_series(series, len);

    // 快速排序
    quick_sort(series, 0, 8);

    // 排序后，打印
    printf("排序后，打印\n");
    print_series(series, len);

    return 0;
}

取一个关键值(取待排序list的第一个值)，把小于关键值的交换到左边，把大于等于关键值的交换到右边，。。。，把关键值放到中间位置。关键值不参与递归
把关键值左边的所有值递归执行，直到排序完成。把关键字右边的所有值递归执行，直到排序完成。

反思总结

冒泡排序

时间复杂度：O(\(n^2\))

空间复杂度：O(1)

算法特点：

1）稳定排序

2）可用于链式存储结构

3）移动记录次数较多。当初始记录无序，n较大时，此算法不推荐使用

快速排序

时间复杂度：O(\(nlog_2n\))

空间复杂度：O(\(log_2n\)) ~ O(\(n\))

算法特点：

1）记录非顺次的移动导致排序方法是不稳定的

2）需要确定界限，仅适合顺序结构

3）适合初始记录无序且n较大时的情况

参考引用

数据结构第二版：C语言版（严蔚敏）