程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 快速排序C++實現

快速排序C++實現

編輯:C++入門知識

快速排序C++實現


//快速排序
#include
#include
#include

using namespace std;

void qksort(int* arr, int cnt)
{
	function getPivot = [&](int* arr, int left, int right)->int
	{
		int mid = (left + right) / 2;
		if (arr[left] > arr[mid])
			swap(arr[left], arr[mid]);   
		if (arr[left] > arr[right])
			swap(arr[left], arr[right]);
		if (arr[mid] > arr[right])
			swap(arr[mid], arr[right]);
		swap(arr[mid], arr[right - 1]);
		return arr[right - 1];
	};

	function insertSort = [&](int* arr, int begin, int end)
	{
		int i = 0, j = 0;
		for (i = begin + 1; i <= end; i++)
		{
			int tmp = arr[i];
			for (j = i; j > begin && arr[j - 1] > tmp; j--)
				arr[j] = arr[j - 1];
			arr[j] = tmp;
		}
	};

	function qk = [&](int* arr, int left, int right)
	{
		if (left + 9 <= right)    //當數組元素大於等於10個的時候,我們用快速排序
		{
			int pivot = getPivot(arr, left, right);
			int i = left;
			int j = right - 1;
			while (1)
			{
				while (arr[++i] < pivot){}
				while (arr[--j] > pivot){}
				if (i < j)
					swap(arr[i], arr[j]);
				else
					break;
			}
			swap(arr[i], arr[right - 1]);
			qk(arr, left, i - 1);
			qk(arr, i + 1, right);
		}
		else                //當數組元素小於10個的時候我們用插入排序
			insertSort(arr, left, right);
	};

	qk(arr, 0, cnt - 1);
};

int main()
{
	int arr[1000];
	int tmp = -1;

	for (int i = 0; i < 500; i++)
	{
		if (i % 2)
			arr[i] = i*tmp;
		else
			arr[i] = i;
	}
	for (int i = 500; i < 1000; i++)
	{
		if (i % 2)
			arr[i] = i*tmp;
		else
			arr[i] = i;
	}

	//我們可以對上面進行全不快排還是部分快排部分插入排序進行時間上的測試,理論上我們元素個數界限是10個,取十個在有些時候不一定是最佳的,但是可以避免一些有害的特殊情形
	{
		LARGE_INTEGER  large_interger;
		double dff;
		__int64  c1, c2;
		QueryPerformanceFrequency(&large_interger);
		dff = large_interger.QuadPart;
		QueryPerformanceCounter(&large_interger);
		c1 = large_interger.QuadPart;

		qksort(arr, 1000);

		QueryPerformanceCounter(&large_interger);
		c2 = large_interger.QuadPart;
		printf("計時%lf毫秒\n", (c2 - c1) * 1000 / dff);
	}

	for (auto i : arr)
		cout << i << endl;

	cin.get();
	return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved