0
0

【数据结构】交换排序之冒泡排序与快速排序

承接上文：

(32条消息) 【数据结构】常见排序之插入排序与选择排序_vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple_/article/details/126568614?spm=1001.2014.3001.5502https://blog.csdn.net/vpurple_/article/details/126568614?spm=1001.2014.3001.5502

交换排序

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

1.冒泡排序

冒泡排序动图演示：

冒泡排序完整代码：

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

冒泡排序的特性总结：

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

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

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

  4. 稳定性：稳定

2.快速排序递归版

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

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

子区间如何有序？ 将子问题进行递归，类似二叉树前序遍历。

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

将区间按照基准值划分为左右两半部分的常见方式有：

1.1. hoare版本

1.1.1hoare1.0版本

hoare演示动图如下：

我们先进行单趟排序：

  1. 选择一个 key , 一般是第一个或者最后一个。
  2. 单趟排序最后，要求小的数在key左边，大的数在key右边。

单趟排序的作用：

  1. key已经找到了最终位置，把key排好。
  2. 分割出了两个子区间，左区间比key小，右区间比key大，如果子区间有序，那整体有序。

hoare版本初代代码解析如下：

hoare版本初代代码如下：

//返回最终基准值下标
int partion(int arr[], int left, int right)
{
    //选最左边数k为基准，两边开始走，比k大到右边，比k小到左边
    int k = left;
    
    while (left < right)
    {
        if (arr[left] > arr[k] && arr[right] < arr[k])
        {
            swap(&arr[left], &arr[right]);
        }
    
        if (arr[left] <= arr[k])
        {
            left++;
        }

        if (arr[right] >= arr[k])
        {
            right--;
        }

    }

    if (arr[left] > arr[k])
    {
        left--;
    }

    swap(&arr[k], &arr[left]);

    return left;
}

1.1.2.hoare2.0版本（三数取中法+使得相遇点大小可控

可采用三数取中法优化进行基准值的选择，从而有效解决递归层度太深的问题。

三数取中法代码如下：


//优化 三数取中法
int mid_ThreeNum(int arr[], int left, int right)
{
    int mid = (left + right) / 2;
    if (arr[left] < arr[mid])
    {
        if (arr[mid] < arr[right])
        {
            return mid;
        }
        else//mid最大
        {
            if (arr[left] > arr[right])
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }
    else//arr[left]>arr[mid] 
    {
        if (arr[left] < arr[right])
        {
            return left;
        }
        else//left最大
        {
            if (arr[mid] > arr[right])
            {
                return mid;
            }
            else
            {
                return right;
            }
        }
    }
}

使得相遇点大小可控

   如果最左边的数做key,就要保证相遇位置比key小，从而使得key和相遇点交换位置之后仍然满足key左边的数比key小。

   而相遇的位置如何保持比key小呢 —— 左边第一个值做key时，R先走，每次交换过后也是R走 。

    以此类推当右边第一个值做key时，L先走，相遇点要比key大。

原因分析如下：

  1. R先停，L与R相遇，此时的相遇位置比key小。
  2. L先停（这里的L先停是L与R交换后的停，此时L指向的数据已被交换），R与L相遇，此时相遇位置比key小。

所以可以优化为：

hoare2.0版本完整代码如下：

int partion0(int arr[], int left, int right)
{
    //选最左边数k为基准，两边开始走，比k大到右边，比k小到左边
    int k = mid_ThreeNum(arr, left, right);
    swap(&arr[left], &arr[k]);
    k = left;
    while (left < right)
    {
        while(arr[right] >= arr[k] && left < right)
        {
            right--;
        }
        
        while (arr[left] <= arr[k]&&left<right)
        {
            left++;
        }

        if ( left < right)
        {
            swap(&arr[left], &arr[right]);
        }
    }
    
    swap(&arr[k], &arr[left]);
    return left;
}

1.1.3小区间优化

   快速排序类似于二叉树的形态，在调用的最后一层占一半的调用次数，倒数第二层占四分之一的调用次数依次类推，可得倒数三层合计可占百分之八十以上的递归调用次数。

    可以选择在倒数8层的时候采用插入排序，可有效减少递归深度。

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int array[], int left, int right)
 {
    
    if (right - left <= 8)
    {
        InsertSort(array + left, right - left + 1);
    }
    else
    {
        // 按照基准值对array数组的 [left, right]区间中的元素进行划分
        int div = partion0(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div] 和 [div+1, right]
        // 递归排[left, div]
        QuickSort(array, left, div - 1);

        // 递归排[div+1, right]
        QuickSort(array, div + 1, right);
    }
}

1.2.挖坑法

1.2.1.挖坑法思路解析

挖坑法动图演示如下：

   令最右边为key,第一个坑位就在最右边。最右边为坑左边先走，找大，把找出的大的值填到右边的坑位去，然后左边这个位置就为坑，右边走，找小，把找出小的值填到左边的坑位，然后右边这个新的位置就是新的坑，以此类推……当左右边相遇时，此时相遇的位置就是最后一个坑位，把key中的值填入坑位即可，单趟排序结束，依次递归即可。

1.2.2.挖坑法完整代码

//挖坑法
int partion2(int* arr, int begin, int end)
{
    //三数取中
    int k = mid_ThreeNum(arr, begin, end);

    //令最右边为坑位
    int key = arr[k];
    swap(&arr[k], &arr[end]);
    k = end;//k指向的就是坑位

    //begin找大 end找小
    while (begin < end)
    {
        while (begin < end)
        {
            if (arr[begin] > key)
            {
                arr[k] = arr[begin];
                k = begin;
                break;
            }
            begin++;
        }

        while (begin < end)
        {
            if (arr[end] < key)
            {
                arr[k] = arr[end];
                k = end;
                break;
            }
            end--;
        }

    }
    arr[k] = key;
    return k;
}

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int array[], int left, int right)
 {
    
    if (right - left <= 8)
    {
        InsertSort(array + left, right - left + 1);
    }
    else
    {
        // 按照基准值对array数组的 [left, right]区间中的元素进行划分
        int div = partion0(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div] 和 [div+1, right]
        // 递归排[left, div]
        QuickSort(array, left, div - 1);

        // 递归排[div+1, right]
        QuickSort(array, div + 1, right);
    }
}

1.3.前后指针法

1.3.1前后指针法思路解析

前后指针法演示动图：

cur一直在找小

prev有两种状态：

  1. 紧跟着cur.

  2. prev与cur间隔着比key大的值

    ** 当key在最右边时，**cur和prev从最左边为起点，如果值都比key小的话，cur和prev同时前进，prev找大，找到大停止，随后cur找小，找到小停止，交换cur和prev所指向的值，随后继续当cur到最右边key的位置时，停止前进，prev继续找大，找大停止后，prev和cur（key）交换,完成单趟排序，依次递归即可。

** 当key在最左边时，**prev=0,cur=1,如果值都比key小的话，cur和prev同时前进，prev找大，找到大停止，随后cur找小，找到小停止，交换cur和prev所指向的值，随后继续当cur到最右边key的位置时，停止前进，将prev指向的值和最左边key中的值交换即可。完成单趟排序，依次递归完成排序。

1.3.2前后指针法完整代码

key在最左边（最简洁的写法）：

int partion5(int* arr, int left, int right)
{
    int mid = mid_ThreeNum(arr, left, right);
    swap(&arr[mid], &arr[left]);
    int key = arr[left];

    int prev = left;//找大
    int cur = left+1;//找小

    while (cur <= right)
    {
        if (arr[cur] < key && ++prev != cur)
        {
            swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }
    swap(&arr[prev], &arr[left]);

    return prev;
}

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int array[], int left, int right)
 {
    
    if (right - left <= 8)
    {
        InsertSort(array + left, right - left + 1);
    }
    else
    {
        // 按照基准值对array数组的 [left, right]区间中的元素进行划分
        int div = partion0(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div] 和 [div+1, right]
        // 递归排[left, div]
        QuickSort(array, left, div - 1);

        // 递归排[div+1, right]
        QuickSort(array, div + 1, right);
    }
}

key在最右边（便于理解的写法）：

int partion4(int* arr, int left, int right)
{
    int mid = mid_ThreeNum(arr, left, right);
    swap(&arr[mid], &arr[right]);
    int key = arr[right];
    
    int prev = left;//找大
    int cur = left;//找小

    while (cur < right && prev < right)
    {
        //如果都小于key就一起走
        while (cur < right && prev < right && arr[cur] <= key && arr[prev] <= key)
        {
            cur++;
            prev++;
        }

        //cur先走
        while (arr[cur] > key && cur < right)//cur==right停止
        {
            cur++;
        }
        while (arr[prev] < key && prev < right)
        {
            prev++;
        }
        if(cur <= right && prev <= right )
            swap(&arr[prev], &arr[cur]);
    }

    return prev;
}

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int array[], int left, int right)
 {
    
    if (right - left <= 8)
    {
        InsertSort(array + left, right - left + 1);
    }
    else
    {
        // 按照基准值对array数组的 [left, right]区间中的元素进行划分
        int div = partion0(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div] 和 [div+1, right]
        // 递归排[left, div]
        QuickSort(array, left, div - 1);

        // 递归排[div+1, right]
        QuickSort(array, div + 1, right);
    }
}

3.快速排序非递归版

3.1.快速排序非递归版思路解析

  快速排序的非递归可以通过借助栈来实现：

(54条消息) 【数据结构】一起来学习栈吧~vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple/article/details/126162037?spm=1001.2014.3001.5502 单趟排序的基本思想还是不变的，重点是如何将递归拆解转换为循环，递归改非递归有一个诀窍就是看递归时函数栈帧中储存什么，那么非递归中的栈就保存什么。之前的递归，函数栈帧中存储的是形参，也就是left,right左右区间，所以在栈中存储左右区间下标即可。

  **注意：**在创建栈最后一定要记得销毁栈，小心内存泄漏。

3.2.快速排序非递归版完整代码

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
    Stack st;
    StackInit(&st);
    StackPush(&st, right);
    StackPush(&st, left);
    while (!StackEmpty(&st))
    {
        int left = StackTop(&st);
        StackPop(&st);
        int right = StackTop(&st);
        StackPop(&st);
        if (left < right)
        {
            int key = partion5(a, left, right);
            
            StackPush(&st, key - 1);
            StackPush(&st, left);
            StackPush(&st, right);
            StackPush(&st, key + 1);
        }
    }
    StackDestroy(&st);
}

最后

又是摆烂许久的重新回归，好久不见，这里是媛仔！最近我们这边疫情又变得严重了，返校之路遥遥无期啊……在家里还是太容易懈怠了，要加油！！希望这篇文章对你能够有所帮助哦！！还有中秋节快乐，记得吃月饼~

标签： 排序算法 算法 数据结构
本文转载自: https://blog.csdn.net/vpurple_/article/details/126788458
版权归原作者 vpurple__ 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】交换排序之冒泡排序与快速排序”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

泷羽sec-星光不负a-学习打卡-安全见闻(1)

Linux 经典面试八股文

docker 拉取MySQL8.0镜像以及安装

【PowerShell】如何使用Pester进行单元测试？

PyCharm中TensorFlow安装指南及.whl文件使用

移动UI：意见反馈设计的8大要点，让用户和产品畅快沟通。

git | 删除指定 commit

文章导航