快速排序 -

（类似于选择排序的定位思想）选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想，from up to down）

时间复杂度：O(NlogN) 　　稳定性：不稳定

快排C++实现

/*快排C++实现*/
void quickSort(vector<int> &arr, int bgn, int end)  //arr must be the reference of real param
{
    //数组arr空or仅有一个元素则退出
    if (bgn >= end - 1)
        return;

    int lindex = bgn;
    int rindex = end - 1;
    int std = arr[lindex];
    while (lindex < rindex)
    {
        while (lindex < rindex)
        {
            if (arr[rindex] < std)
            {
                arr[lindex++] = arr[rindex];
                break;
            }
            --rindex;
        }

        while (lindex < rindex)
        {
            if (arr[lindex] >= std)
            {
                arr[rindex--] = arr[lindex];
                break;
            }
            ++lindex;
        } 
    }

    arr[lindex] = std;
    quickSort(arr, bgn, lindex);
    quickSort(arr, rindex + 1, end);
}

快排C语言实现

int partition(int a[], int low, int high)
{
	int i = low, j = high + 1; //左右扫描指针
	int v = a[low];//切分元素
	int temp;
	while (true) //扫描左右，检查扫描是否结束并交换元素
	{
		while (a[++i] < v)
			if (i == high)
				break;
		while (v < a[--j]);
		if (i >= j)
			break;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	temp = a[low];
	a[low] = a[j];
	a[j] = temp;
	return j;
}

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