快速排序

快速排序，纵观各类技术博客，关于快速排序，方法很多，各有千秋，但是，我拙见：

快速排序需要用递归，二分，分治的思想去操作，那么在这其中，就需要找一个基准，通过这个基准，把序列分开，达到可以用分治的思想取解决的目的；

能看到这里的，基本对快排都有个了解，不多说，盗了几个图看看，更方便记忆：

    

动态图只能理解个意思，主要还是理解第一张图，说的很明白了，结合代码，分析：

#pragma once

//方法一：
void swap(int* a, int left, int right)
{
	int temp = a[left];
	a[left] = a[right];
	a[right] = temp;
}

int partitionNumOne(int* a, int left, int right)
{
	//The selected benchmark example :left
	int markKey = a[left];
	int mark = left;

	while (left < right)
	{
		while (left < right && a[right] >= markKey)
			right--;
		while (left < right && a[left] <= markKey)
			left++;
		swap(a, left, right);
	}

	swap(a,mark,left);
	return left; //or right because left == right
}

void QuickSortNumOne(int* a, int left, int right)
{
	if (left >= right)
		return;
	int position = partitionNumOne(a, left, right);
	QuickSortNumOne(a, left, position - 1);
	QuickSortNumOne(a, position + 1, right);
}

void SortNumOne(int* a,int size)
{
	assert(a);
	QuickSortNumOne(a, 0, size - 1);
}

//方法二：

int part(int* a, int left, int right)
{
	int markKey = a[left];
	
	while (left < right)
	{
		while (left < right && a[right] >= markKey)
			right--;
		a[left] = a[right];   //小的直接覆盖左边
		while (left < right && a[left] <= markKey)
			left++;
		a[right] = a[left];
	}
	
	a[left] = markKey;
	return left;
}

void QuickSortNumTwo(int* a, int left, int right)
{
	if (left >= right)
		return;

	int pos = part(a,left,right);
	QuickSortNumTwo(a,left,pos-1);
	QuickSortNumTwo(a,pos+1,right);
}

void SortNumTwo(int* a, int size)
{
	assert(a);

	QuickSortNumTwo(a,0,size-1);
}


//方法三：
//计算中间那个位置 一边都大于他 一边都小于他
int Partition(int *a, int left, int right)
{
	int key = a[right];
	int begin = left;
	int end = right - 1;

	while (begin < end)
	{

		//key是自己选
		while (a[begin] < key && begin < end) //也就是说 key左边的都比key小 右边的都比key大
		{
			++begin;
		}

		while (a[end] > key && end > begin)//处理右边
		{
			--end;
		}

		//但凡上边任何一个循环跳出来，都是因为遇到条件 下面判断
		if (begin < end)
		{
			swap(a[begin], a[end]);
		}
	}

	if (a[begin] < key)
	{
		return right;
	}

	else
	{
		swap(a[begin], a[right]);
		return begin;
	}
}

void QuickSortOne(int *a, int left, int right)
{
	assert(a);
	if (left <= right)
	{
		int tmp = Partition(a, left, right); //单趟排序
		QuickSortOne(a, left, tmp - 1);
		QuickSortOne(a, tmp + 1, right);
	}
}

//方法四：
void QsortMedianOfThree(int* a, int low, int high)
{
	if (low >= high) return;                        //递归出口
	PartitionMedianOfThree(a, low, high);         //三数取中
	int partition = Partition(a, low, high);      //将 >= x 的元素交换到右边区域，将 <= x 的元素交换到左边区域
	QsortMedianOfThree(a, low, partition - 1);
	QsortMedianOfThree(a, partition + 1, high);
}


// 三数取中确定基准元，将确定好的基准元与第一个数交换，无返回值
        
void PartitionMedianOfThree(int* a, int low, int high)
{
	int mid = low + (high + -low) / 2;
	if (a[mid] > a[high])
	{
		swap(a, mid, high);
	}
	if (a[low] > a[high])
	{
		swap(a, low, high);
	}
	if (a[mid] > a[low])
	{
		wap(a, mid, low);
	}                                                //将中间大小的数与第一个数交换
}

三种方法，都测试通过，前两种都是按图中方案写的代码，第二种方法优化了一点，不同第一种方法的地方是，第二种不用交换，直接覆盖，节省了时间；

之后：快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

附一张图：

赐教！