【洛谷】P1177 【模闆】快速排序 題解

題目描述

利用快速排序算法将讀入的N個數從小到大排序後輸出。

快速排序是資訊學競賽的必備算法之一。對于快速排序不是很了解的同學可以自行上網查詢相關資料，掌握後獨立完成。（C++選手請不要試圖使用

sort

• 普通快排方法二（逾時！！）：

#include <iostream>
using namespace std;
int L[100005];

void QSort(int L[], int left, int right)
{
	if (left >= right)	return;	//遞歸跳出條件
	int temp = L[left];	//采用最左邊的數作為支點
	int i = left, j = right;
	while (i < j)
	{
		while (i < j && L[j] >= temp)  j--;	//從右往左，大于等于支點的數跳過
		while (i < j && L[i] <= temp)	i++;  //從左往右，小于等于支點的數跳過
		if (i < j) {	//交換
			int t = L[i];
			L[i] = L[j];
			L[j] = t;
		}
	}
	//交換支點和i位置所在的數
	L[left] = L[i];
	L[i] = temp;

	QSort(L, left, i - 1);	//遞歸處理左邊的數
	QSort(L, i + 1, right);	//遞歸處理右邊的數
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &L[i]);
	QSort(L, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", L[i]);
	return 0;
}
           

• 優化後的快排（AC！！）：

主要思想：對于基本有序的大量資料，如果采用最左端的數作為支點，時間複雜度将退化為O(n^2)，是以優化思路就是采用中間位置的數作為支點。

#include <iostream>
using namespace std;
int L[100005];

void QSort(int L[], int left, int right)
{
	if (left > right)	return;		//遞歸跳出條件
	int temp = L[(left + right) / 2];	//采用中間位置的數作為支點
	int i = left, j = right;
	while (i <= j)
	{
		while (L[j] > temp)  j--;	//從右往左，大于支點的數跳過
		while (L[i] < temp)	i++;	//從左往右，小于支點的數跳過
		if (i <= j) {	//交換
			int t = L[i];
			L[i] = L[j];
			L[j] = t;
			i++;
			j--;
		}
	}
	//注意：此時j一定小于i
	QSort(L, left, j);	//遞歸處理左邊的數
	QSort(L, i, right);	//遞歸處理右邊的數
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &L[i]);
	QSort(L, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", L[i]);
	return 0;
}