交换排序(2)：冒泡，快速

冒泡

1.流程

2.//代码
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int array[8]={9,0,6,7,1,5,4,8};
    int temp=0;
    int n=sizeof(array)/sizeof(int); 
    for(int i=0;i<n;i++)//轮次比较 
    {
        cout<<"第"<<i+1<<"轮比较: ";

        for(int j=n-1;j>0;j--)
        {               
            if(array[j]<array[j-1]) 
            {
                swap(array[j],array[j-1]);
            }
        }

        for(int i=0;i<8;i++)
        {
            cout<<array[i]<<" ";
        }   
        cout<<endl; 
    } 
} 

3.性能分析：

快速

1.思想：
通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

每次寻找一个哨兵，一般是头部。定义每次的Low和High标签。
一轮循环后，将哨兵赋值给i=j处

2.代码：

#include<bits/stdc++.h>
using namespace std; 
// 简洁版
void quickSort(int array[], int low, int high) 
{
    // 将第一个元素作为哨兵
    int i=low, j=high, temp=array[low];
    //这一段必须有 
    if (low > high) {
        return;
    }

    /*******************************************/ 
    while (i != j) {
        // 从右往左找第一个小于哨兵的元素
        while (i < j && array[j] >= temp)
            j--; 
        if (j > i)array[i++] = array[j];


        // 从左往右找第一个大于哨兵的元素
        while (i < j && array[i] <= temp)
            i++;
        if (j > i) array[j--] = array[i];
    }
    /*******************************************/ 

    //输出 
    for(int i=0;i<8;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;

    //把哨兵放在 i == j 处
    array[i] = temp;
    quickSort(array, low, i - 1);
    quickSort(array, i + 1, high);
}
int main()
{
    int array[8]={5,0,6,7,1,9,4,8};
    quickSort(array, 0,7);//一般是首尾元素 
}
//下图红色矩形框是哨兵

3.性能