快速排序（QuickSort）

时间复杂度：最好情况O(nlogn)*，最坏 O(n^2)

• 算法思想

  
  转自《坐在马桶上看算法：快速排序》

• 最容易理解的写法

//快速排序
void quick_sort1(int s[],int low,int high)
{
    int i = low, j = high, x = s[low];//x存基准数
    
    if (low > high) {
        return;
    }//递归出口
    
    while (i<j) {
        while (i < j && s[j] >= x) // 从右向左找第一个小于等于x的数
            j--;
        
        while (i < j && s[i] <= x) // 从左向右找第一个大于等于x的数（一定要有等于，否则无法跳过第一个基准数）
            i++;
        
        if (i<j) {
            int temp = s[i];
            s[i] = s[j];
            s[j] = temp;//交换
        }
    }
    
    s[low] = s[i];
    s[i] = x;//一趟循环结束后，将基准数与s[i]交换
    
    quick_sort1(s, low, i-1); // 递归调用
    quick_sort1(s, i+1, high);
}

• 快速排序（分离出partition算法）

int partition(int s[],int low,int high) {
    int i = low,j = high,x = s[low];//x存基准数
    
    while (i<j) {
        while (i < j && s[j] >= x) // 从右向左找第一个小于等于x的数
            j--;
        
        while (i < j && s[i] <= x) // 从左向右找第一个大于等于x的数（一定要有等于，否则无法跳过第一个基准数）
            i++;
        
        if (i<j) {
            int temp = s[i];
            s[i] = s[j];
            s[j] = temp;//交换
        }
    }
    s[low] = s[i];
    s[i] = x;//将基准数与s[i]交换
    
    return i;//返回基准数所在数组位置的下标
}

void quick_sort(int s[],int low,int high) {
    if (low < high) {
        int i = partition(s, low, high);//记下基准位置，在把其左右两边递归
        quick_sort(s, low, i-1);
        quick_sort(s, i+1, high);
    }
}

• 最简单的写法

//快速排序
void quick_sort_up2(int s[],int low,int high)
{
    if (low < high) {
        //Swap(s[low], s[(low + high) / 2]); //将中间的这个数和第一个数交换
        int i = low, j = high, x = s[low];
        while (i<j) {
            while (i<j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if (i < j)
                s[i++] = s[j];
            
            while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;
            if (i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort_up2(s, low, i-1); // 递归调用
        quick_sort_up2(s, i+1, high);
    }
}

二分查找(折半查找,Binary Search)

时间复杂度O(log2n)

• 算法思想

(1)首先确定整个查找区间的中间位置mid=(low+high)/2;

(2)用待查关键字值与中间位置关键字值进行比较；

若相等，则查找成功；

若大于，则在后半个区域中继续进行折半查找。

若小于，则在前半个区域中继续进行折半查找。

查找成功，返回关键字所在数组下标，没找到返回-1；

• 用递归实现

/**
 * 递归方法实现二分查找法.
 * @param Array数组
 * @param low 数组第一位置
 * @param high 最高
 * @param key 要查找的值.
 * @return 返回值.
 */
int BinarySearch(int Array[],int low,int high,int key)
{
    if (low<=high) {
        int mid = (low+high)/2;
        if(key == Array[mid])
            return mid;//递归出口
        else if(key < Array[mid])//移动low和high
            return BinarySearch(Array,low,mid-1,key);//key在左半边
        else if(key > Array[mid])
            return BinarySearch(Array,mid+1,high,key);//key在右半边
    }
    return -1;
}

• 非递归实现

//二分查找非递归方式
int HalfSearch(int a[],int low,int high,int key)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;//二分点
        if(a[mid]==key) return mid;
        else if(a[mid]<key) low=mid+1;
        else high=mid-1;
    }
    return -1;
}

and so on...