1.3 有效的方法找到数组的中值（面试题） 题目：假如有一个巨大的数组，如何用最有效的方法找到它的中值？ 中值的含义：如果有三个数1，2，10，那么中值是2。在很多场合，中值比平均值更有意义。...比如考察一个国家个人的收入。 “最有效”的含义：指时间上最快，而非最节省空间。 处理海量的数据，所使用的方法必须是最优化的，否则很轻易地就浪费掉上百倍资源。...至于那些大于中值的数字彼此的关系是什么，小于中值的数字相对的次序是什么，不用关心。 有经验的面试者：能否给点提示？ 在工作中，请求帮助永远比自己闷头做不出来要好。...证明为什么上述方法的计算复杂度只相当于把数组扫描几遍，最好的情况和最坏的情况会是什么样，什么时候会发生。 当数组特别特别大，以至于一台服务器都存不下了，应该怎么处理？...最后将 key 插入到数组中。
假设正在将一组数字按照升序排列，较大的值会浮动在数组的右侧，而较小的值则会浮动到数组的左侧。产生这种冒泡的现象是因为算法会多次在数组中移动过，比较相邻的数据，当左侧值大于右侧值的时候将它们互换。...如下图： 自底向上的归并排序算法的思想是将数组先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，以此类推，直到归并的长度大于整个数组的长度，此时整个数组有序。...顺序查找 对于查找数据来说，最简单的就是从列表中的第一个元素开始对列表元素逐个进行判断，直到找到了想要的元素，或者直到列表结尾也没有找到。这种方法称为顺序查找或者线性查找。...那么，有什么更加高效的查找方法嘛？这就是我们接下来要讲的了。 二分查找算法 在开始之前，我们来玩一个猜数字游戏： 规则：在数字1-100之间，你朋友选择要猜的数字之后，由你来猜数字。...那么二分查找的原理是什么呢？ 二分查找又称为折半查找，对有序的列表每次进行对半查找。就是这么简单@～@！
假设正在将一组数字按照升序排列，较大的值会浮动在数组的右侧，而较小的值则会浮动到数组的左侧。产生这种冒泡的现象是因为算法会多次在数组中移动过，比较相邻的数据，当左侧值大于右侧值的时候将它们互换。...如下图： merge-sort-demo1 自底向上的归并排序算法的思想是将数组先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，以此类推，直到归并的长度大于整个数组的长度，此时整个数组有序...顺序查找 对于查找数据来说，最简单的就是从列表中的第一个元素开始对列表元素逐个进行判断，直到找到了想要的元素，或者直到列表结尾也没有找到。这种方法称为顺序查找或者线性查找。...那么，有什么更加高效的查找方法嘛？这就是我们接下来要讲的了。 二分查找算法 在开始之前，我们来玩一个猜数字游戏： 规则：在数字1-100之间，你朋友选择要猜的数字之后，由你来猜数字。...那么二分查找的原理是什么呢？ 二分查找又称为折半查找，对有序的列表每次进行对半查找。就是这么简单@～@！
插入排序 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。...插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。...将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。...基数排序 vs 计数排序 vs 桶排序 基数排序有两种方法： 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异： 基数排序：根据键值的每位数字来分配桶； 计数排序：每个桶只存储单一键值； 桶排序
插入排序示意图 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。...算法步骤： 1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） ---- 算法二：希尔排序序 ?...希尔排序是基于插入排序的以下两点性质而提出改进方法的： - 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 - 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位...4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 ---- 算法五：归并排序 ? 归并排序示意图 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。
插入排序示意图 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。...算法步骤： 1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） 算法二 希尔排序 ? 希尔排序示意图 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。...希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位 希尔排序的基本思想是...4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 算法五 归并排序 ? 归并排序示意图 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。
当只有一个数时，则不需要选择了，因此需要n-1趟排序 代码实现要点：两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大值，随后与当前趟数组最后的一位元素交换 插入排序 思路：将一个元素插入到已有序的数组中...与有序的数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入。...递归支点后一个元素(i)到R元素 归并排序 学习归并排序的前提：需要了解递归 思路：将两个已排好序的数组合并成一个有序的数组。将元素分隔开来，看成是有序的数组，进行比较合并。...替换后会导致下面的子树发生了变化，因此同样需要进行比较，直至各个节点实现父>子这么一个条件 希尔排序 思路：希尔排序实质上就是插入排序的增强版，希尔排序将数组分隔成n组来进行插入排序，**直至该数组宏观上有序...基数排序(桶排序) 思路：基数排序(桶排序)：将数字切割成个、十、百、千位放入到不同的桶子里，放一次就按桶子顺序回收一次，直至最大位数的数字放完～那么该数组就有序了 代码实现：先找到数组的最大值，然后根据最大值
插入排序示意图 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。...算法步骤： 1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） 算法二：希尔排序 ? 希尔排序示意图 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。...希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位...4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 算法五：归并排序 ? 归并排序示意图 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。
插入排序示意图 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。...算法步骤： 1)将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2)从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。) 算法二：希尔排序 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。...希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 希尔排序的基本思想是...4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 算法五：归并排序 ? 归并排序示意图 归并排序(Mergesort)是建立在归并操作上的一种有效的排序算法。
算法一：插入排序 插入排序示意图 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 ...算法步骤： 1)将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2)从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。) 算法二：希尔排序 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。...希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 希尔排序的基本思想是...4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 算法五：归并排序 归并排序示意图 归并排序(Mergesort)是建立在归并操作上的一种有效的排序算法。
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。...算法步骤： 1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）点击这里了解常用的加密算法。 算法二：希尔排序 ?...希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位 希尔排序的基本思想是...：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。...即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： ?...两种多关键码排序方法： 多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法： 最高位优先(Most Significant Digit first)法，简称MSD...说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；...直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。 直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序 5）一般不使用或不直接使用传统的冒泡排序。
System.out.println("降序数组为：" + Arrays.toString(descendingSort)); } 3.插入排序 插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列...3.1 排序原理 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。...该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。...快速排序和归并排序是互补的： 归并排序 将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序; 快速排序 的方式则是当两个数组都有序时，整个数组自然就有序了。...插入排序： 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
1.排序的基本概念与分类 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中，排序是数据处理中非常基本且重要的操作，它可以帮助人们更有效地理解和分析数据。...这里的理牌方法，就是直接插入排序法。...将插入的数据依次往前比较，如果比前面的数字end大，则放在end后面 如果比前面的数字小，则让前面的数字往后移动，则这里用变量tmp存放要插入的值 前面的数字移动后，end减一，继续比较 这里还有一种情况...，end可能会变成-1，这意味着tmp比有序序列中所有现有的元素都要小，应该被放在整个序列的最开始位置。...：2, 5, 8 子序列3排序后：1, 4, 7 现在将排序后的子序列放回原数组中，数组变化为： 完成了一轮希尔排序，此时整个数组并不完全有序，但是已经比原始的数组更接近有序了。
: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。...即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。...两种多关键码排序方法： 多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法： 最高位优先(Most Significant Digit first)法，简称MSD...说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；...直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。 直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序 5）一般不使用或不直接使用传统的冒泡排序。
插入排序 简介 插入排序是一种最简单的排序方法，对于少量元素的排序，它是一个有效的算法。 复杂度与稳定性 ? 过程介绍 首先将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。...每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。 可以选择不同的方法在已经排好序数据表中寻找插入位置。...根据查找方法不同，有多种插入排序方法，下面要介绍的是直接插入排序。 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。...将红色的数据依次插入组成一个逐渐有序的数组 代码实现 void insert_sort(int a[],int n) { int i,j; //外层循环标识并决定待比较的数值 for...注：归并排序需要创建一个与原数组相同长度的数组来辅助排序 过程介绍 首先将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
针对第一个问题，我们可以采用类似于散列函数的方法，即通过某种转换方式将浮点数或者负数转换为正整数作为数组下标，然后按照从小到大或者从大到小输出，当然，这只是思想，我们要怎么去实现呢？...2、插入排序： 扑克牌都玩过吧，插入排序就像我们摸扑克牌一样，摸到一张扑克牌，我们就可以将它插入到对应位置，使得已经摸到的牌有序，插入排序正是这种思想：首先，把数组元素中的第一个元素看成是有序的，从第二个元素开始...，我们每次取出一个元素，并且将这个元素插入到相应位置，使得插入后的元素仍有序，直到所有元素都插入完成。...下面上代码： /* * 插入排序：先将数组第一个数字看成有序的，然后逐步将后面的数字插入到前面有序的数字中 */ #include using namespace std;...插入排序：O(n*n)，看具体的数字元素，有时候效率很高，有时候很低。 希尔排序 ：事件复杂度与 G 数组和具体的数字元素有关。 冒泡排序：看具体情况，一般是O(n*n)。
二、直接插入排序 直接插入排序是一种最简单的排序方法，时间复杂度O(n2)，实现方式是将一个记录插入到已经排序好的有序表，得到一个新的、记录数增加1的有序表。...插入排序的核心思想，即假设原数组的第0位至第i-1位都是有序排列的（如从小到大），当第i位出现顺序错误（如第i位的值小于第i-1位），则需要进行插入排序。...1、算法 直接插入排序经过以下几步： 1）按照待排序数组的顺序，从第二个数字开始，逐个数字与前一个数字进行比较。 2）假设当前的比较是从小到大的排序，数组arr。...方法是将arr[i]拎出来，从i-1直至0位置的值，逐个进行比较，当比较到第k位，arr[k]<arr[i]时，将arr[k+1]至arr[i-1]的至分别往后挪一位，挪到arr[k+2]至arr[i]...的位置，然后将原来的arr[i]的值插入至arr[k+1]处。
因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的. 因此希尔排序在时间效率上比前两种方法有较大提高。步长的选择是希尔排序的重要部分。...将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。 再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。 重复第二步，直到k=1执行简单插入排序。...第二次用第二个数字去和后面的每个数字比较，将晓得放到第二个位置，这样完成这一轮之后，第二个数就是最第二小的数。...， 即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程 用于大量数，很长的数进行排序时。...循环操作：从低位开始（我们采用LSD的方式），将所有元素对应该位的数字存到相应的桶子里去（对应二维数组的那一列）。
，快速排序，希尔排序，堆排序 稳定排序：冒泡排序，直接插入排序，归并排序，奇数排序 1、插入排序 将第一个和第二个元素排好序，然后将第3个元素插入到已经排好序的元素中，依次类推（插入排序最好的情况就是数组已经有序了...元素个数N，取奇数k=N/2，将下标差值为k的数分为一组（一组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为一组，构成有序序列，直到k=1，然后再进行直接插入排序...7、归并排序 将一个无序的数列一直一分为二，直到分到序列中只有一个数的时候，这个序列肯定是有序的，因为只有一个数，然后将两个只含有一个数字的序列合并为含有两个数字的有序序列，这样一直进行下去，最后就变成了一个大的有序数列...一、直接插入排序（Insertion Sort) 算法思想： 直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过...说明： 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）； 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
