题解 | #排序#

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

// 插入排序
void InsertSort(int arr[], int len) {
	for (int i = 1; i < len; i++) {
		int tmp = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > tmp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = tmp;
	}
}

// 希尔排序
void ShellSort(int arr[], int len) {
	for (int step = len / 2; step >= 1; step /= 2) {
		for (int i = step; i < len; i++) {
			int tmp = arr[i];
			int j = i - step;
			while (j >= 0 && arr[j] > tmp) {
				arr[j + step] = arr[j];
				j -= step;
			}
			arr[j + step] = tmp;
		}
	}
}

// 冒泡排序
void BubbleSort(int arr[], int len) {
	int tmp;
	for (int i = 0; i < len - 1; i++) {
		bool flag = false;
		for (int j = len - 1; j > i; j--) {
			if (arr[j - 1] > arr[j]) {
				tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;
				flag = true;
			}
		}
		if (flag == false)
			return;
	}
}

// 快速排序
int partion(int arr[], int low, int high) {
	int pivot = arr[low];
	while (low < high) {
		while (low < high && arr[high] >= pivot) high--;
		arr[low] = arr[high];
		while (low < high && arr[low] <= pivot) low++;
		arr[high] = arr[low];
	}
	arr[low] = pivot;
	return low;
}

void quickSort(int arr[], int low, int high) {
	if (low < high) {
		int pivot = partion(arr, low, high);
		quickSort(arr, low, pivot - 1);
		quickSort(arr, pivot + 1, high);
	}
}

void QuickSort(int arr[], int len) {
	quickSort(arr, 0, len - 1);
}

// 选择排序
void SelectSort(int arr[], int len) {
	int min, tmp;
	for (int i = 0; i < len - 1; i++) {
		min = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[j] < arr[min])
				min = j;
		}
		tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
	}
}

// 堆排序
void heapAdjust(int arr[], int root, int len) {
	int tmp = arr[root];
	for (int i = (root + 1) * 2 - 1; i < len; i = (i + 1) * 2 - 1) {
		if (i < len - 1 && arr[i] < arr[i + 1])
			i++;
		if (tmp >= arr[i])
			break;
		else{
			arr[root] = arr[i];
			root = i;
		}
	}
	arr[root] = tmp;
}

void buildHeap(int arr[], int len) {
	for (int i = (len / 2) - 1; i >= 0; i--) {
		heapAdjust(arr, i, len);
	}
}

void HeapSort(int arr[], int len) {
	int tmp;
	buildHeap(arr, len);
	for (int i = len - 1; i > 0; i--) {
		tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		heapAdjust(arr, 0, i);
	}
}

// 归并排序
void merge(int arr[], int low, int mid, int high) {
	int* tmp = (int*)malloc((high - low + 1) * sizeof(int));
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high) {
		if (arr[i] <= arr[j]) 
			tmp[k++] = arr[i++];
		else
			tmp[k++] = arr[j++];
	}
	while (i <= mid) 
		tmp[k++] = arr[i++];
	while (j <= high) 
		tmp[k++] = arr[j++];
	for (i = low, k = 0; i <= high; i++, k++)
		arr[i] = tmp[k];
	free(tmp);
}

void mergeSort(int arr[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;
		mergeSort(arr, low, mid);
		mergeSort(arr, mid+1, high);
		merge(arr, low, mid, high);
	}
}

void MergeSort(int arr[], int len) {
	mergeSort(arr, 0, len - 1);
}

int arr[100];

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
		}
		QuickSort(arr, n);
// 		sort(arr, arr + n);
		for (int i = 0; i < n; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");
	}
	return 0;
}