【循環搜尋法（使用衛兵）】

/*
循環搜尋法（使用衛兵） 
說明:
搜尋的目的，是在「已排序的資料」中尋找指定的資料，而當中循序搜尋是最基本的搜尋法，隻要從資料開頭尋找到最後，看看是
否找到資料即可。
解法:
初學者看到循序搜尋，多數都會使用以下的方式來進行搜尋：

while(i < MAX){
    if(number[i] == k){
        printf("找到指定值");
        break; 
    }
    i++;
}

這個方法基本上沒有錯，但是可以加以改善，可以利用設定衛兵的方式，省去if判斷式，衛兵通常設定在數列最後或是最前方，假設
設定在列前方好了（索引0的 位置），我們從數列後方向 前找，如果找到指定的資料時，其索引值不是0，表示在數列走訪完之前就
找到了，在程式的撰寫上，隻要使用一個while回圈就可 以了。下面的程式為了配合衛兵的設定，自行使用快速排序法先将産生的數
列排序，然後才進行搜尋 ，若隻是數字的話，通常您可以使用程式語言函式庫所提供的搜尋函式.
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 10
#define SWAP(x, y) {int t; t = x; x = y; y = t;}

int search(int []);
int partition(int [], int, int);
void quicksort(int [], int, int);

int main(void){
    int number[MAX+1] = {0};
    int i, find;
    
    srand(time(NULL));
    
    for(i = 1; i <= MAX; i++){
        number[i] = rand() % 100;
    }
    
    quicksort(number, 1, MAX);
    
    printf("數列：");
    for(i = 1; i <= MAX; i++){
        printf("%d ", number[i]);
    }
    
    printf("\n輸入搜尋值： ");
    scanf("%d", &number[0]);
    
    if(find = search(number)){
        printf("\n找到數值索引 %d ", find);
    }else{
        printf("\n找不到數值");
    }
    
    printf("\n");
    
    return 0;
}

int search(int number[]){
    int i, k;
    k = number[0];
    i = MAX;
    
    while(number[i--] != k);return i;
}

int partition(int number[], int left, int right){
    int i, j, s;
    
    s = number[right];
    i = left - 1;
    
    for(j = left; j < right; j++){
        if(number[j] <= s){
            i++;
            SWAP(number[i], number[j]); 
        }
    }
    
    SWAP(number[i+1], number[right]);
    return i+1;
}

void quicksort(int number[], int left, int right){
    int q;
    
    if(left < right){
        q = partition(number, left, right);
        quicksort(number, left, q-1);
        quicksort(number, q + 1, right);
    }
}      

運作結果：

轉載于:https://www.cnblogs.com/libra-yong/p/6390276.html