【第四课】冒泡排序，快速排序(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)。

• 平衡划分：选择中间元素作为基准元素可以更有可能地将数组分成两个大致相等的子数组。如许可以镌汰递归调用的深度，使算法的效率更高。且假如每次划分都能将数组分成两个大致相等的子数组，递归树的高度将靠近 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)，尤其是在数组已经逆序的情况下。
快排代码如下

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企服之家，中国第一个企服评测及商务社交产业平台。