数据结构和算法学习--插值查找算法
数据结构和算法学习--插值查找算法（1）插值查找原理介绍：插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。（2）将折半查找中的求mid索引的公式，low表示左边索引left,hight表示右边索引right.key就是前面我们讲的findVal（3）int mid = low + (high - low) (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引*/ 对应前面的代码公式： int mid = left + (right – left) * (findVal – arr[left]) / (arr[righ...
数据结构和算法学习--二分查找算法
数据结构和算法学习--二分查找算法一、二分查找请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。二、二分查找算法的思路分析：1.首先确定该数组的中间的下标mid=(left+right)/22.然后让需要查找的数findVal和arr[mid]比较findVal>arr[mid]:说明你要查找的数在mid的右边，因此需要递归的向右查找findVal<arr[mid]:说明你要查找的数在mid的左边，因此需要递归的向左查找findVal==arr[mid]:说明...
数据结构和算法学习--常用排序算法总结和对比
数据结构和算法学习--常用排序算法总结和对比相关术语解释：1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；2)不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；3)内排序：所有排序操作都在内存中完成；4)外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；5)时间复杂度： 一个算法执行所耗费的时间。6)空间复杂度：运行完一个程序所需内存的大小。7)n: 数据规模8)k: “桶”的个数9)In-place: 不占用额外内存10)Out-place: 占用额外内存
数据结构和算法学习--基数排序
数据结构和算法学习--基数排序一、基数排序（桶排序）介绍（1）基数排序（radix sort）属于“分配式排序”(distribution sort),又称"桶子法"(bucket sort)或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法（3）基数排序(Radix Sort)是桶排序的扩展（4）基数排序是1887年赫尔曼.何乐礼发明的，它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。二、基数排序基本思想 将所有待比较数值统一为同...
数据结构和算法学习--快速排序
数据结构和算法学习--快速排序一、快速排序法介绍快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。二、快速排序法示意图三、快速排序法应用实例要求：对[-9,78,0,23,-567,70]进行从小到大的排序，要求使用快速排序法。【测试8w和800w】说明[验证分析]：（1）如果取消左右递归，结果是-9 -567 0 23 78 70（2）如果取消右递归，结果是 -567 -9 ...
数据结构和算法学习--归并排序
数据结构和算法学习--归并排序一、归并排序介绍归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）二、归并排序思想示意图1-基本思想三、归并排序思想示意图2-合并相邻有序子序列再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8...
数据结构和算法学习--希尔排序
数据结构和算法学习--希尔排序一、简单插入排序存在的问题我们看简单的插入排序可能存在的问题.数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：{2,3,4,5,6,6}{2,3,4,5,5,6}{2,3,4,4,5,6}{2,3,3,4,5,6}{2,2,3,4,5,6}{1,2,3,4,5,6}结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.二、希尔排序法介绍希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序...
数据结构和算法学习--插入排序
数据结构和算法学习--插入排序一、插入排序介绍插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。二、插入排序法思想插入排序(Insertion Sorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，元素表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。三、插入排序思路图四、插入排序法应用实例有一群小牛，考试成绩分别是101,34,119,1请从小到大排序代码public class...
数据结构和算法学习--选择排序
数据结构和算法学习--选择排序一、基本介绍选择排序属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。二、选择排序的思想选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1...
数据结构和算法学习--冒泡排序
数据结构和算法学习--冒泡排序一、基本介绍冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。优化：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。二、演示冒泡排序过程冒泡排序规则（1）一共进行数组的大小-1次大的循环（2）每一趟排序的次数在逐渐的减少（3）如果我们发现在某趟排序中，没有发生一次交换，可以提前...