昨天搞了下二分查找，今天看看它的升级版：插值查找。 插值查找核心思想是尽量将中间值取的更靠近要查找的目标以减少运算次数，而非像二分法那样盲目的取中间值，即： {{mid=left+ \tfrac{(dst-arr[left])}{(arr[right]-arr[left])}*(right-left)}} 它的缺点与二分法类似,理想情况下时间复杂度为： {{O(log_2 N)}} int insert_search(int arr[], int dst, int left, int right) { int mid = left + (dst – (arr[left]) / (arr[right] – arr[left])) * (right – left); if (arr[mid] … “算法之简单的插值查找”

二分查找也成为折半查找，理想状态下的时间复杂度为： {{O(log_2 N)}} 之所以说是理想状态是因为此算法存在一个缺点，即查找对象必须是有序状态下的排列数据。 int binary_search(int arr[], int dst, int left, int right) { int mid = left + (right – left) / 2; if (arr[mid] == dst) return mid; else if (arr[mid] > dst) … “算法之简单的二分查找”

首先要说明的是快速排序是递归算法的一种，因此对于内存紧张的机器来说它并非是个好的选择。 而且快速排序是大规模递归的算法，因此它比大部分排序算法都要快一般用于数据个数比较多的情况。尽管可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。 快速排序是C.R.A.Hoare于1962年发明的一种划分交换排序，由于采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。 分治法的流程是： 1. 从数列中取出一个数作为基准数。 2. 排序过程中，把比基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3. 再对左右区间重复第二步，直到各区间只有一个数。 看起好像很简单，嗯，写起来也很简单。 void quicksort(int arr[],int left,int right){ if(left<right){ int idx=left, sec=right, tmp=arr[left]; while(idx<sec){ while(arr[sec]>=tmp) sec–; if(idx<sec) arr[idx++]=arr[sec]; while(idx<sec && arr[idx]<tmp) idx++; if(idx<sec) arr[sec–]=arr[idx]; } arr[idx] = … “算法之快排 Quick Sort”