寫教學的最大目的是教會未來的自己

C/C++ 排序快速寫法(quick sort) 同場加映binary search

今天在看維機百科時才發現的…..

這應該算是最佳解了 時間複雜度和merge sort相同,需要的buffer 更少

 

參考資料:http://www.cplusplus.com/reference/cstdlib/

 

首先

#include <stdlib.h>

 

再來要寫 比大小的function

static int cmp(const void *a, const void *b)
{
float t=*(float *)a – *(float *)b>0
if(t>0) return 1;
else if(t==0) return 0;
else return -1;
//    return *(int *)a – *(int *)b;
}

基本上input 和output 都規定好了 ,就是看你要怎麼比,上面有float 和int 版本,只要 >0 代表大於,=0 代表相同,<0代表小於 就可以了

 

最後使用

 

float arr[10]={5.2, 3.1, 7.7, 4.5, 1.2, 9.9, 9.9, 6.6, 2.2,10.1};

qsort(arr, 10, sizeof(float), cmp); //第一個參數放array 第二個放 有n個數 第三個是 每個數的大小 第四個就是比較的function

這樣 arr 就會自動排序了

剛好再C++ 的lib 看到 binary search

float key = 5.2;

float *pItem = (float*) bsearch (&key, arr, 10, sizeof (int), cmp);
cout << *pItem;

參數沒啥改變,再前面多了一個要找的值,就OK了,另外 如果沒找到 會噴NULL 喔 請注意

 

Post to Twitter Post to Plurk Post to Facebook Send Gmail

發表迴響

Copyright © 2024. All Rights Reserved.

歡迎光臨
初音