快速排序

int partition(int arr[], int low, int high)
{
    // 分割元素
    int key = arr[low];
    
    // 从右边开始找比key小的元素
    while (low < high) {
        
        // 从右边找到一个比key小的元素
        if (arr[high] <= key) {
            // 把左边存放key的位置给找到的元素
            arr[low] = arr[high];
            // 左边指针右移一位
            low++;
            break;
        }
        
        // 如果没找到，一直往左找
        high --;
    }
    
    
    //从左边开始找比key大的元素
    while (low < high) {
        
        // 从左边找到一个比key大的元素
        if (arr[low] >= key) {
            // 把上一步找到的元素的位置给当前较小元素
            arr[high] = arr[low];
            // 右边指针左移一位
            high --;
            break;
        }
        
        // 如果没找到，一直往右找
        low++;
    }
    

/*
// 另一种循环
    for (; left < right; right--) {
        
        if (arr[right] <= key) {
            arr[left] = arr[right];
            left++;
            break;
        }
    }
    
    for (; left < right; left++) {
        if (arr[left] >= key) {
            arr[right] = arr[left];
            right--;
            break;
        }
    }
*/

    
    // 把较小元素的那个位置放回key元素
    arr[low] = key;
    
    return low;
}

void quick_sort(int arr[], int left, int right)
{
    if (left < right){
        
        int pos = partition(arr, left, right);
        
        // 分割元素的左边去排序
        quick_sort(arr,left,pos-1);
        
        // 分割元素的右边去排序
        quick_sort(arr,pos+1,right);
    }

}