冒泡排序

1、算法思想

冒泡排序是一种简单的排序算法，通过循环遍历，将临近的两个元素进行比较，满足排序规则时，进行下一组元素对比，当不满足排序规则时，将两个元素交换位置，再继续进行下一组元素对比，确保最大的元素在一遍循环过后一定排在最后面，然后最后通过最多n2次循环对比，直到完全有序。

2、算法描述

（1）比较两个相邻的元素，如果第一个比第二个大，那么就交换他们的位置。

（2）重复步骤（1）的操作，依次比较两两相邻的两个元素。所有元素对比过后表示一次循环结束。

（3）至多循环n-1次，重复上面两个步骤。

（4）直到没有任何一组元素需要交换位置表示排序完成。

3、代码实现

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

void BubbleSort(int* slist,int length)
{
    int temp;
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (slist[j] > slist[j + 1])
            {
                temp = slist[j];
                slist[j] = slist[j + 1];
                slist[j + 1] = temp;
            }
        }
    }
}
int main()
{
    int sortlist[] = { 5,0,4,1,8,3,7 };
    BubbleSort(sortlist,7);
}

4、算法复杂度

最好的情况为正序，只需要一遍遍历，所以时间复杂度为O(n),最坏的情况为逆序，需要遍历n2次，所以时间复杂度为O(n2)。由于只有一个交换的变量temp需要内存，所以空间复杂度为O(1)。