排序算法之交换排序（快排的三种方法的单趟排序）（上）

**个人主页：欢迎大家光临——>**沙漠下的胡杨

** 各位大帅哥，大漂亮**

如果觉得文章对自己有帮助

可以一键三连支持博主

** 你的每一分关心都是我坚持的动力**

** **

☄：本期重点：快速排序三种方法的单趟实现

** 希望大家每天都心情愉悦的学习工作。**

交换排序的思想：

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序的思想：

冒泡排序比较简单，我们之前使用也很多，简单讲解，就是比较两个数，如果比他大就交换，没有他大就接着向后比，一直到数组结束，这是单趟排序，多趟就是控制好下标，进行循环即可。

冒泡代码实现：

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}


void BubbleSort(int* a, int n)
{
    assert(a);

    for (int j = 0; j < n - 1; ++j)
    {
        int exchange = 0;//定义变量，用于判断是否交换过
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)//没有交换过表示有序，直接跳出
        {
            break;
        }
    }
}

冒泡排序的特性：

1. 冒泡排序是一种非常容易理解的排序

**2. 时间复杂度：O(N^2) **

**3. 空间复杂度：O(1) **

4. 稳定性：稳定

快速排序的整体框架：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

简单理解：

我们先选出一个数，然后把所有数据分为三部分，第一部分是大于这个数的部分，第二个部分是这个数，第三个部分是大于这个数的。

然后，进行递归求解，对于小于的部分，选一个数，分为三部分。对于大于的部分，选一个数，分为三部分进行求解。

递归返回条件：首先是区间不存在返回，区间只有一个数返回。

快速排序单趟实现逻辑：

1. hoare版本单趟实现（左右指针法）

首先我们先学习下最经典的左右指针法：

首先我们一般都会这两个疑问？（后续挖坑法和前后指针法同理）

1.为什么要选左边的数作为初识位置比较位置。

2.为什么要让右边先走？

我们之所以选取左边，只是因为方便，容易控制，你也可以选择右边，或者任意位置，都可以，只不过在代码逻辑上稍微复杂点，不容易控制。

我们让右边先走，是因为最后我们要把 key位置的数据移动到相遇位置，也就是key位置数据的正确位置，所以我们应该保证让左边来遇到右边，就是让右边的位置先到等着左边。因为我们选取的是左边的key，所以左边的下标就是少了 1 ，我们让右边先走就可以刚好弥补过来。反之，如果我们选取左边为key，还让左边先走，那么我们最后就会发现，这个位置的下标就错了，不能保证左边都是大于key的数了。

综上：我们如果选择了左边为key，那么就让右边先走，选择右边为key，就让左边先走。

我们看着示意图实现下单趟排序代码：

//前后指针法单趟排序
int PartSort(int *a,int left,int right)
{
    int keyi = left;//先保存最左侧下标，作为keyi

    while (left < right)
    {
        //先让右走，找小，并且不能越界
        while (left < right && a[right] >= a[keyi])
        {
            --right;
        }

        //再让左走，找大，不越界。
        while (left < right && a[left] <= a[keyi])
        {
            ++left;
        }

        //交换左边大的，和右边小的
        Swap(&a[left], &a[right]);
    }

    //循环完成，我们在最后交换下，相遇位置的和原来keyi位置的值
    Swap(&a[keyi], &a[left]);

    //返回相遇位置的下标是为进行下一步递归。
    return left;
}

2.挖坑法单趟排序实现

我们看下有点意思的挖坑法。

我们观察发现，还是先选取一个位置作为我们比较的数同时也是坑位，然后还是先让右边走，然后把数据放到坑中，形成一个新的坑，接着左边走，再把数据放入坑中，形成新坑，最后，把我们选取位置的数据放到最后一个坑位上，就满了。

其实在我们调试发现，"挖坑" 只不过是形象描述了，其实乜有坑位，只是数据重复，然后替换掉了。

图示比较简单，我们尝试实现下单趟排序：

//挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];//保存最左边初始位置的值

    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            --right;
        }

        a[left] = a[right];//产生一个坑位

        while (left < right && a[left] <= key)
        {
            ++left;
        }

        a[right] = a[left];//上一个坑位填上，产生新的坑位
    }

    a[left] = key;//把最后的坑位填上了。

    return left;//返回最后相遇的下标，以便后序递归
}

3.前后指针法

前后指针法和左右指针类似但是不完全一样哦。

前后指针法，其实就是定义两个指针，一个是prev为初始位置，一个是cur为初始位置+1，cur是遇见大于初始位置的值停下，交换（prev+1）下标的值，直到 cur 指针走到结尾，此时就交换prev指针和初始位置即可。

简单理解：

前后指针，就是不停的把大于初始位置的数据向后移动，最后一个指针走到末尾了，另一个指针此时的指向，刚好就是我们初始位置在整个数据中要排的位置。

需要注意的是：我们每次交换的都是prev+1的下标值，如果 prev = cur 时，此时我们不用交换，prev也不用++，只需要 cur++ 即可。

前后指针的单趟代码实现：

//前后指针法
int PartSort3(int *a, int left, int right)
{
    int prev = left;//后指针
    int cur = left + 1;//前指针
    int keyi = left;//初始位置

    while(cur <= right)//当cur小于等于最右边时进入循环
    {
        //当cur找到比初始位置大的数，如果此时cur不等于prev，
        //那么就交换cur和++prev，一定是前置++。
        if (a[cur] < a[keyi] && prev != cur)
        {
            Swap(&a[cur], &a[++prev]);
        }
        cur++;
    }
    Swap(&a[prev], &a[keyi]);//最后交换prev和初始位置即可

    return prev;//返回prev为了后续递归做铺垫
}

补充后续：

关于快速排序还有很多知识在下期继续讲解，包括单趟之后的递归，以及非递归的实现，以及快速排序的优化。