快速排序的几种优化

   排序是面试常考的的题，对于快速排序是对冒泡排序的一种改进。

   对于快排：我在这写了几种实现方法：

//1、快速排序一般

//排序思想：

//1.从数列中挑出一个元素，称为 “基准”（pivot），

//2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

//3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

    
int PartSort(int* a, int left, int right)
{
    int key = a[right];//找最右边一个为基准
    int begin = left;
     int end = right - 1;
  while (begin < end)
  {
       while (begin < end&&a[begin] <= key)//当找到大于基准数时停
        {
           ++begin;
         }
      while (begin < end&&a[end] >= key)//当找到小于基准数时停
     {
      --end;
     }
     if (begin < end)
       {
          swap(a[begin], a[end]);
        }
   }
    if (a[begin]>a[right])
   {
      swap(a[begin], a[right]);
      return begin;
    }
    else
    {
    return right;
     }
}
void QuickSort(int* a, int left, int right)
{
    assert(a);
     if (left >= right)
      return;
    int div = PartSort(a, left, right);//快排挖坑法
    QuickSort(a, left, div - 1);
    QuickSort(a, div + 1, right);
}

//2、挖坑法

//该方法的基本思想是：

//1．先从数列中取出一个数作为基准数。

//2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

//3．再对左右区间重复第二步，直到各区间只有一个数。

int PartSort1(int *a, int left, int right)
{
	assert(a);
	int key = a[right];
	while (left < right)
	{
		while (left < right && a[left] <= key)//从左向右找比key大的值
			left++;
		if (left < right)
		{
			a[right] = a[left];
			right--;
		}
		while (left < right && a[right] > key)//从右向左找比key小的值
			right--;
		if (left < right)
		{
			a[left] = a[right];
			left++;
		}
	}
	a[left] = key;
	return left;
}
void QuickSort1(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
	int div = PartSort1(a, left, right);//快排挖坑法
	QuickSort1(a, left, div - 1);
	QuickSort1(a, div + 1, right);
}

//3、三数取中

//引入的原因：

//虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n ^ 2），要缓解这种情况，就引入了三数取中选取枢轴

//分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N / 2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。

//事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数

int Midfind(int *a, int left, int right)
{
	int mid = left - (left - right) / 2;
	if (a[left] >= a[right])
	{
		if (a[right] > a[mid])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else  if (a[left] < a[mid])
	{
		return mid;
	}
	else
	{
		return left;
	}
}

void QuickSort2(int* a, int left, int right)//三数取中
{
	assert(a);
	if (left > right)
		return;
	int mid = Midfind(a, left, right);
	swap(a[mid], a[right]);
	int div = PartSort(a, left, right);
	QuickSort2(a, left, div - 1);
	QuickSort2(a, div + 1, right);
}

//4、单向

//设计思想：

//1.先从数列中取出一个数作为基准数key

//2.设计两个指针，cur，prev，cur开始指向首元素，next开始指向（即cur后一位）。

//3.若next大于key就与往最后交换  end左移

//4.若next小于key就交换cur。next

//5.等于key next就往后移

void  QuickSort3(int *a, int left, int right)//单向（排序）
{
	assert(a);
	if (left > right)
	{
		return;
	}
	int key = a[left];
	int cur = left;
	int next = left + 1;
	int end = right;
	while (next <= end)
	{
		if (a[next] > key)
		{
			swap(a[next], a[end]);
			end--;
		}
		else if (a[next] < key)
		{

			swap(a[cur], a[next]);  //一直交换 ，待cur左边都小于key，右边都大于key为止。
			cur++;
			next++;
		}
		else
		{
			next++;
		}
	}//此时next==end跳出循环
	QuickSort3(a, left, cur - 1);
	QuickSort3(a, end + 1, right);
}

//5、非递归形式(借助栈)

//设计思想：

//1、先进行部分排序分成两部分

//2、先压小再压大

//3、判断栈是否为空

//4、不为空，取栈顶（就是先取出一部分重复步骤2）；

//5、直到栈为空

int PartSort4(int* a, int left, int right)
{
	int key = a[right];//找最右边一个为基准
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		while (begin < end&&a[begin] <= key)//当找到大于基准数时停
		{
			++begin;
		}
		while (begin < end&&a[end] >= key)//当找到小于基准数时停
		{
			--end;
		}
		if (begin < end)
		{
			swap(a[begin], a[end]);
		}
	}
	if (a[begin]>a[right])
	{
		swap(a[begin], a[right]);
		return begin;
	}
	else
	{
		return right;
	}
}
void QuickSort4(int *a, int left, int right)
{
	
	stack<int> ch;
	if (left < right)
	{
		int mid = PartSort4(a, left, right);
		if (left < mid - 1)
		{
			ch.push(left);
			ch.push(mid - 1);
		}
		if (mid + 1 < right)
		{
			ch.push(mid + 1);
			ch.push(right);
		}
		while (!ch.empty())
		{
			int tmp = ch.top();
			ch.pop();
			int cur = ch.top();
			ch.pop();
			int mid = PartSort(a, cur, tmp);
			if (cur < mid - 1)
			{
				ch.push(cur);
				ch.push(mid - 1);
			}
			if (mid + 1 < tmp)
			{
				ch.push(mid + 1);
				ch.push(tmp);
			}
		}
	}
}