1. 冒泡排序

核心思想

从后往前每次将相邻元素比较、交换，直到所有元素有序

核心代码

//冒泡排序
void BubbleSort()
{
    int n=10;
    for (int i=0;i<n;i++)
    {
        int flag=0;
        for (int j=n-1;j>i;j--)
        {
            if (a[j]<a[j-1])
            {
                swap(&a[j],&a[j-1]);
                flag=1;
            }
        }
        if (flag==0) return;
    }
}

举例

5 4 7 3 6

第一趟：3 5 4 7 6

第二趟：3 4 5 6 7

排序完成

2.快速排序

核心思想

每次以第一个元素为中枢，两个指针，low指针指向第一个元素，high指针指向最后一个元素。从最后一个元素向前一直遍历，直到比中枢小，将这个元素移到low指针的位子上；然后将low指针向后遍历，直到比中枢大，最后当low>high的时候，low指针的位子就是中枢的最终位置。

核心代码

int Partition(int low,int high)
{
    int pivot=a[low];
    while (low<high)
    {
        while (low<high&&a[high]>=pivot) high--;
        a[low]=a[high];
        while (low<high&&a[low]<=pivot) low++;
        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
}
void QuickSort(int low,int high)
{
    if (low<high)
    {
        int pivotpos=Partition(low,high);
        QuickSort(low,pivotpos-1);
        QuickSort(pivotpos+1,high);
    }
}

举例

25 84 21 47 15 27 68 35 20

第一趟：20 15 21 25 47 27 68 35 84

第二趟：15 20 21 25 35 27 47 68 84

第三趟：15 20 21 25 27 35 47 68 84

特点

每趟的中枢左边元素都比它小，右边元素都比它大。

3.总结

稳定性

冒泡排序：稳定

快速排序：不稳定

效率

空间复杂度

冒泡排序：O（1）

快速排序：O（logn）

时间复杂度

冒泡排序：O（$n^2$）

快速排序：O（logn），最坏情况O（$n^2$）