简单整理一下二分法查找、快速排序算法
（一）二分法查找二分法查找其实就是折半查找，一种效率较高的查找方法。针对有需数组来查找的。主要思想是：（设查找的数组期间为array[low, high]）（1）确定该期间的中间位置K（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。递归找，即可。
时间复杂度:O(log2n);
代码实现: /// <summary> /// 二分法查找 /// </summary> /// <param name="array">目标数组(已经排序好了)</param> /// <param name="a">查找的数</param> /// <returns>目标数的索引</returns> public int BinarySearch(int[] array, int T) { int low, high, mid; low = 0; high = array.Length - 1; while (low <= high) { mid = (low + high) / 2; if (array[mid] < T) { low = mid + 1; } else if (array[mid]>T) { high = mid - 1; } else { return mid; } } return -1; }
（二）快速排序算法快速排序是尽量避免额外计算的极好例子.其工作方式是在数组中划分出小的和大的元素基本思想是：从数组中取出一个元素作为基准值把其他元素分为两组：“小的”是那些小于基准值的元素。“大的”是那些大于基准值的元素，递归对这两个组做排序。快速排序快速的原因在于：一旦知道了某个元素比基准值小，它就不需要在与那些大的元素比较。而大的元素也不需要在与小的元素比较，这个性质使快速排序比简单排序、冒泡排序快的多。
时间复杂度：O（nlogn）代码实现： /// <summary> /// 快速排序 /// </summary> /// <param name="array"></param> /// <param name="left"></param> /// <param name="right"></param> public void QuickSort(int[] array,int left,int right) { int last; if (left>=right) return; int rand = (left+right)/2; Swap(array, left, rand); last = left; for (int i = left + 1; i <= right; i++) { if (array[i] < array[left]) Swap(array, ++last, i); } Swap(array, left, last); QuickSort(array, left, last - 1); QuickSort(array, last + 1, right); }
/// <summary> /// 交换两个值 /// </summary> /// <param name="a"></param> /// <param name="i"></param> /// <param name="j"></param> private void Swap(int[] a,int i,int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }
转载于:https://www.cnblogs.com/pengjuwang/p/6125065.html
