ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【第四课】冒泡排序，快速排序(acwing-785) [打印本页]
作者: 大号在练葵花宝典    时间: 2025-1-18 02:18
标题: 【第四课】冒泡排序，快速排序(acwing-785)
目次
冒泡排序 
快速排序 
死循环问题：
基准元素的选择：
快排代码如下
递归时间复杂度：
空间暴力代码


冒泡排序 

由于之前学过冒泡排序，在没打仗快速排序算法之前这道题我就用冒泡做了。
  1. #include <iostream>
  2. using namespace std;
  3. const int N = 1e5 + 10;
  4. int a[N], n;
  5. void bubble(int a[], int n)
  6. {
  7.     int flag = 1;
  8.     for (int i = 0; i < n; i++) // 有n个数需要排序，所以需要n趟
  9.     {
  10.         flag=1;//注意每一趟开始之前要把flag置1，否则无法发挥它本身的作用
  11.         for (int j = 0; j < n - i - 1; j++) // 针对每一趟，都要进行n-i-1次比较
  12.         {
  13.             if (a[j] > a[j + 1])
  14.             {
  15.                 int tmp = a[j];
  16.                 a[j] = a[j + 1];
  17.                 a[j + 1] = tmp;
  18.                 flag = 0;
  19.             }
  20.         }
  21.         if (flag == 1)
  22.             break; // 倘若一个循环下来都没有交换数据说明本来这个序列就是有序的
  23.     }
  24. }
  25. int main()
  26. {
  27.     cin >> n;
  28.     for (int i = 0; i < n; i++)
  29.     {
  30.         cin >> a[i];
  31.     }
  32.     bubble(a, n);
  33.     for (int i = 0; i < n; i++)
  34.     {
  35.         cout << a[i] << " ";
  36.     }
  37.     return 0;
  38. }
复制代码
  简朴说一下冒泡排序的头脑：就是有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)。
举例：
一个长度为 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)，尤其是在数组已经逆序的情况下。
快排代码如下

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int N = 1e5 + 10;
  5. int a[N], n;
  6. void quicksort(int a[], int l, int r)
  7. {
  8.     if (l >= r)
  9.         return;
  10.     int x = a[l], i = l - 1, j = r + 1;
  11.     while (i < j)
  12.     {
  13.         do
  14.         {
  15.             i++;
  16.         } while (a[i] < x);
  17.         do
  18.         {
  19.             j--;
  20.         } while (a[j] > x);
  21.         if (i < j)
  22.             swap(a[i], a[j]);//引头文件algorithm
  23.     }
  24.     quicksort(a, l, j);
  25.     quicksort(a, j + 1, r);
  26. }
  27. int main()
  28. {
  29.     cin >> n;
  30.     for (int i = 0; i < n; i++)
  31.     {
  32.         cin >> a[i];
  33.     }
  34.     int l = 0, r = n - 1;
  35.     quicksort(a, l, r);
  36.     for (int i = 0; i < n; i++)
  37.     {
  38.         cout << a[i] << " ";
  39.     }
  40.     return 0;
  41. }
复制代码
递归时间复杂度：

在快速排序的每一轮中，都需要选取一个基准元素，然后将待排序序列中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边。这一步骤需要O(n)的时间复杂度。
由于函数中包含递归。我们就要补充一下，递归函数盘算时间复杂度的方法：

有点复杂。。。着实是暂时不太想了解了(doge) 
空间暴力代码

创建两个数组，一个数组p 放<x的数，一个数组q 放>x的数，然后再将 p q 数组归并到 a 数组，实现排序，在这个过程中实在也是需要递归的。
  1. #include<iostream>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int a[N],p[N],q[N];
  5. int n;
  6. void mysort(int a[],int l,int r)
  7. {
  8.     if(l>=r)return;
  9.     int x=a[l];
  10.     int j=0,k=0;
  11.     for(int i=l+1;i<=r;i++)//l+1是为了把基准数字排除出去
  12.     {
  13.         if(a[i]<=x)p[j++]=a[i];
  14.         else q[k++]=a[i];
  15.     }
  16.     for(int i=0;i<j;i++)
  17.     {
  18.         a[l+i]=p[i];//l + i 确保了这些元素被放置在从 l 开始的正确位置上
  19.     }
  20.     a[l+j]=x;//把基准元素插到二者之间
  21.     for(int i=0;i<k;i++)
  22.     {
  23.         a[l+j+1+i]=q[i];//l + j + 1 + i 确保了这些元素被放置在从 l + j + 1 开始的正确位置上。
  24.     }
  25.     mysort(a,l,l+j-1);//j 是 p 数组的长度，因此 l + j - 1 是 p 数组中最后一个元素的下标在原数组中的位置。
  26.     mysort(a,l+j+1,r);//l + j 是基准元素的位置，因此 l + j + 1 是右部分的第一个元素的下标在原数组中的位置
  27. }
  28. int main()
  29. {
  30.     cin>>n;
  31.     for(int i=0;i<n;i++)
  32.     {
  33.         cin>>a[i];
  34.     }
  35.     int l=0,r=n-1;
  36.     mysort(a,l,r);
  37.    
  38.     for(int i=0;i<n;i++)
  39.     {
  40.         cout<<a[i]<<" ";
  41.     }
  42.     return 0;
  43. }
复制代码
ok了，就先写到这里了。
有问题的话欢迎指出，非常感谢！！
也欢迎交流建议哦。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4