排序及二分查找

class Bubble   
{   
    //测试   
    public void test(int a)   
    {   
        a++;   
    }   
       
    //冒泡排序   
    public void sort(int arr[])   
    {   
        int temp=0;   
        //外层循环,决定一共走几趟   
        for(int i=0;i<arr.length-1;i++)   
        {   
            //内层循环，开始逐个比较，如果发现前一个数比后一个数大，则交换    
            for(int j=0;j<arr.length-1-i;j++)   
            {   
                if(arr[j]>arr[j+1])   
                {   
                    //换位   
                    temp=arr[j];   
                    arr[j]=arr[j+1];   
                    arr[j+1]=temp;   
                }   
            }   
        }   
    }   
}   
  
class Select   
{   
    //选择排序   
    public void sort(int arr[])   
    {   
        int temp=0;//临时变量   
        for(int j=0;j<arr.length-1;j++)   
        //j<arr.length说明当只剩最后一个数没比较时，不必再比较了   
        {   
            //假设第j个数是最小的数   
            int min=arr[j];   
            //记录最小数的下标   
            int minIndex=j;   
            for(int k=j+1;k<arr.length;k++)   
            //k<arr.length说明只剩两个数未比较时，最后一个数要参与比较   
            {   
                if(min>arr[k])   
                {   
                    //修改最小   
                    min=arr[k];   
                    minIndex=k;   
                }   
            }   
            //当退出内层for循环时，就找到这次的最小值   
            temp=arr[j];   
            arr[j]=arr[minIndex];   
            arr[minIndex]=temp;   
        }   
    }   
}   
  
//插入排序   
class InsertSort   
{   
    //插入排序方法   
    public void sort(int arr[])   
    {   
        for(int i=1;i<arr.length;i++)   
        {   
            int insertVal=arr[i];   
            //insertVal准备和前一个数比较   
            int index=i-1;   
            while(index>=0&&insertVal<arr[index])   
            {   
                //将把arr[index]向后移动一位   
                arr[index+1]=arr[index];   
                //让index向前移动   
                index--;   
            }   
            //将insertVal插入到行当 位置   
            arr[index+1]=insertVal;   
        }   
    }   
}   
  
//快速排序   
class QuickSort   
{   
    public void sort(int left,int right,int[] array)   
    {   
        int l=left;//左边   
        int r=right;//右边   
        int pivot=array[(left+right)/2];//中间的作为隔板数   
        int temp=0;   
        while(l<r)   
        {   
            while(array[l]<pivot) l++;   
            while(array[r]>pivot) r--;   
            if(l>=r) break;   
            temp=array[l];   
            array[l]=array[r];   
            array[r]=temp;   
               
            if(array[l]==pivot) --r;   
            if(array[r]==pivot) ++l;   
        }   
        if(l==r)   
        {   
            l++;   
            r--;   
        }   
        if(left<r) sort(left,r,array);   
        if(right>l) sort(l,right,array);            
    }   
}  

//二分查找   
class BinaryFind   
{   
    public void find(int leftIndex,int rightIndex,int val,int[] arr)   
    {   
        //首先找到中间的数   
        int midIndex=(rightIndex+leftIndex)/2;   
        int midVal=arr[midIndex];   
        if(rightIndex>=leftIndex)   
        {   
            //如果要找的数比midVal大   
            if(midVal>val)   
            {   
                //在arr的左边数中找   
                find(leftIndex,midIndex-1,val,arr);//递归   
            }   
            else if(midVal<val)   
            {   
                //在arr的右边的数找   
                find(midIndex+1,rightIndex,val,arr);//递归   
            }   
            else if(midVal==val)   
            {   
                System.out.println("找到下标"+midIndex);   
            }   
        }   
        else  
        {   
            System.out.println("没有找到！");   
        }   
    }   
}

#import <Foundation/Foundation.h>  
#import "Sort.h"  

#define kSize 20  
#define kMax 100  

int main (int argc, const char * argv[])  
{  

    // insert code here...  
    NSLog(@"Hello, World!");  

    NSMutableArray *data = [[NSMutableArray alloc] initWithCapacity:kSize];  

    for (int i =0;i<kSize;i++) {  
        u_int32_t x = arc4random() % kMax;//0~kMax  
        NSNumber *num = [[NSNumber alloc] initWithInt:x];  
        [data addObject:num];  
    }  

    NSLog(@"排序前的数据：%@",[data description]);  

    Sort *sort = [[Sort alloc] init];  
    [sort bunbleSortWithArray:data];  
    [sort selectSortWithArray:data];  
    [sort insertSortWithArray:data];  
    [sort quickSortWithArray:data];  
    return 0;  
}