Browsed by
标签:算法

二分搜索 Binary search

二分搜索 Binary search

二分搜索也是比较常见的,在生活中的应用尤其广泛。比如在酒桌上玩猜数字,一个人坐庄先准备一个在一定范围内的数字,其余每个人轮流猜一次,庄说出是大了还是小了,说中的人喝。这个游戏玩过的人应该不少,其中肯定有许多人都是从中间开始猜,认为这样是比较快的排除方法。是的,这就是二分搜索。 二分搜索对于查找对象有要求,即有序。原理就是取其中间进行判断,如果未找到,则根据顺序关系再分别对两边其中的一个子区进行再次查找,直到找到或者未发现,搜索结束。 public static void main(String[] args) { int[] array = {1, 12, 13, 27, 34, 38, 49, 50, 64, 65, 76, 78, 97}; int target = 50; System.out.println(“result index:” + binarySearch(array, target)); } public static int binarySearch(int[] arr, int target) { int startPosition = 0; // 设置搜索的上下界 int endPosition = arr.length – 1; while (startPosition <= endPosition) { // 在搜索过程中,会逐渐缩小搜索范围 int midPosition = (startPosition + endPosition) / 2; // 确定中间…

阅读全文 Read More

顺序搜索 sequential search

顺序搜索 sequential search

顺序搜索是所有搜索算法中,最简单最无脑的,原理就是穷举,一个一个的比对,直到找到为止。所以对于被搜索的对象也没有任何要求,并不像其他的某些算法那样要求有序等等。 public static void main(String[] args) { int[] array = {49, 38, 65, 97, 76, 13, 27, 50, 78, 34, 12, 64, 1}; int target = 50; System.out.println(“result index:” + sequentialSearch(array, target)); } public static int sequentialSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { // 遍历整个数组 if (arr[i] == target) { // 如果找到,则返回对应的下标 return i; } } return -1; // -1表示未找到 }

快速排序 Quick Sort

快速排序 Quick Sort

快速排序也算是很出名的一种算法了,虽然说是不稳定的,但在各类面试笔试中出现的频率相当高。并且相较一些排序算法来说,快速排序的核心思路也比较简单: 挑选一个数target(一般为第一个),经过一次遍历比较后,将比此数小的,放在其前面,比此数大的,放在其后面。此数的前后序列都是无序的。此过程通常称为分区(partition)。其中交换的逻辑是比较重要的,具体为:有一个指针index指向第二个数,并且从第二个开始(第一个为target,不参与)遍历,如果比选定数小,则index后移,并且交换index与i;如果比选定数大,则直接进入下一次循环。 整个循环完成后,最后交换target与index。 则此被挑选的数的位置就确定了,然后再递归排序前后两个无序的数组即可。 int[] array = {49, 38, 65, 97, 76, 13, 27, 50, 78, 34, 12, 64, 1}; quickSort(array, 0, array.length – 1); static void quickSort(int[] array, int startPos, int endPos) { if (endPos > startPos) { // 设置终止条件 int target = array[startPos]; // 保存目标中间数 int index = startPos; // 设置索引位置 for (int i = startPos + 1; i <= endPos; i++…

阅读全文 Read More

归并排序 Merge sort

归并排序 Merge sort

归并排序相对于上两个的思路不同,并不是遍历单条序列找最大或最小的思路,最主要的是递归思想。假定有两个有序序列,将其合并为一个有序序列,所需要做的就是不断取出两个序列中最小的,并将其中较小的放在新的序列中,则最后合并得到的序列仍然是有序的序列,这就是所谓归并。 要归并排序一个序列,可以先将其分成两部分,分别进行排序,得到的就是两个有序序列,再按照如下步骤进行。 有两个指针分别指向两个有序序列的首位。 比较两个指针对应的大小,小的放入新序列,并且此指针向后移,再重复比较。 int[] array = {3, 5, 7, 4, 2, 1, 6}; mergeSort(array, 0, array.length – 1); // 指定排序范围 public static void mergeSort(int[] arr, int start, int end) { if (start == end – 1) { // 如果起始与终点相邻,则将两者进行比对 if (arr[start] > arr[end]) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } } else if (start < end – 1) { // 如果排序子集大于三个,则需要进行递归操作 int mid = (start + end) / 2; // 选取中间点 mergeSort(arr, start, mid); // 前半部分进行…

阅读全文 Read More

希尔排序 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; } } }

算法回顾

算法回顾

[toc] 三日不弹,手生荆棘 回顾是非常好的学习方法,让自己想起OI的时光。 排序 冒泡排序 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; } } } 插入排序 Insertion sort 这个原理应该是最简单的,即假定存在一个有序序列,将另一个数放入其中并保持最终的有序;在…

阅读全文 Read More