快排的两种写法

快排方法一：

附：全代码实现

?

#include
  
   
#include
   
     using namespace std; int OnceSort(int *a, int left, int right) { int i = 0; int middle = right; right -= 1; while (left < right) { //left找大于middle的数 while (left < right && *(a + left) <= *(a + middle)) left++; //right找小于middle的数 while (left < right && *(a + right) > *(a + middle)) right--; if (left < right) { swap(*(a + left), *(a + right)); } else { break; } } if (*(a + left) < *(a + middle)) { i = left + 1; } else { i = left; } while (i < middle) { swap(*(a + middle - 1), *(a + middle)); middle--; } return i; } void QuickSort(int* a, int left, int right) { assert(a); int middle = 0; if (left < right) { middle = OnceSort(a, left, right); QuickSort(a, left, middle - 1); QuickSort(a, middle + 1, right); } } int main() { // int a[] = { 6, 5, 4, 1, 4, 2, 4, 3 }; int a[] = { 9, 9, 9, 7, 7, 7, 8, 8, 8, 3, 2, 1, 8, 6 }; QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1); return 0; }
   
  

快排方法二：

代码实现，下附：

?

#include
  
   
using namespace std;

int onceSort(int a[], int left, int right)
{
	int key = a[left];
	while (left < right)
	{
		while (left < right && (*(a + right) >= key))
		{
			right--;
		}
		if (left < right && (*(a + right) < key))
			swap(*(a + right), *(a + left));
		while (left < right && (*(a + left) < key))
		{
			left++;
		}
		if (left < right && (*(a + left) >= key))
			swap(*(a + left), *(a + right));
	}
	a[left] = key;
	return left;
}

void QuickSort(int a[], int left, int right)
{
	int middle = 0;
	if (left < right)
	{
		middle = onceSort(a, left, right);
		QuickSort(a, left, middle - 1);
		QuickSort(a, middle + 1, right);
	}
}

int main()
{
	int a[] = {2,1,4,3,8,7,5,6,4,4,4,4,4};
	QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	return 0;
}