最近總是在想著煞肾，如何去設(shè)計(jì)，如何更好的編碼嗓袱，更充分地體會面向?qū)ο蟮乃枷爰龋部桃馔@方面去學(xué)習(xí)。寫了幾年代碼渠抹，也改總結(jié)總結(jié)蝙昙，發(fā)現(xiàn)最重要的還是在與思考闪萄。重溫了一下《程序設(shè)計(jì)實(shí)踐》這本書，進(jìn)一步規(guī)范反思下自己寫的代碼風(fēng)格奇颠、質(zhì)量败去、性能、可移植性等(想起來斯坦福教授講二分的時(shí)候直接撕字典了=>=)烈拒。對了數(shù)據(jù)結(jié)構(gòu)這方面的知識與算法進(jìn)一步鞏固圆裕。下面寫筆試經(jīng)常遇見的算法：二分法查找、快速排序算法荆几。實(shí)現(xiàn)算法其關(guān)鍵在于實(shí)現(xiàn)的思想吓妆。
（一）二分法查找
二分法查找其實(shí)就是折半查找，一種效率較高的查找方法吨铸。針對有需數(shù)組來查找的耿战。
主要思想是：（設(shè)查找的數(shù)組期間為array[low, high]）
（1）確定該期間的中間位置K
（2）將查找的值T與array[k]比較。若相等焊傅，查找成功返回此位置剂陡；否則確定新的查找區(qū)域，繼續(xù)二分查找狐胎。區(qū)域確定如下：
a.array[k]>T 由數(shù)組的有序性可知array[k,k+1,……,high]>T;故新的區(qū)間為array[low,……鸭栖，K-1]
b.array[k]
時(shí)間復(fù)雜度:O(log2n);
代碼實(shí)現(xiàn):
///
/// 二分法查找
///
/// 目標(biāo)數(shù)組(已經(jīng)排序好了)
/// 查找的數(shù)
/// 目標(biāo)數(shù)的索引
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;
}
（二）快速排序算法
快速排序是盡量避免額外計(jì)算的極好例子.其工作方式是在數(shù)組中劃分出小的和大的元素
基本思想是：
從數(shù)組中取出一個(gè)元素作為基準(zhǔn)值
把其他元素分為兩組：
“小的”是那些小于基準(zhǔn)值的元素。
“大的”是那些大于基準(zhǔn)值的元素握巢，
遞歸對這兩個(gè)組做排序晕鹊。
快速排序快速的原因在于：一旦知道了某個(gè)元素比基準(zhǔn)值小，它就不需要在與那些大的元素比較暴浦。而大的元素也不需要在與小的元素比較溅话，這個(gè)性質(zhì)使快速排序比簡單排序、冒泡排序快的多歌焦。
時(shí)間復(fù)雜度：O（nlogn）
代碼實(shí)現(xiàn)：
///
/// 快速排序
///
///
///
///
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);
}
///
/// 交換兩個(gè)值
///
///
///
///
private void Swap(int[] a,int i,int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
