排序算法(一)

作者: Orient_ZY | 来源:发表于2018-04-09 11:24 被阅读2次

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

    冒泡排序

    基本思想:是从左到右两两比较相邻数据,若反序则进行交换。第一轮比较从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)的排序算法。如果对您有所帮助,欢迎对作者进行打赏,万分感谢!

    相关文章

      网友评论

        本文标题:排序算法(一)

        本文链接:https://www.haomeiwen.com/subject/ganbhftx.html