排序算法 面试必备

void quick_sort(vector& nums, int l, int r)
{
	if (l + 1 > r)
		return ;
	int first = l, last = r - 1, key = nums[first];
	while (first < last) {
		while (first < last && key <= nums[last]) {
			last--;
		}
		nums[first] = nums[last];
		while (first < last && key >= nums[first]) {
			first++;
		}
		nums[last] = nums[first];
	}
	nums[first] = key;
	quick_sort(nums, l, first);
	quick_sort(nums, first+1, r);
}

void merge_sort(vector&nums, int l, int r, vector&temp){
	if (l+1 >=r)
		return;
	int m = (l + r) << 1;
	merge_sort(nums, l, m, temp);
	merge_sort(nums, m, r, temp);
	int p = l, q = m,i = l;
	while (p < m|| q < r) {
		if (q >= r || (p < m && nums[p] <= nums[q])) {
			temp[i++] = nums[p++];
		}
		else {
			temp[i++] = nums[q++];
		}
	}
	for (i = 1; i < r; i++) {
		nums[i] = temp[i];
	}
}

void insertion_sort(vector&nums, int n) {
	for (int i = 0; i < n; i++) {
		for (int j = i; j > 0; j--) {
			if (nums[j-1] > nums[j]) {
				swap(nums[j - 1], nums[j]);
			}
		}
	}
}

void select_sort(vector&nums, int n)
{
	int mid;
	for (int i = 0; i < n - 1; i++) {
		mid = i;
		for (int j = i + 1; j < n; j++) {
			if (nums[j] < nums[mid]) {
				mid = j;
			}
		}
		swap(nums[i],nums[mid]);
	}
}