数据结构 冒泡排序和快速排序

交换：根据数据之间的比较，把每个数据都放在自己应该的位置

（1）冒泡排序：通过不断的比较两个相邻的元素，若这两个元素是乱序的，则交换位置。从而实现每趟都把最大的数据交换到最后面

时间复杂度：O(n^2)
是否稳定：稳定
为就地排序
（2）快速排序：首先选定一个基准数（比较的标准），把比基准数x小的数据放在x前面，比基准数x大的数据放在后面。排好一趟后，x把序列划分为了两部分，这两部分还都是乱序的，再分别对这两部分进行快速排序。//递归

选择基准数（排序区间[l.r]）:理论上谁都可以
(1)选择排序区间第一个 a[l]----为例
    1.两个下标i=l,j=r;相对遍历
    2.先用j找一个比x小的数，放在i位置，i++
    3.再用i找一个比x大的数，放在j位置，j--
    4.不断循环，直到i==j为止，此时i/j位置就是x的位置
    5.然后再对x前后两个区域进行递归调用

(2)选择排序区间最后一个 a[r]
(3)选择排序区间中间位置 a[(l+r)/2]

时间复杂度：O(nlogn)
是否稳定：不稳定
为就地排序


#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
//left和right分别为排序区间范围
void Quick_Sort(vector<int>(&v), int left, int right)
{
    int i(left);
    int j(right);
    //递归出口,即排序区间只有一个元素时不进行排序
    if (left < right)
    {
        int x(v[i]);
        //排序
        while (i < j)
        {
            
            while (i < j && v[j] > x)
            {
                j--;
            }
            if (i < j)
            {
                v[i] = v[j];
                i++;
            }
            while (i < j && v[i] < x)
            {
                i++;
            }
            if (i < j)
            {
                v[j] = v[i];
                j--;
            }
        }
        v[i] = x;

        //递归调用，以v[i] = x为基准
        Quick_Sort(v, left, i - 1);
        Quick_Sort(v, i + 1, right);
    }
    //选取区间第一个作为基准数
}
void Quick_Sort_2(vector<int>(&v),int left,int right)
{
    int i(left);
    int j(right);
    //递归出口,即排序区间只有一个元素时不进行排序
    if (left < right)
    {
        int x(v[j]);
        //排序
        while (i < j)
        {
            while (i < j && v[i] < x)
            {
                i++;
            }
            if (i < j)
            {
                v[j] = v[i];
                j--;
            }
            while (i < j && v[j] > x)
            {
                j--;
            }
            if (i < j)
            {
                v[i] = v[j];
                i++;
            }
            
        }
        v[i] = x;

        //递归调用，以v[i] = x为基准
        Quick_Sort(v,left,i-1);
        Quick_Sort(v,i+1,right);
    }
    
    //选取区间最后一个作为基准数
}
void Bubble_Sort(vector<int>(&v))
{
    int tmp(0);
    //枚举趟数
    for (int i = 0; i < v.size() - 1; ++i)
    {
        //记录乱序区是否发生交换
        bool flag(false);
        //遍历乱序区
        for (int j = 0; j < v.size() - 1 - i; ++j)
        {
            if (v[j] > v[j + 1])
            {
                flag = true;
                tmp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = tmp;
            }
        }
        if (flag == false)
        {
            break;
        }
    }
}
int main()
{
    vector<int> v;
    int n(0);
    cin >> n;
    v.resize(n);
    for (auto& a : v)
    {
        cin >> a;
    }
    Quick_Sort_2(v,0,v.size()-1);
    for (auto a : v)
    {
        cout << a << ' ';
    }
    return 0;
}
/*
6
30
20
10
60
50
40
*/