注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ksnowlv的博客

积土成丘,集腋成裘,坚持再坚持!

 
 
 

日志

 
 

排序(插入,冒泡,交换,选择)&二分查找  

2013-05-15 10:35:13|  分类: 算法与数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOTICE:模板函数的声明和定义放到头文件中,

不然在调用模板函数时会出现如下问题。问题原因可以自己考虑下。


排序(插入,冒泡,交换,选择)二分查找 - ksnowlv - ksnowlv的博客

 核心点是:模板不支持分离编译。(当然,如果你仅仅是编译模板函数而不调用不会导致如上错误!注意前提条件)

/**交换T的值**/

template <typename T>

void swap(T* p, T* q)

{

    T tmp = *p;

    *p = *q;

    *q = tmp;

}


/**输出T数组中各个元素的值**/

template <typename T>

void showArray(const T* pArray,const int arrayLen)

{

    for (int i = 0; i < arrayLen; ++i) {

        printf("%d->",pArray[i]);

    }

    printf("end");

}


/**直接插入排序,时间复杂度,平方级,稳定排序**/

template <typename T>

void insertSort(T* pArray, const int arrayLen)

{

    T tmp;

    

    for (int i = 1; i < arrayLen; ++i) {

        

        tmp = pArray[i];

        int j = 0;

        

        for (j = i; j > 0; --j) {

            

            if (tmp < pArray[j - 1]) {

                pArray[j] = pArray[j - 1];

            }

            else

            {

                break;

            }

        }

        

        pArray[j] = tmp;

        

    }

}


/**冒泡排序,时间复杂度,平方级,稳定排序**/

template <typename T>

void bubbleSort(T* pArray, const int arrayLen)

{

    bool isExchanged = false;

    for (int i = arrayLen - 1; i >= 0; --i) {

        

        isExchanged = false;

        

        for (int j = 0 ; j < i; ++j) {

            if (pArray[j + 1] < pArray[j]) {

                swap(&pArray[j + 1], &pArray[j]);

                isExchanged = true;

            }

        }

        

        if (!isExchanged) {

            break;

        }

    }

}


/**交换排序**/

template <typename T>

void exchangeSort(T* pArray, const int arrayLen)

{

    for (int i = 0; i < arrayLen; ++i) {

        

        for (int j = i + 1; j < arrayLen; ++j) {

            

            if (pArray[j] < pArray[i]) {

                swap(&pArray[j], &pArray[i]);

            }

            

        }

        

    }

}


/**选择排序**/

template <typename T>

void selectSort(T* pArray, const int arrayLen)

{

    int smallIndex = 0;

    

    for (int i = 0; i < arrayLen; ++i) {

        

        smallIndex = i;

        

        for (int j = i + 1; j < arrayLen; ++j) {

            if (pArray[smallIndex] > pArray[j]) {

                smallIndex = j;

            }

        }

        

        if (i != smallIndex) {

            swap(&pArray[i], &pArray[smallIndex]);

        }

        

    }

}


template <typename T>

const int binaryFind(const T* pArray, const int arrayLen,const T value)

{

    int mid = 0;

    int low = 0;

    int high = arrayLen - 1;

    

    while (low <= high) {

        mid = low + (high - low)/2;

        

        if (pArray[mid] > value)

        {

            high = mid - 1;

        }

        else if (pArray[mid] < value)

        {

            low = mid + 1;

        }

        else if (pArray[mid] == value) {

            return mid;

        }

    }

    

    return -1;

}


调用CODE如下:

- (void)viewDidLoad

{

    [super viewDidLoad];

// Do any additional setup after loading the view, typically from a nib.

    

    const int  KArrayLength = 10;

    int  pArray[KArrayLength] = {22,34,89,0,3,81,99,23,1,10} ;

   

    showArray(pArray, KArrayLength);

    //insertSort(pArray, KArrayLength);

    //bubbleSort(pArray, KArrayLength);

    //selectSort(pArray, KArrayLength);

    exchangeSort(pArray, KArrayLength);

    printf("\n");

    showArray(pArray, KArrayLength);


    int index = binaryFind(pArray, KArrayLength, 81);

    printf("\nindex = %d\n",index);

    

    index = binaryFind(pArray, KArrayLength, 811);

    printf("index = %d",index);

}


执行结果如下:

22->34->89->0->3->81->99->23->1->10->end

0->1->3->10->22->23->34->81->89->99->end

index = 7

index = -1

  评论这张
 
阅读(291)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018