剑指offer--快速排序递归实现，年龄排序O(N)实现，旋转数组最小值查找

快速排序的思想可以运用到很多情况，如，还可以用来实现，

1. 在长度为N的数组中，查找第K大的数字，

2.数组中出现次数超过一半的数字。

3.最小的K个数字。

等

快速排序算法的递归实现：
void swap(int *a,int *b)
{
    int c;
    c=*a;
    *a=*b;
    *b=c;
}

int Partition(int data[],int length,int start,int end){
    int i;
    i= RandomInRange(start,end);
    swap(&data[i],&data[end]);
    int small;//计数左侧的数据个数
    small = start-1;
    for(i=start;i<end;i++)
    {
        if(data[i]<data[end])
        {
            small++;
            if(small!=i)
                swap(&data[i],&data[small]);
        }

    }
    small++;
    swap(&data[end],&data[small]);
    return small;

}
void quickSort(int data[],int length,int start,int end)
{
    if(start==end) return;

    int index;
    index = Partition(data,length,start,end);
    if(index>start) quickSort(data,length,start,index-1);
    if(index<end) quickSort(data,length,index+1,end);
}


对公司员工的年龄排序，复杂度为N。
void sortAges(int ares[],int length)
{
    int i,j,index;
    int numOfAges[100]={0};

    if(ages==NULL) return;

    for(i=0;i<length;i++)
    {
        if(ages[i]>99||ages<0) throw new std::exception();
        numOfAges[ages[i]]++;
    }
    index = 0;
    for(i=0;i<100;i++)
    {
        for(j=0;j<numOfAges[i];j++)
        {
            ages[index++]=i;
        }

    }
}

面试题八：旋转数组的最小数字。

<pre name="code" class="objc">int MinInOrder(int numbers[],int index1,int index2){int result,i;result = numbers[index1];for(i=index1+1;i<=index2;i++){if(result>numbers[index1])result = numbers[index1];}return result;}int Min(int *numbers,int length){int index1 = 0;int index2 = length-1;int indexMid=0;if(numbers==NULL||length<=0) {throw new std::exception("invalid parameters.");}while(numbers[index1]>=numbers[index2]){if(index2-index1==1){indexMid=  index2;break;}indexMid=(index1+index2)/2;if(numbers[index1]==numbers[index2]&&numbers[index2]==numbers[indexMid])return MinInOrder(numbers,index1,index2);if(numbers[index1]<=numbers[indexMid])index1 = indexMid;else if(numbers[index2]>=numbers[indexMid])index2 = indexMid;}return numbers[indexMid];}