快速排序与二分查找

// BinarySearch.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

/*
/处理两数交换
*/
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}


//在数组a中，排序区间为[low, high]
int partition(int a[],int low, int high)
{
    int temp = a[high];//temp为基准值

    int middle = low;
    
    for(int j = low; j < high; j++)
    {
        if(a[j] < temp)
        {
            if(j != middle)
            {
                swap(a[middle],a[j]);
            }
            middle++;
        }
    }

    swap(a[high],a[middle]);

    return middle;
}


void QuickSort(int a[], int low, int high)
{
    if(low < high)
    {
        int q = partition(a, low, high);
        QuickSort(a, low, q-1);
        QuickSort(a, q+1, high);
    }
}

//二分折半查找，在长度为length的数组a中查找target，成功返回在数组
//中的位置，否则返回-1
int BinarySearch(int a[], int target, int length)
{
    int left = 0;
    int right = length -1;
    int middle;

    while(left < right) //迭代
    {
        middle = (left + right)/2;

        if(target == a[middle])
            return middle;

        else if(target > a[middle])
            left = middle + 1;

        else
            right = middle - 1;
    }

    return -1;
}

void PrintArray(int a[], int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    int test[] = {3,1,4,2,6,1,3,7,8,4,11,34,21,9,8,10};

    int length = sizeof(test)/sizeof(int);

    int target = 9;
    
    PrintArray(test,length);

    //快速排序
    QuickSort(test,0,length-1);
    
    PrintArray(test,length);

    int position = BinarySearch(test,target,length);

    if (position != -1)
    {
        printf("target position is %d.\n", position);
    }
    else
        printf("target was not found!\n");

    getchar();

    return 0;
}