renyuntao · November 17, 2015 01:02 · Nov 17, 2015
diff --git a/quicksort.cxx b/quicksort.cxx
@@ -0,0 +1,74 @@
+#include<iostream>
+#include<ctime>
+#include<random>
+using std::cout;
+using std::cin;
+using std::endl;
+
+int partition(int arr[],int low,int high)
+{
+	int i = low + 1;
+	int j = high;
+	int tmp = arr[low];
+	while(1)
+	{
+		while(j != low && arr[j] > tmp) --j;   //from right to left
+		while(i != high && arr[i] <= tmp) ++i;  //from left to right
+		if(i < j)
+		{
+			int t = arr[j];
+			arr[j] = arr[i];
+			arr[i] = t;
+		}
+		else
+			break;
+	}
+	return j;
+}
+
+void quicksort(int arr[],int low,int high)
+{
+	if(low < high)
+	{
+		int j = partition(arr,low,high);
+		int t = arr[j];
+		arr[j] = arr[low];
+		arr[low] = t;
+		if(low < j)
+			quicksort(arr,low,j-1);
+		if(high > j)
+			quicksort(arr,j+1,high);
+	}
+}
+
+void generateRandData(int *randArr,int size,int seed)
+{
+	std::uniform_int_distribution<unsigned> u(0,1000);
+	std::default_random_engine e(seed);
+	for(int i = 0; i < size; ++i)
+		randArr[i] = u(e);
+}
+
+
+int main()
+{
+	int *arr = new int[1000000];
+	int seed;
+	cout<<"Input seed:";
+	cin>>seed;
+
+	generateRandData(arr,1000000,seed);
+
+	//std::default_random_engine e(seed);
+	//std::uniform_int_distribution<unsigned> u(0,10000);
+	//for(int i = 0;i < 999999;++i)
+	//	arr[i] = u(e);
+
+
+	clock_t start = clock();
+	quicksort(arr,0,999999);
+	clock_t end = clock();
+	cout<<"time:"<<static_cast<float>(end-start)/CLOCKS_PER_SEC<<endl;
+	delete [] arr;
+	return 0;
+}