排序算法是算法的入门知识，在面试中经常被问到排序算法及相关的问题，因此在学习的同时做一次总结。欢迎访问作者的个人博客

冒泡排序

基本思想：是从左到右两两比较相邻数据，若反序则进行交换。第一轮比较从0~N-1；第二轮0~N-2……最后一轮比较0~1。

时间复杂度：O(n)~O(n^2)

C代码：

void bubble_sort(int a[], int N)
{
    for (int i=0; i<N-1; i++)
    {
        for (int j=0; j<N-1-i; j++)
        {
            if (a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

优化：设置标志位，若某一轮没有任何元素位置发生变化，则排序完成。

优化代码：

void bubble_sort(int a[], int N)
{
    int sort = 1;
    for(int i=0; i<N-1; i++)
    {
        for(int j=0; j<N-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                sort = 0;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        if(sort) break;
    }
}

选择排序

基本思路：在0~N-1选最小值放在0位置；在1~N-1选最小值放在1位置……在N-2~N-1选最小值放在N-2位置。

时间复杂度：O(n^2)

C代码：

void select_sort(int a[], int N)
{
    for(int i=0; i<N-2; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            if(a[i] > a[j])
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

插入排序

基本思路：先比较位置0、1两数，小值置左；再将位置2的数与已排好序的队列从右向左依次比较，小值置左；再将位置3的数与已排好序的队列从右向左依次比较，小值置左……最后将位置N-1的数与已排好序的队列从右向左依次比较，小值置左。

时间复杂度：O(n^2)

C代码：

void insert_sort(int a[], int N)
{
    for(int i=0; i<N-1;i++)
    {
        for(int j=i+1; j>0; j--)
        {
            if(a[j-1] > a[j])
            {
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
}

同样可以设置标志位进行优化：

void insert_sort(int a[], int N)
{
    int sort = 1;
    for(int i=0; i<N-1;i++)
    {
        for(int j=i+1; j>0; j--)
        {
            if(a[j-1] > a[j])
            {
                sort = 0;
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
            if(sort) break;
        }
    }
}

结语

本篇文章总结了时间复杂度为O(n^2)的排序算法。如果对您有所帮助，欢迎对作者进行打赏，万分感谢！