面试题快速排序 递归和非递归实现

 递归

void Recursion_sort(vector<int>& nums, int l, int r) {
	if (l + 1 >= r) {
		return;
	}
	int first = l, last = r - 1, temp = nums[first];//基准
	while (first < last) {
		while (first < last && temp <= nums[last]) {
			last--;
		}
		if (first < last)
		nums[first] = nums[last]; 
		while (first < last && temp >= nums[first]) {
			first++;
		}
		if(first < last)
		nums[last] = nums[first];
	}
	nums[first] = temp;
	Recursion_sort(nums, l, first);//区间 [0---mid]
	Recursion_sort(nums, first+1, r);//区间 [mid+1---size]
}

非递归

int Recursion_sort(vector<int>& nums, int l, int r) {
	if (l >= r) {
		return -1;
	}
	int first = l, last = r , temp = nums[first];//基准
	while (first < last) {
		while (first < last && temp <= nums[last]) {
			last--;
		}
		if (first < last)
		nums[first] = nums[last]; 
		while (first < last && temp >= nums[first]) {
			first++;
		}
		if(first < last)
		nums[last] = nums[first];
	}
	nums[first] = temp;
	return first;
}




void NRecursion_sort(vector<int>& nums) {
	stack<int>st;
	st.push(0), st.push(nums.size() - 1);
	while (!st.empty()) {
		int r = st.top();
		st.pop();
		int l = st.top();
		st.pop();
		int mid = Recursion_sort(nums,l, r);
		if (mid - 1 > l) {
			st.push(l), st.push(mid - 1);
		}
		if (mid + 1 < r) {
			st.push(mid+1), st.push(r);
		}
	}
}

测试：

int main()
{
	vector<int>nums={ 6,2,5,8,7,9,4,5,1,3,5,4,0 };
	for (auto c : nums) {
		cout << c << " ";
	}
	cout << endl;
	NRecursion_sort(nums);
	Recursion_sort(nums, 0, nums.size());
	for (auto c : nums) {
		cout << c << " ";
	}
return 0;
}