Overview of sorting algorithm

The ten sorting algorithms can be divided into two categories:

  • Comparison sorting: by comparing to determine the relative order of elements, time complexity can not break O(Nlogn), also known as nonlinear time comparison sorting
  • Non-comparative sorting: it does not determine the relative order of elements by comparison. It can break through the lower bound of time based on comparison sorting and run in linear time. Therefore, it is also called linear time non-comparative sorting.

The text and images above are from [Ten Classic Sorting algorithms (GIF demo)] (www.cnblogs.com/onepixel/ar…)

1.1 Time Complexity

Two. Bubble sort

2.1 the thought

Compare neighboring elements from front to back, and if the order is from smallest to largest, place the largest number in the back row until the largest number is ranked last

In the figure above, there are six elements and it takes five comparisons to complete, with the number of comparisons being the data length – number of comparisons -1

2.2 Algorithm Steps

  • Compare two adjacent elements and swap them if they are in reverse order
  • Do this for each pair of adjacent elements, and when the comparison is complete the largest element will be the last
  • The best case is that the elements in the sequence are all in positive order and only need to compare n minus 1 times, and the worst case is that the elements in the sequence are all in reverse order
  • A stable sort
void bubbleSort(int a[],int len)
{
	int i = 0;
	int j = 0;
	int temp;

	for (i = 0; i < len - 1; i++)
	{
		for (j = 0; j < len - 1 -i; j++)// If the last number of rows is the maximum, there is no need to sort
		{
			if (a[j + 1] < a[j])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp; }}}}Copy the code

Code optimization, if there is no exchange in a certain sort, it means that this sort has sorted the data in good order, there is no need to conduct the next sort, just add a flag bit

void bubbleSort2(int a[], int len)
{
	int i = 0;
	int j = 0;
	int temp;
	bool flag = false;

	for (i = 0; i < len - 1; i++)
	{
		for (j = 0; j < len - 1 - i; j++)// If the last number of rows is the maximum, there is no need to sort
		{
			if (a[j + 1] < a[j])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = true; }}if(! flag)// Check whether flag is flase after a certain trip, indicating that no exchange occurs
		{
			break;// If no swap occurs during a certain sort, end the sort early}}}Copy the code

Quicksort

3.1 the thought

  • Select a base number from the data to be sorted
  • Sort the data smaller than the base number to the left and the data larger than the base number to the right
  • Through Step 2, the two parts in are sorted, and the sorting process is carried out recursively. Finally, the whole data becomes an ordered sequence

Think can be summarized as: excavation fill number + divide and conquer

3.2 partition method

Divide and conquer: Divide and conquer, by dividing a complex problem into several sub-problems, and then dividing the sub-problems into many similar smaller problems, until the sub-problems can be solved simply and directly. The solution of the original problem is the combination of the solutions of several sub-problems

3.3 example

So let’s take an example of how quicksort works, where the first element is the base number, where the red box is the pit that needs to be filled in, and the green box is the element that has been moved and assigned, okay

  • At the beginning: I = 0,j =7, base = array[0] = array[I] = 20, base = array[0] = array[I] = 20, in this case, start from the back to the left, that is, from j=7 to the left, each move j decreases by 1. When j= 6, If the condition is met, fill the value of array[6] directly to array[0] and move I to the right by one position, I ++.

The pseudocode is:

while (left < right && array[right] >= base)// Find a value smaller than the base number from right to left
{
	right--;
}

// Find a value less than the base number and fill it directly to the left position
if (left < right)
{
	array[left] = array[right];
	left++; // the left subscript is increased by 1 to move to the right
}
Copy the code

At this point the graph

  • The pit of array[0] is filled by array[6]. The pit of array[6] is filled by array[6] from left to right. The pit of array[6] is filled by a number greater than base. We then assign array[1] to array[6] and move j one position to the left, j–

The code is:

while (left < right && array[left] < base)// Find a value greater than the base number from left to right
{
	left++;
}

// Find a value greater than the base number and fill it directly with rigth's position
if (left < right)
{
	array[right] = array[left];
	right--; // The subscript of right is incremented by 1, that is, to move to the left
}
Copy the code

The picture at this time is:

  • The final diagram is

Then you only need to operate on the elements on either side of array[5]

The code for divide and conquer is

quickSort(array,left,left - 1);
quickSort(array,left + 1,right);
Copy the code

3.4 code for

void quickSort(int array[].int low, int high)
{
	if (low >= high)
	{
		return;
	}

	int left = low;
	int right = high;
	int base = array[left];

	while (left < right)
	{
		while (left < right && array[right] >= base)// Find a value smaller than the base number from right to left
		{
			right--;
		}

		// Find a value less than the base number and fill it directly to the left position
		if (left < right)
		{
			array[left] = array[right];
			left++; // the left subscript is increased by 1 to move to the right
		}

		while (left < right && array[left] < base)// Find a value greater than the base number from left to right
		{
			left++;
		}

		// Find a value greater than the base number and fill it directly with rigth's position
		if (left < right)
		{
			array[right] = array[left];
			right--; // Right subsets by 1 to move to the left
		}

		array[left] = base;// Fill the base number into the last pit
		quickSort(array, low, left - 1);
		quickSort(array, left + 1, high); }}Copy the code