クイックソート_C++実装

#include 
#include 
using namespace std;

/*
	#       ，            。
	#         ：
		  、  、  
*/


void QuickSort(int *A, int left, int right);
int Partition(int *A, int left, int right);
void swapValue(int &a, int &b);
int Randomized_Partition(int *A, int left, int right);

int main()
{
	int A[8] = { 2,8,7,1,3,5,6,4 };
	/*int A[16] = { 20,19,21,5,4,9,3,1,14,8,45,75,65,22,15,16 };*/
	QuickSort(A, 0, 7);
	for (int j = 0;j < 8;j++) {
		cout << A[j] << " ";
	}
	return 0;
}



void QuickSort(int *A, int left, int right) {
	if (left < right) {
		int qevt = Randomized_Partition(A, left, right);  //    ，       
		QuickSort(A, left, qevt - 1);  //        
		QuickSort(A, qevt + 1, right);  //        
	}
}

//VS               ，            。

void swapValue(int &a,int &b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}

//Partition                  
int Partition(int *A, int left, int right) {
	int x = A[right];
	int i = left - 1;
	for (int j = left;j < right;j++) {
		if (A[j] <= x) {
			i = i + 1;
			swapValue(A[i], A[j]);
		}
	}
	swapValue(A[i + 1], A[right]);
	return i + 1;
}

//            ：   /             
//    ：            Θ(nlgn)
int Randomized_Partition(int *A, int left, int right) {
	srand((int)time(NULL));
	int i = rand() % (right - left+1)+left;
	swapValue(A[i], A[right]);
	return Partition(A, left, right);
}

時間対価分析:最悪の場合:Θ(n²) 最良の状況:Θ(nlgn)