网页爱好者

**////快速排序递归部分
    /**//**
        请不要直接使用这个方法,这个方是给Array_QuickSort设用的
        @param [in] aArray 要排序的数组
        @param [in] aLow 要排序低位下标
        @param [in] aHigh 要排序的高位下标
        @param [in] aCompare 元素比较的对象
     */
    template<class Array,class Compare>
    void __Array_QuickSort(Array & aArray,XInt aLow,XInt aHigh,const Compare & aCompare)
    ...{
        typedef typename Array::ElementType ElementType;
        XInt iTmpLow = aLow;
        XInt iTmpHigh = aHigh;
        while(iTmpLow < iTmpHigh)
        ...{
            ...{
                const ElementType & E = aArray[iTmpLow];
                while( iTmpLow < iTmpHigh && !aCompare(aArray[iTmpHigh],E) ) --iTmpHigh;
                if( iTmpLow < iTmpHigh ) aArray.Swap(iTmpLow,iTmpHigh);
            }
            ...{
                const ElementType & E = aArray[iTmpHigh];
                while( iTmpLow < iTmpHigh && !aCompare(E,aArray[iTmpLow]) ) ++ iTmpLow;
                if( iTmpLow < iTmpHigh ) aArray.Swap(iTmpLow,iTmpHigh);
            }
        }
        if( iTmpLow - 1 > aLow ) __Array_QuickSort(aArray,aLow,iTmpLow - 1,aCompare);
        if( iTmpLow + 1 < aHigh ) __Array_QuickSort(aArray,iTmpLow + 1,aHigh,aCompare);
    }
    /**////数组快速排序
    /**//**
        @param [in] aArray 要排序的数组
        @param [in] aCompare 元素比较的对象
     */
    template<class Array,class Compare>
    inline void Array_QuickSort(Array & aArray,const Compare & aCompare)
    ...{
        __Array_QuickSort(aArray,aArray.getFirstIndex(),aArray.getLastIndex(),aCompare);
    }
    /**////数组快速排序
    /**//**
        这里默认使用XFunctions_Less<>这个比较对象的实例
        @param [in] aArray 要排序的数组
     */
    template<class Array>
    inline void Array_QuickSort(Array & aArray)
    ...{
        __Array_QuickSort(aArray,aArray.getFirstIndex(),aArray.getLastIndex(),XFunctions_Less<Array::ElementType>());
    }
    /**////数组选择排序
    /**//**
        @param [in] aArray 要排序的数组
        @param [in] aCompare 元素比较的对象
     */
    template<class Array,class Compare>
    void Array_SelectSort(Array & aArray,const Compare & aCompare)
    ...{
        XInt iMaxIndex = aArray.getLastIndex();
        for(XInt i = aArray.getFirstIndex(); i < iMaxIndex; i++ )
        ...{
            XInt iMinValueIndex = i;
            for(XInt j = i + 1; j <= iMaxIndex; j++)
            ...{
                if( aCompare(aArray[j],aArray[iMinValueIndex])) iMinValueIndex = j;
            }
            if( iMinValueIndex != i ) aArray.Swap(i,iMinValueIndex);
        }
    }
    /**////数组选择排序
    /**//**
        这里默认使用XFunctions_Less<>这个比较对象的实例
        @param [in] aArray 要排序的数组
     */
    template<class Array>
    inline void Array_SelectSort(Array & aArray)
    ...{
        Array_SelectSort(aArray,XFunctions_Less<Array::ElementType>());
    }
    /**////数组冒泡排序
    /**//**
        @param [in] aArray 要排序的数组
        @param [in] aCompare 元素比较的对象
     */
    template<class Array,class Compare>
    void Array_BubbleSort(Array & aArray,const Compare & aCompare)
    ...{
        XInt iMaxIndex = aArray.getLastIndex();
        for(XInt i = aArray.getLastIndex(); i>0; i--)
        ...{
            bool bNotChange = true;
            for(XInt j = 0; j<i; j++)
            ...{
                if( aCompare(aArray[j+1],aArray[j]) ) 
                ...{
                    aArray.Swap(j,j+1);
                    bNotChange = false;
                }
            }
            if( bNotChange ) break; //如果没有发生交换,表示这个数组是有序的,则直接退出
        }
    }
    /**////数组冒泡排序
    /**//**
        这里默认使用XFunctions_Less<>这个比较对象的实例
        @param [in] aArray 要排序的数组
     */
    template<class Array>
    inline void Array_BubbleSort(Array & aArray)
    ...{
        Array_BubbleSort(aArray,XFunctions_Less<Array::ElementType>());
    }
    /**////查找数组指定元素的下标
    /**//**
        @param [in] aArray 要查找的数组
        @param [in] e 要查找的元素
        @param [in] aEqual 比较两个元素是否相等的对象
        @return 返回查找结果
            - ARRAY_INVALID_INDEX 表示数据未找到
            - 其它值 表示数据在数组中的下标
     */
    template<class Array,class E,class Compare>
    XInt Array_Find_Normal(const Array & aArray,const E & e,const Compare & aEqual)
    ...{
        XInt iMaxIndex = aArray.getLastIndex();    
        for(XInt i = 0; i<=iMaxIndex;  i++ )
        ...{
            if( aEqual(aArray[i],e) ) return i;
        }
        return ARRAY_INVALID_INDEX;
    }

    /**////查找数组指定元素的下标
    /**//**
        @param [in] aArray 要查找的数组
        @param [in] e 要查找的元素
        @return 返回查找结果
            - ARRAY_INVALID_INDEX 表示数据未找到
            - 其它值 表示数据在数组中的下标
     */
    template<class Array,class E>
    inline XInt Array_Find_Normal(const Array & aArray,const E & e)
    ...{
        return Array_Find_Normal(aArray,e,XFunctions_Equal<typename Array::ElementType>());
    }
    /**////二分查找数组指定元素的下标
    /**//**
        要求数组是一个有序的数组,并和Compare对应用的上
        @param [in] aArray 要查找的数组
        @param [in] e 要查找的元素
        @param [in] aEqual 比较两个元素是否相等的对象
        @return 返回查找结果
            - ARRAY_INVALID_INDEX 表示数据未找到
            - 其它值 表示数据在数组中的下标
     */
    template<class Array,class E,class Compare>
    XInt Array_Find_Binary(const Array & aArray,const E & e,const Compare & aCompare)
    ...{
        XInt Low = aArray.getFirstIndex(); 
        XInt High = aArray.getLastIndex();
        XInt Mid;
        XInt iRet = ARRAY_INVALID_INDEX;
        while( Low <= High )
        ...{
            Mid = (Low + High) /2;
            const Array::ElementType & Tmp = aArray[Mid];
            XInt CompareResult = aCompare(Tmp,e);
            if( CompareResult == 0 ) 
            ...{
                iRet = Mid;
                break;
            }
            else if( CompareResult > 0 ) High = Mid -1;
            else Low = Mid + 1;
        }
        return iRet;
    }
    /**////二分查找数组指定元素的下标
    /**//**
        要求数组是一个有序的数组,在这里默认使用的是XFunctions_Compare比较对象
        @param [in] aArray 要查找的数组
        @param [in] e 要查找的元素
        @return 返回查找结果
            - ARRAY_INVALID_INDEX 表示数据未找到
            - 其它值 表示数据在数组中的下标
     */
    template<class Array,class E>
    inline XInt Array_Find_Binary(const Array & aArray,const E & e) 
    ...{
        return Array_Find_Binary(aArray,e,XFunctions_Compare<const typename Array::ElementType>());
    }