資料結構之二分法查找、快速排序思想與實現

   最近總是在想著，如何去設計，如何更好的編碼，更充分地體會面向對象的思想，也刻意往這方面去學習。寫了幾年程式碼，也改總結總結，發現最重要的還是在與思考。重溫了一下《程式設計實踐》這本書，進一步規範反思下自己寫的程式碼風格、品質、效能、可移植性等。對了資料結構這方面的知識與演算法進一步鞏固。下面寫筆試常遇見的演算法：二分法查找、快速排序演算法。實現演算法其關鍵在於實現的思想。

（一）二分法查找
二分法查找其實就是折半查找，一種效率較高的查找方法。針對有需數組來查找的。
主要想法是：（設查找的數組期間為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]

時間複雜度:O(log2n);

程式碼實作:
        ///

       /// 目標陣列(已經排序好了)
        /// 找出的數
        /// (int[] array, int T)
        {
            int low, high, mid       high = array.Length - 1;
            while (low         ) / 2;
                                  low = mid + 1;
                }
                {
                    high = mid - 1;
         else 
{
                           return -1;
        }

（二）快速排序演算法
快速排序是盡量避免額外計算的絕佳範例.其運作方式是在陣列中分割出小的和大的元素
基本思想是：
從數組中取出一個元素作為基準值
把其他元素分為兩組：
「小的」是那些小於基準值的元素。
「大的」是那些大於基準值的元素，
遞歸對這兩組做排序。
快速排序快速的原因在於：一旦知道了某個元素比基準值小，它就不需要在與那些大的元素比較。而大的元素也不需要在與小的元素比較，這個性質使快速排序比簡單排序、冒泡排序快的多。

時間快速複雜度：O（nlogn）
程式碼實作：
        ///

        /// 排序  y">
        ///
        ///
     {
            int last;
           if (left>=right)🎠      int rand = (left+right)/2;
            交換（陣列，左，蘭特）；
      + 1; i             {
                   Swap(array, ++last, i);
}
            交換（陣列，左，最後);
快速排序（數組，左，最後- 1）;
           快速排序（數組，最後+ 1，右）;
       
        ///

        / //
        /// ;
        /// Swap(int[] a,int i,int j)
        {
             int temp;
      a[i] = a[j];

            a[j] = temp;

        }







更多資料結構之二分法查找、快速排序思想與相關實際文章請關注PHP中文網！