排序 （C语言代码）

解题思路:

注意事项:

参考代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000;

int a[maxn];
int n;

void swap(int a[], int i, int j){
	int temp;
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

int p[2];

void partation(int arr[], int L, int R){
	
	int less = L-1;
	int more = R;
	int cur = L;
	while(cur < more){
		if(arr[cur] < arr[R]) swap(arr, ++less, cur++);
		else if(arr[cur] > arr[R]) swap(arr, --more, cur);
		else cur++;
	}
	swap(arr, R, more);
	p[0] = less+1;
	p[1] = more;

}

//int partation(int arr[], int L, int R){
//	int less = L-1;
//	int more = R;
//	int cur = L;
//	while(cur < more){
//		if(arr[cur] < arr[R]) swap(arr, ++less, cur++);
//		else if(arr[cur] > arr[R]) swap(arr, --more, cur);
//		else cur++;
//	}
//	swap(arr, R, more);
//	return less+1;
//}

void quickSort(int arr[], int L, int R){
	if(L < R){
		partation(arr, L, R);
		quickSort(arr, L, p[0]-1);
		quickSort(arr, p[1]+1, R); 
	}
}

//void quickSort(int arr[], int L, int R){
//	if(L < R){
//		int pos = partation(arr, L, R);
//		quickSort(arr, L, pos-1);
//		quickSort(arr, pos+1, R); 
//	}
//}

int main(void){
	while(cin >> n){
		for(int i = 0; i < n; i++){
			cin >> a[i];
		} 
		quickSort(a, 0, n-1);
		for(int i = 0; i < n; i++){
			cout << a[i] << " ";
		}	
		cout << "\n";
	}	
	return 0;
}