交换类排序包括冒泡排序和快速排序两种。

冒泡排序

        基本介绍

        冒泡排序是通过重复比较相邻元素并交换位置实现排序。其核心思想是每一轮遍历将未排序序列中的最大（或最小）元素"浮动"到正确位置，类似气泡上升。

        基本过程是从序列起始位置开始，逐个比较相邻的两个元素，以升序为例，若左边的元素大于右边的元素则交换两个元素的位置，每轮遍历之后都会使一个最大元素移动到最右边，在下一轮遍历时就无需再考虑这个元素。

        实现过程

        以升序为例，从起始位置开始遍历，2 < 5，无需交换，5 < 8，无需交换，8 > 3，需要交换。

         交换之后继续比较8,6,8 > 6，需要交换

         交换之后继续比较，8 < 9，无需交换，继续比较,9 > 1，需要交换

         交换之后继续比较,9 > 4，需要交换

        交换之后继续比较,9 > 7，需要交换 

        最终完成一轮遍历，将最大的元素移到了右边，然后继续后续遍历，后续遍历则不用再考虑9了，再找出一个最大值移到右边，进行size - 1次遍历即可完成排序。 

        代码展示

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void sort(int *a,int len)
{//len个元素需要排序len - 1次for (int i = 0; i < len - 1; i++){//单轮循环可以找出来一个最大/最小并移到边上，下一轮循环就不考虑该元素，len - 1次之后只剩下一个元素，无需排序for (int j = 0; j < len - i - 1; j++){if(a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}//打印每轮排序的结果for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}}int main(int argc, char const *argv[])
{sort(array,9);return 0;
}

        代码优化 

        如果在排序过程中，我们发现在某一次遍历过程中都没有发生元素交换，那么我们就可以认为序列已经排序完成，此时没有必要遍历size - 1次。遍历size - 1次一定可以使序列有序，但是有些序列执行更少次数的遍历就已经有序了。所以我们可以减少这些无意义的遍历，设置一个标志位swap_flag来记录遍历过程中是否发生了交换，若无交换则提前结束排序。

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void sort(int *a,int len)
{//len个元素需要排序len - 1次for (int i = 0; i < len - 1; i++){//记录该轮循环是否发生了交换int swap_flag = 0;//单轮循环可以找出来一个最大/最小并移到边上，下一轮循环就不考虑该元素，len - 1次之后只剩下一个元素，无需排序for (int j = 0; j < len - i - 1; j++){if(a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;swap_flag = 1;}}//如果本轮循环没有发生交换，则已经全部有序，跳出循环。if(swap_flag == 0)break;for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}}int main(int argc, char const *argv[])
{sort(array,9);return 0;
}

       优化效果对比

        未经优化的冒泡排序运行结果如下，完整进行了8次(size - 1)遍历。

        经优化的冒泡排序运行结果如下，进行了7次遍历，对于不同的序列，优化效果有所不同。运行结果仅打印了6次是因为break写在了打印之前，排序完成之后的后一次遍历才能检测到排序已完成。

 快速排序

        基本介绍

        快速排序的思想是通过一个基准值，把一组数据分成两个部分（一边小，一边大），然后，在对两个部分，分别找一个基准值，再次进行排序，直至每一个小部分不可再分，所得到的整个数组就成为了有序数组。

        快速排序的基本过程是先选择一个数作为基准值 (这里用的是第一个数，key)，进行一次排序，(以升序为例)然后将所有比'基准值小的数'放在基准值的'左边'， 将所有比'基准值大的数'放在基准值的'右边'，然后再对两边的，各自'再取一个数作为基准值'，然后再次排序（递归[自己调自己]）。

        实现过程

        定义两个指示器，low和high，分别指向首尾。定义一个i,j分别指向low和high，用于遍历。

         从 j 开始逐个向左开始和基准值相比较。7大于key，不移动，4 > key，不移动，1 < key，要移动到左边。由于已经用key保存了基准值，所以放到左边是可以直接在a[i]处赋值。

        之后再从左边开始，1 < key，不动，5 > key，需要移动到右边，直接在右边赋值为5即可。放在这里的原因是因为这里的元素已经在前面被移动到了其他位置，不用担心数据丢失，而且下标位置也属于右边。

        这样完成一轮之后，发现一开始不符合规律的5已经移到了右边，不符合规律的1已经移到了左边。然后继续移动指示器，寻找不符合规律的元素。从 j 处继续，9 > key，不移动，6 > key，不移动，3 > key，不移动，8 > key，不移动，比较完8之后，发现 i 已经等于 j 了，此时结束，发现基准值应该插入到 i  、 j 处，在i 、j 处插入基准值。

         然后我们发现，基准值2的左边都比他小，右边都比他大，就以基准值为界限，分为了两部分。

        然后再对左边和右边分别找基准值再进行排序，之后再对分成的两部分排序，一直递归，直到不可再分为止。

        递归最重要的是要找到终止条件，否则就会一直套娃，这里的终止条件是不可再分，不可再分具体表现在哪呢？在本例中，进行一轮之后，以2为界限分为左右两部分，左边部分是[low,i - 1],右边部分是[i + 1,high]，不可再分就代表只有一个元素，即low = i - 1,i + 1 = high时就是不可再分，再加上一个数学限制条件，low应该小于i - 1，所以最终的终止条件是low >= i-1和high <= i+1.

         代码展示

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void quick_sort(int *a,int low,int high)
{//定义两端的下标int i = low,j = high;//选择一个基准值，这里选择第一个元素int key = a[i];//循环之后的结果是，比基准值小的都放在左边，比基准值大的都放在右边//同时i,j都在向中间靠近，当i = j时循环跳出，就找到了区分左右的边界(i、j)//之后a[i] = key是将基准值放在中间的分界。//条件设置为i < j就是因为当i，j相遇时，即找到了分界线的位置（i、j），然后将基准值插入到这个位置上//外层循环一次的结果是将不属于两边的元素互换（比如位于左边但是没有小于基准值）while (i < j){//从右边开始，右边的元素应比基准值大，寻找不符合的元素while (i < j && a[j] >= key)j--;//将不符合的元素放到左边，直接覆盖是因为：//第一次循环，a[i]是基准值，已经用key保存，所以可以覆盖//之后的循环，a[i]也是不符合条件的元素，已经在上一次循环中被移动，所以可以覆盖a[i] = a[j];//从左边开始，左边的元素应比基准值小，寻找不符合的元素while (i < j && a[i] <= key)i++;//将不符合的元素放到右边，直接覆盖是因为a[j]的值已经在上边被移动了。a[j] = a[i];}//循环结束，i，j相遇//上述循环中，由于基准值已经用key保存了，所以其所在位置充当了一个交换缓冲的角色，//a[i],a[j]的每次移动都让自己之前的地方成为了下一个移动的目的地a[i] = key;//对基准值左右两边的元素再进行快排，直到无法再分//i,j的位置就是基准值，左边就是[low,i - 1],右边就是[i + 1,high]//不可再分的条件就是i - 1 和 low不满足i - 1 > low,i + 1 和 high不满足i + 1 < highif(i - 1 > low)quick_sort(a,low,i - 1);if(i + 1 < high)quick_sort(a,i + 1,high);
}int main(int argc, char const *argv[])
{quick_sort(array,0,8);for (int j = 0; j < 9; j++){printf("%d ",array[j]);}printf("\n");return 0;
}