Browsed by
月份:2018年7月

希尔排序 Shell sort

希尔排序 Shell sort

我认为希尔排序的思想是比较另类的,属于插入排序的一个变种。由于插入排序在插入新数时需要遍历整个序列,希尔排序针对这种情况做出了修改:将整个序列分为几部分分别进行插入排序,而希尔排序的分组比较有意思,并不是像切肉一样简单分为几个连续的部分,而是设定了一个小于数组长度的跨度d(d通常小于数组长度/2),每隔d长度的为一组。假设共有10个数,d为3的情况,分组即为{0,3,6,9},{1,4,7},{2,5,8}这样三组。这一步的优点一是,由于每个子序列变短了,虽然总的需要排序的个数不变,但移动次数减少;优点二是可以将较小的数尽量快的放到整个数组的前面;例如按上面的分组第一次排序后,下标为0,1,2的元素均为个分组中最小的。然后将d缩短,即子序列变短,再对每部分进行插入排序,直到d=1时,无需排序,则完成整个序列的排序。 设定初始跨度d=array.length/2,相隔相同跨度的为一组,进行插入排序。 缩小跨度d,d=d/2,再此进行分组与插入排序。 d=1时结束。 int[] array = {6, 5, 3, 1, 8, 7, 2, 4}; int d = array.length; while (d > 1) { // 控制跨度 d = d / 2; // 每次跨度缩小一半 for (int start = 0; start < d; start++) { // 每个分组的起点 for (int currPos = start + d; currPos < array.lengt…

阅读全文 Read More

插入排序 Insertion sort

插入排序 Insertion sort

###这个原理应该是最简单的,即假定存在一个有序序列,将另一个数放入其中并保持最终的有序;在插入过程中为顺序扫描整个序列,当发现位置正确时进行插入。 例如手中有一副排好顺序的扑克,摸一张放里面,则需要挨个进行比较才能确定能放置的位置。 所以当数据结构为链表时操作比较简单,而为数组时则稍微复杂一些。下面以数组为例。 将数组分为两部分,前半部分是已排好的有序数组,后半部分都是待插入的数字;开始时前半部分只有序列的第一位,其余后面都是待插入的部分。 从第二位开始,将第二位的前一位,即第一位与当前位相比,如果比当前位大,则此比较位向后移,然后一直往前找,直到找到比当前位小的,则说明当前位应该放在比较位的后面。 然后再从当前位的下一位开始,再进行插入。 int[] array = {3, 5, 7, 4, 2, 1, 6}; for (int currPos = 1; currPos < array.length; currPos++) { // 从第二位开始,选取数字进行插入 int comparePos = currPos – 1; // 比较位是从前一位开始 int current = array[currPos]; while (comparePos >= 0 && array[comparePos] > current) { // 如果比较位比当前位大,则需要后移 array[comparePos + 1] = array[comparePos]; compareP…

阅读全文 Read More

冒泡排序 Bubble Sort

冒泡排序 Bubble Sort

先来一个最简单的,冒泡排序。顾名思义,就像水底往上冒的气泡,离水面越近,水泡越来越大。 从第一位开始,将其和它的下一个进行比对,如果前一个大,则交换位置;然后到第二位,就变为第二位与第三位比对,以此类推,两两比对完成后,就能保证最后一位为整个序列的最大。 然后再从第一位进行相邻的两两比对,这一次比对到倒数第二位即可,因为最后一位已经是最大,无需再比,则完成后,倒数第二位为整个序列的次大。 每次两两比对交换的终点位前移一次,则此算法终止与最终位为第二位时。 int[] array = {3, 5, 7, 4, 2, 1, 6}; for (int end = array.length – 1; end > 0; end–) { // 两两比对的终点控制 for (int index = 0; index < end; index++) { // 当前位控制 if (array[index] > array[index + 1]) { // 当前位与其下一位进行比对 int temp = array[index]; array[index] = array[index + 1]; array[index + 1] = temp; } } }

Material更新

Material更新

在上次说Material整体完工后,没想到官方再次更新,新增了3个组件的内容,分别是: Tree Badge Bottom Sheet 当然,还是能看出来是半成品,缺失了不少内容,不过好在也算是有了一个指导文档。 最近三个月由于有其他事情在忙,大家也能看出来文章数量的降低,关于网站维护以及文章发布等延迟了很多。好在快搞完了,预计8/9月应该能恢复正常。 被林同棪公司故意拖欠一笔款项高达7个月了。。。这公司大家一定要把他拉入黑名单