当前位置：首页 > article >正文

【第四课】冒泡排序，快速排序(acwing-785)

article 2025/1/19 3:18:56

冒泡排序

快速排序

死循环问题：

基准元素的选择：

快排代码如下

递归时间复杂度：

空间暴力代码

冒泡排序

因为之前学过冒泡排序，在没接触快速排序算法之前这道题我就用冒泡做了。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void bubble(int a[], int n)
{
    int flag = 1;
    for (int i = 0; i < n; i++) // 有n个数需要排序，所以需要n趟
    {
        flag=1;//注意每一趟开始之前要把flag置1，否则无法发挥它本身的作用
        for (int j = 0; j < n - i - 1; j++) // 针对每一趟，都要进行n-i-1次比较
        {
            if (a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                flag = 0;
            }
        }
        if (flag == 1)
            break; // 倘若一个循环下来都没有交换数据说明本来这个序列就是有序的
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    bubble(a, n);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

简单说一下冒泡排序的思想：就是有n个元素就进行n趟，每一趟 从第一个元素从前到后把每两个相邻的元素进行大小比较，不符合条件(升/降)的两个元素值进行交换的过程。

比如这道题是要从小到大排序，那么代码中的外层循环就是需要遍历完数组的趟数(那自然是几个数排序就是几趟)，内层循环就是实现相邻两个数的比较了，比较的次数应该是n-i-1，这是因为有n个数的时候，相邻元素的比较次数只有n-1次(想一个例子，5个数的时候，相邻两个元素比较的话，是不是只有4次比较？)，然而每经过一趟就有一个数已经排好序了，所以需要再减去 i (已经经历的趟数)。

注：这里我多在循环开始前定义一个变量flag的目的是：在每一趟有数据进行交换的时候更改flag的值，如果某一趟结束之后都没有数据进行交换(也就是flag值没有更改)，说明整个序列已经是有序的了，就不需要再进行后面的几趟了，直接跳出循环。

冒泡排序的时间复杂度为 O(n^2)。

快速排序

为了寻找更为高效的排序算法，出现了快速排序。

快速排序的思想：①把已知区间(数组)分成两段，②让<x的数放在x的左边，>x的数放在x的右边，③继续不断地把已知的这两段区间分别再分成两个子区间 [这里是递归思想] 重复即可。

注意：当已知区间中只有一个元素(l=r)或者区间非法(l>r)时，直接return

①把已知区间分成两段 ，分的原则就是找出一个数记为x作为基准(这个数可以是a[l] a[r] a[mid] 还可以是数组中随机一个数这四种选择方式)。

②让<x的数在x的左边，>x的数在x的右边，如何实现这个操作就是我们快排算法的关键：定义两个变量 i j 作为指针，让 i 从数组左边开始扫描不符合 <x 这个条件的数，找到一个之后就停下；j 从数组右边向左扫描不符合 >x 这个条件的数，每找到一个之后停下。

这个操作代码如何实现呢？想让 i 不断地从左向右寻找，让 j 不断地从右向左寻找，每次比较完之后符合条件的就直接+1或-1即可，通过后置++/--实现。不符合条件的指针不是会停下么？当两个指针都停下的时候，同时满足 i j 并未相遇：即在满足i<j，且i j 又因为不满足我们的条件停了下来的时候，就将这两个数进行交换。

交换之后继续重复这个步骤进行判断，直到两个指针相遇时停止(由此得到循环出口条件)。

由于我们希望在第一次执行循环时就能够正确地移动(后置++/--) i 和 j 指针(数组下标实质意思就是指针)，因此我们需要将它们的初始值设为 l-1 和 r+1。

③继续不断地把已知的这两段区间分别分成两个子区间 [这里是递归思想] 重复即可。实现来说就是调用我们这个快排函数，调用的时候要注意l,r的值。由于我们是通过 i j 指针的位置来分段的，那么两个子区间的边界就通过 i j 的值来展现，当划分左半段的右边界时，用 i 表示就是 i-1，即【l,i-1】；用 j 表示是 j ，即【l,j】；当传递右半段的左边界时，用 i 表示就是 i，【i,r】；用 j 表示是 j +1，即【j+1,r】。

死循环问题：

如果把数组第一个元素a[l]作为基准，就不能在传递子区间边界的时候使用 i 的方式传递。

可视化：以x=a[l]为基准，且quicksort(a,l,i-1)，会出现什么问题？

一开始 i 指针指向的值是x，直接就不符合<x的条件，因此会停下不移动(即 i = l )，对于只有两个元素的数组来说，接下来就会退出循环，执行递归，那么递归时就要传递【l,i-1】，发生了什么，如果 i=l 那么 i-1<l 左边界大于右边界，直接return了；而右边的递归用了quicksort(a,i,r) i=l 导致区间并未改变，导致造成死循环。

同理如果当把数组中最后一个元素a[r]作为基准，就不能在传递子区间边界的时候使用 j 的方式传递。

可视化：以x=a[r]为基准，且 quicksort(a,l,j)，一开始 j 指针就要停下不移动(j=r)，对于只有两个元素的数组，执行递归左半边的时候，quicksort(a,l,j) j=r 造成区间未改变，死循环；递归右半边的时候，quicksort(a,j+1,r) j=r，左边界>右边界，直接return了。

基准元素的选择：

我们通常会选择数组的中间元素作为基准元素。这样可以保证算法的时间复杂度为 O(nlogn)。

平衡划分：选择中间元素作为基准元素可以更有可能地将数组分成两个大致相等的子数组。这样可以减少递归调用的深度，使算法的效率更高。且如果每次划分都能将数组分成两个大致相等的子数组，递归树的高度将接近 logn。每次递归调用都会将问题规模减半，这意味着在 logn 次递归调用后，问题规模可以被减小到 1。
避免最坏情况：在数组已经有序或逆序的情况下，选择第一个或最后一个元素作为基准元素会导致每次划分只减少一个元素，从而使时间复杂度退化为 O(n^2)。选择中间元素可以避免这种情况。

举例：

一个长度为 8 的数组 a = [8, 7, 6, 5, 4, 3, 2, 1]，选定右边界a[r]为基准元素。

移动指针 i 和 j。由于恰好所有元素都大于基准元素，所以指针 i 不会移动；指针 j 指向a[r]，因此j指针也会停下，二者交换，得到 [1, 7, 6, 5, 4, 3, 2, 8]，之后i指针移动到7停下，j指针会一直走到7的位置，因为中间这些元素都是>1的，这样二者指针相遇，此次循环结束。开始进行两个区间递归。

在这种情况下，由于每次划分只能减少一个元素，会导致快速排序的时间复杂度退化为 O(n^2)，尤其是在数组已经逆序的情况下。

快排代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void quicksort(int a[], int l, int r)
{
    if (l >= r)
        return;
    int x = a[l], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
        {
            i++;
        } while (a[i] < x);
        do
        {
            j--;
        } while (a[j] > x);
        if (i < j)
            swap(a[i], a[j]);//引头文件algorithm
    }
    quicksort(a, l, j);
    quicksort(a, j + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int l = 0, r = n - 1;
    quicksort(a, l, r);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

递归时间复杂度：

在快速排序的每一轮中，都需要选取一个基准元素，然后将待排序序列中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边。这一步骤需要O(n)的时间复杂度。

由于函数中包含递归。我们就要补充一下，递归函数计算时间复杂度的方法：

有点复杂。。。实在是暂时不太想了解了(doge)

空间暴力代码

创建两个数组，一个数组p 放<x的数，一个数组q 放>x的数，然后再将 p q 数组合并到 a 数组，实现排序，在这个过程中其实也是需要递归的。

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],p[N],q[N];
int n;
void mysort(int a[],int l,int r)
{
    if(l>=r)return;
    int x=a[l];
    int j=0,k=0;
    for(int i=l+1;i<=r;i++)//l+1是为了把基准数字排除出去
    {
        if(a[i]<=x)p[j++]=a[i];
        else q[k++]=a[i];
    }
    for(int i=0;i<j;i++)
    {
        a[l+i]=p[i];//l + i 确保了这些元素被放置在从 l 开始的正确位置上
    }
    a[l+j]=x;//把基准元素插到二者之间
    for(int i=0;i<k;i++)
    {
        a[l+j+1+i]=q[i];//l + j + 1 + i 确保了这些元素被放置在从 l + j + 1 开始的正确位置上。
    }
    mysort(a,l,l+j-1);//j 是 p 数组的长度，因此 l + j - 1 是 p 数组中最后一个元素的下标在原数组中的位置。
    mysort(a,l+j+1,r);//l + j 是基准元素的位置，因此 l + j + 1 是右部分的第一个元素的下标在原数组中的位置
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int l=0,r=n-1;
    mysort(a,l,r);
    
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

ok了，就先写到这里了。

有问题的话欢迎指出，非常感谢！！

也欢迎交流建议哦。

查看全文

http://www.kler.cn/a/508707.html