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 喔 請注意
Leave a Reply