数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序)

注:排序后的结果可以从小到大,或者从大到小,这只是一个相反的处理而已,为方便起见,本文中的方法都是从小到大排序

1、直接插入排序(InsertOrder)

思路:从第二个元素开始向后遍历,检查本身(后面称之为tmp)与前面相邻元素的大小,如果发现前面的元素更大,则依次从近及远(即倒序遍历)检查前面的所有元素,将比自身元素大的元素依次后移,这样最终将得到一个空位,将tmp元素插在这个位置即可.

        /// <summary>
        /// 直接插入排序法
        /// </summary>
        /// <param name="lst"></param>
        static void InsertSort(int[] lst)
        {
            int _circleCount = 0;
            //外循环从第二个元素开始从前向后遍历
            for (int i = 1; i < lst.Length; i++)
            {
                _circleCount++;
                //Console.WriteLine("外循环i=" + i);
                //如果发现某元素比前一个元素小
                if (lst[i] < lst[i - 1])
                {
                    int tmp = lst[i];
                    int j = 0;
                    //则该元素前面的元素,从后到前遍历,依次后移,直接找到应该插入的空档在哪里(这样tmp元素就找到了自己的位置)
                    for (j = i - 1; j >= 0 && tmp < lst[j]; j--)
                    {
                        //如果发现有比tmp小的元素,则将元素后移一位(从而把自身空出来,形成一个空档,以方便如果前面还有更小的元素时,可以继续向后面的空档移动)
                        lst[j + 1] = lst[j];
                        _circleCount++;
                        //Console.WriteLine("内循环i=" + i + ",内循环j=" + j);
                    }
                    //Console.WriteLine("j={0}", j);
                    //运行到这里时,j已经是空档的前一个下标
                    lst[j + 1] = tmp;
                }
            }
            Console.WriteLine("InsertOrder共循环了{0}次", _circleCount);
        }

点评:最好情况下,如果所有元素(N个)已经排好序了,则外循环跑N-1次,内循环一次也进不了,即0次,时间复杂度为O(N);最坏情况下,所有元素反序,外循环N-1次,内循环为i(i从1到N-1),时间复杂度为O(N*N);所以元素越有序列,该方法效率越高,其时间复杂度从O(N)到O(N*N)之间,此外,该方法是一种稳定排序。(注:若数组中有相同值的元素时,经过某方法排序后,这二个相同值的元素先后顺序仍然不变,则称这种排序方法为稳定的,反之为不稳定排序方法)

2、冒泡排序法(BubbleSort)

思路:从最后一个元素开始向前遍历,依次检查本元素与前面相邻元素的大小,如果前面的元素更大,则交换位置,如此反复,直到把自己前移到合适的位置(即 相当于后面的元素,通过这种比较,按照从小到大将不断移动前面来,就象气泡从下面向上冒一样)

        /// <summary>
        /// 冒泡排序法
        /// </summary>
        /// <param name="lst"></param>
        static void BubbleSort(int[] lst)
        {
            int _circleCount = 0;//辅助用,可以去掉

            int tmp;
            for (int i = 0; i < lst.Length; i++)
            {
                for (int j = lst.Length - 2; j >= i; j--)
                {
                    if (lst[j + 1] < lst[j])
                    {
                        tmp = lst[j + 1];
                        lst[j + 1] = lst[j];
                        lst[j] = tmp;
                    }

                    _circleCount++;
                }
            }

            Console.WriteLine("BubbleOrder共循环了{0}次", _circleCount);
        }

点评:与插入排序法类似,最好情况是所有元素已经排好序,这样只跑外循环,内循环因为if判断不成立,直接退出;最坏情况是所有元素反序,外循环和内循环每次都要处理,因此时间复杂度跟插入排序法完全相同,同样这也是一种稳定排序。

3、简单选择排序法 (SimpleSelectOrder)

思路:先扫描整个数组,找出最小的元素,然后跟第一个元素交换(这样,第一个位置的元素就排好了),然后从第二个元素开始继续扫描,找到第二小的元素,跟第二个元素交换(这样,第二个位置的元素也排好了)...如此反复

        /// <summary>
        /// 简单选择排序法
        /// </summary>
        /// <param name="lst"></param>
        static void SimpleSelectSort(int[] lst)
        {
            int _circleCount = 0;//辅助用

            int tmp = 0;
            int t = 0;
            for (int i = 0; i < lst.Length; i++)
            {
                t = i;
                //内循环,找出最小的元素下标
                for (int j = i + 1; j < lst.Length; j++)
                {
                    if (lst[t] > lst[j])
                    {
                        t = j;
                    }
                    _circleCount++;
                }
                //将最小元素[下标为t]与元素i互换
                tmp = lst[i];
                lst[i] = lst[t];
                lst[t] = tmp;
            }
            Console.WriteLine("SimpleSelectSort共循环了{0}次", _circleCount);
        }

点评:跟冒泡法很类似,不过应该注意到,这里的元素交换操作是在内循环外,即不管如何这个交换操作是省不了的,所以其时间复杂度均为O(N*N),同样这也是一个稳定排序。

4、快速排序(QuickOrder)

思路:以数组中间的元素做为分界线(该元素称为支点),扫描其它元素,比支点小的放在左侧,比支点大的放在右侧,这样就把数组分成了二段(即做了一次粗放的大致排序),然后对每一段做同样的处理(即二段变四段,4段变8段...),直到最后每一段只有一个元素为止(没错,该方法是一个递归调用)

        /// <summary>   
        /// 快速排序   
        /// </summary>   
        /// <param name="arr">待排序数组</param>   
        /// <param name="left">数组第一个元素索引Index</param>   
        /// <param name="right">数组最后一个元素索引Index</param>   
        static void QuickSort(int[] arr, int left, int right)
        {
            //左边索引小于右边,则还未排序完成   
            if (left < right)
            {
                //取中间的元素作为比较基准,小于他的往左边移,大于他的往右边移   
                int middle = arr[(left + right) / 2];
                //因为while中要做++与--的操作,所以这里先将i,j各自换外扩张一位
                int i = left - 1;
                int j = right + 1;
                while (true)
                {
                    while (arr[++i] < middle) ;//如果前半部的元素值本身就比支点小,则直接跳过

                    while (arr[--j] > middle) ;//如果后半部的元素值本身就比支点大,则直接跳过

                    //因为前半段是向后遍历,而后半段是向前遍历,所以如果二者碰到了,
                    //则说明所有元素都被扫过了一遍,完成退出
                    if (i >= j) 
                    {
                        break;
                    }

                    //经过前面的处理后,如果发现有放错位置的元素,则将二者对换
                    int tmp = arr[i];
                    arr[j] = arr[i];
                    arr[i] = tmp;

                }

                //经过上面的while循环后,元素已被分成左右二段(左段小于支点,右段大于支点)

                //递归调用,处理左段
                QuickSort(arr, left, i - 1);

                //递归调用,处理右段
                QuickSort(arr, j + 1, right);
            }
        }

点评:每次从中间分成二段,然后再中分为二段,如此反复...这跟二叉树很相似(每次分段,相当于树中的某个节点分成二叉),最好情况下所有元素已经排好序,最终树的左右分支数大致相同(即左右分支长度大致相同),所以分解次数为树的高度log2N,而最坏情况下,所有元素反序,这时分解得到的树相当于一个单右支二叉树(即一个右分支超级长,没有左分支的怪树),即时间复杂度范围为nLog2N 至 N*N。此外,快速排序是一种不稳定的排序(从代码就能看出来,即使是二个相同值的节点,在分段过程中,也有可能被交换顺序)

本来想将堆排序与归并排序一起写在这篇文章里的,今天看了看堆排序,还有点小复杂,完全可以另起一篇详解原理了,下篇将专门学习堆排序及归并排序。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-796-Rotate String

28460
来自专栏Jackson0714

IL指令速查

36770
来自专栏Java架构师学习

为Java程序员金三银四精心挑选的五十道面试题与答案

1、面向对象的特征有哪些方面? 【基础】 答:面向对象的特征主要有以下几个方面: 1)抽象:抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地...

37160
来自专栏Linyb极客之路

简洁又快速地处理集合——Java8 Stream(下)

而 parallelStream() 是并行流方法,能够让数据集执行并行操作,后面会更详细地讲解

14.7K110
来自专栏java一日一条

(转)Java正则表达式入门

众所周知,在程序开发中,难免会遇到需要匹配、查找、替换、判断字符串的情况发生,而这些情况有时又比较复杂,如果用纯编码方式解决,往往会浪费程序员的时间及精力。因此...

10010
来自专栏每日一篇技术文章

Foundation-String

最近写完了Swift 3.0教程 ,在接下来这段时间,继续写Foundation 的教程,帮助大家更加深入,系统的学习Foundation 框架,可能会持续一段...

11010
来自专栏chenjx85的技术专栏

leetcode-686-Repeated String Match(重复多少次A能够找到B)

14930
来自专栏orientlu

读 《C Traps and Pitfalls》Record

单引号实际代表一个整数 双引号代表指向无名数组的起始字符的指针(字符结尾 0) 使用库函数计算得到的字符串长度不包括结尾的0!

12130
来自专栏java思维导图

MySQL函数及用法示例(收藏大全)

1、字符串函数 ascii(str) 返回字符串str的第一个字符的ascii值(str是空串时返回0) mysql> select ascii('2...

9930
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第3章 Python的数据结构、函数和文件3.1 数据结构和序列3.2 函数3.3 文件和操作系统3.4 结论

本章讨论Python的内置功能,这些功能本书会用到很多。虽然扩展库,比如pandas和Numpy,使处理大数据集很方便,但它们是和Python的内置数据处理工具...

48060

扫码关注云+社区

领取腾讯云代金券