排序算法之插入排序、希尔排序、归并排序(C#)

插入排序

两次for循环,外层从数组第二位i=1开始,内层for循环由i向前进行判断,大于则将该位置与遍历位置交换。此时注意,不能按i的位置获取元素,应将该元素暂存,因为交换时对应i位置元素值会变换。
插入排序动态演示
c#代码如下

		/// <summary>
        /// 插入排序
        /// </summary>
        /// <param name="array"></param>
        public int[] InsertSort(int[] array)
        {
            for (int i = 1; i < array.Length; i++)
            {
                int temp = array[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (temp > array[j])
                    {
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            return array;
        }

希尔排序

希尔排序是插入的变种,插入排序比较的相邻两个元素,而希尔排序则是先将数组基本排序后,在进行相邻遍历。引用菜鸟教程的话是:

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

希尔排序
C#代码如下

		/// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public int[] ShellSort(int[] array)
        {
            int gap = array.Length / 2;
            while (gap>=1)
            {
                for (int i = 0; i < array.Length; i++)
                {
                    for (int j = i + gap; j < array.Length && array[i] > array[j]; j+= gap)
                    {
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
                gap /= 2;
            }
            return array;
        }

归并排序

归并排序使用的是递归,将数组分成左右两个集合,递归直至左右集合只剩一个元素,将两个元素排序后向上返回。
归并排序
C#代码如下

		/// <summary>
        /// 归并排序
        /// </summary>
        /// <returns></returns>
        public int[] MergeSort(int[] array)
        {
            int length = array.Length;
            int half = length / 2;
            if (length <= 1)
            {
                return array;
            }
            //数组截取成左右两个
            int[] left = array.Take(half).ToArray();
            int[] right = array.Skip(half).ToArray();
            //递归 直至分成 左右两个只含一个元素时 排序后 向上返回
            left = MergeSort(left);
            right = MergeSort(right);
            return MergeSortDouble(left, right);
        }

        /// <summary>
        /// 对两个数组排序后合并成一个返回
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        public int[] MergeSortDouble(int[] left, int[] right)
        {
            List<int> li = new List<int>();
            int leftPositon = 0, rightPosition = 0;
            while (left.Count() > leftPositon && right.Count() > rightPosition)
            {
                if (left[leftPositon] > right[rightPosition])
                {
                    li.Add(right[rightPosition]);
                    rightPosition++;
                }
                else
                {
                    li.Add(left[leftPositon]);
                    leftPositon++;
                }
            }
            while (left.Count() > leftPositon)
            {
                li.Add(left[leftPositon]);
                leftPositon++;
            }
            while (right.Count() > rightPosition)
            {
                li.Add(right[rightPosition]);
                rightPosition++;
            }
            return li.ToArray();
        }

热门文章

暂无图片
编程学习 ·

连续子数组的最大和

一、问题描述 给定一个数组, 找出数组的一个连续子数组, 这个子数组的和最大; 遍历数组,将数组的值加入到sum中, 如果sum大于0, 继续遍历下一个数据, 如果sum小于等于0,说明前面的子数组是无用的,丢弃前面的数组,从下一个数组开始继续遍历; 二、连续子数组的最大和代…
暂无图片
编程学习 ·

js 的递归写法 代码的健壮性

这几天参加面试,有个关于递归的问题,之前学红皮书的手后,看过也写过代码,但是时间长了不用就会忘记,翻书肯定没有自己记住效率高;首先解释一下为什么这么写;//因为函数的本质是一个对象,fun是声明在栈内存中,其中保存一个地址,系统通过地址可以在堆中找到一个Function的对象;fu…
暂无图片
编程学习 ·

WEB安全的总结学习与心得(十一)——命令注入

WEB安全的总结学习与心得(十一) 01 命令注入之简介 类型:服务器端漏洞 02 命令注入的三个条件 1.调用可执行系统命令的函数 2.函数或函数的参数可控 3.拼接注入命令 03 命令注入的攻击过程 1.构造命令 2.拼接命令,执行注入的命令 3.结果回显
暂无图片
编程学习 ·

javaScript之ES6

ES6新增的内容 新增的let和constlet num1 = 10console.log(num1) //10const num2 = 10console.log(num2) //10let const声明变量和 var声明变量的区别:用let 和const 声明的变量不会进行预解析,只能先声明后使用 用let 和const 不能重复声明同一个变量 用let 和const声明 变…
暂无图片
中恒嘉业 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
cgfy ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
coreui ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

STL Practice —— 【map (1)】

Description 给出学生姓名和分数&#xff0c;要求你输入姓名查询分数。 Input 输入包含T组测试数据。 开头是一个正整数T (0<T<10)&#xff0c;为测试数据数量。 对于每组测试数据&#xff0c;第一行是一个正整数N (0<N<100000)。 接下来有N行&#xff0c;每行包…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
mfbz ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…