Simple and unpretentious, graphic quick sorting, multi-language realization. (PS: There is also treasure information)

I. Introduction

Quicksort is a kind of exchange sort , which was proposed by CAR Hoare in 1962.

Two, algorithm thinking

The basic idea of ​​quick sort is: divide the data to be sorted into two independent parts by sorting : the left side of the split point is smaller than it, and the right side is larger than it.

Then according to this method to quickly sort the two parts of the data, the entire sorting process can be recursively, in order to achieve the entire data into an ordered sequence.

Schematic diagram of dynamic effects:

Sort (4): Quick sort

Detailed illustrations are often more explanatory than a lot of text, so go directly to the picture:

Sort (4): Quick sort

In the figure above, the process of quick sort is demonstrated:

The initial state is a set of unordered arrays: 2, 4, 5, 1, 3.

After the above steps, the first sorting is completed , and new arrays are obtained: 1, 2, 5, 4, 3.

In the new array, with 2 as the dividing point, all numbers are smaller than 2 on the left and numbers larger than 2 on the right.

Because 2 has found a suitable position in the array, there is no need to move it.

The array on the left of 2 has only one element 1, so obviously there is no need to sort and the position is determined. (Note: In this case, the left pointer and the right pointer are obviously coincident. Therefore, in the code, we can set the judgment condition that left must be less than right . If it is not met, there is no need to sort ).

For the arrays 5, 4, and 3 on the right side of 2, set left to point to 5 and right to point to 3, and then continue to repeat steps one, two, three, and four in the figure to sort the new array.

1. Code


#include <iostream>#include <vector> using namespace std; int division(vector<int> &list, int left, int right){	// 以最左边的数(left)为基准	int base = list[left];	while (left < right) {		// 从序列右端开始,向左遍历,直到找到小于base的数		while (left < right && list[right] >= base)			right--;		// 找到了比base小的元素,将这个元素放到最左边的位置		list[left] = list[right]; 		// 从序列左端开始,向右遍历,直到找到大于base的数		while (left < right && list[left] <= base)			left++;		// 找到了比base大的元素,将这个元素放到最右边的位置		list[right] = list[left];	} 	// 最后将base放到left位置。此时,left位置的左侧数值应该都比left小;	// 而left位置的右侧数值应该都比left大。	list[left] = base;	return left;} // 快速排序void QuickSort(vector<int> &list, int left, int right){	// 左下标一定小于右下标,否则就越界了	if (left < right) {		// 对数组进行分割,取出下次分割的基准标号		int base = division(list, left, right); 		// 对“基准标号“左侧的一组数值进行递归的切割,以至于将这些数值完整的排序		QuickSort(list, left, base - 1); 		// 对“基准标号“右侧的一组数值进行递归的切割,以至于将这些数值完整的排序		QuickSort(list, base + 1, right);	}} void main(){	int arr[] = { 6, 4, 8, 9, 2, 3, 1 };	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));	cout << "排序前" << endl;	for (int i = 0; i < test.size(); i++){		cout << test[i] << " ";	}	cout << endl;	vector<int> result = test;	QuickSort(result, 0, result.size() - 1);	cout << "排序后" << endl;	for (int i = 0; i < result.size(); i++){		cout << result[i] << " ";	}	cout << endl;	system("pause");}

operation result:

Sort (4): Quick sort


# -*- coding:utf-8 -*- def QuickSort(input_list, left, right):	'''	函数说明:快速排序(升序)	Author:	Parameters:		input_list - 待排序列表	Returns:		无	'''		def division(input_list, left, right):		'''		函数说明:根据left和right进行一次扫描,重新找到基准数		Author:		Parameters:			input_list - 待排序列表			left - 左指针位置			right - 右指针位置		Returns:			left - 新的基准数位置		'''			base = input_list[left]		while left < right:			while left < right and input_list[right] >= base:				right -= 1			input_list[left] = input_list[right]			while left < right and input_list[left] <= base:				left += 1			input_list[right] = input_list[left]		input_list[left] = base		return left 	if left < right:		base_index = division(input_list, left, right)		QuickSort(input_list, left, base_index - 1)		QuickSort(input_list, base_index + 1, right) if __name__ == '__main__':	input_list = [6, 4, 8, 9, 2, 3, 1]	print('排序前:', input_list)	QuickSort(input_list, 0, len(input_list) - 1)	print('排序后:', input_list)

The result of the operation is the same as above.

Three, algorithm analysis

1. The performance of the quick sort algorithm

Sort (4): Quick sort

2. Time complexity

When the data is in order, it is divided into two subsequences based on the first keyword. The previous subsequence is empty, and the execution efficiency is the worst at this time.

When the data is randomly distributed, it is divided into two sub-sequences based on the first keyword, and the number of elements in the two sub-sequences is close to the same. At this time, the execution efficiency is the best.

Therefore, the more randomly distributed the data, the better the quick sort performance; the closer the data is to order, the worse the quick sort performance.

3. Time complexity

Quicksort requires 1 space to store the reference value during each division. The quick sort requires approximately logN split processing, so the space occupied is also logN.

4. Algorithm stability

In quick sort, equal elements may exchange order due to partitions, so it is an unstable algorithm.

Finally, I will give you a copy to help me get the data structure brushing notes of BAT and other major manufacturers' offers. It was written by a Google master. It is very useful for students with weak algorithms or in need of improvement:

Leetcode brushing notes from Google and Alibaba

And I have compiled the BAT algorithm engineer learning route, books + videos, complete learning route and instructions, which are definitely helpful for those who want to become an algorithm engineer (extraction code: jack):

How I became an algorithm engineer, super detailed learning route

For more exciting, please see here:

Quietly jointing, stunning all~