Simple sorting algorithm

Today’s IT industry is not as easy to deal with as it used to be. There are too many employees, resulting in a surplus of junior programmers. This has also indirectly led to the company’s recruitment threshold becoming higher and higher, requiring programmers to master more and more knowledge. more.

#Algorithms are also a topic that has been debated for a long time. Should programmers master algorithms? Different people have different answers. In fact, many companies have certain requirements for algorithms. Some companies directly require interviewers to handwrite algorithm questions during interviews. This puts a great test on the technical requirements of programmers. Therefore, in the face of today's environment, we must master the algorithm in order to occupy a place in future work.

Then next, I will briefly introduce several sorting algorithms, hoping to be helpful to you.

Bubble Sort

Bubble Sort (Bubble Sort) is a relatively simple sorting algorithm.

It repeatedly visits the column of elements to be sorted, compares two adjacent elements in turn, and swaps them if their order (such as from large to small, first letter from A to Z) is wrong . The work of visiting elements is repeated until no adjacent elements need to be exchanged, which means that the element column has been sorted.

The name of this algorithm comes from the fact that larger elements will slowly "float" to the top of the sequence through exchange (in ascending or descending order), just like the carbon dioxide bubbles in carbonated drinks will eventually float to the top. , hence the name "bubble sort".

Demonstration:

The code is as follows:

@Test
public void bubbleSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	// 统计比较次数
	int count = 0;
	// 第一轮比较
	for (int i = 0; i  arr[j + 1]) {
				// 交换位置
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("一共比较了:" + count + "次");
}

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
一共比较了:105次

Select sort

Selection sort is a simple and intuitive sorting algorithm. Its working principle is: first select the smallest (or largest) element from the data elements to be sorted, store it at the beginning of the sequence, and then find the smallest (largest) element from the remaining unsorted elements. elements and place them at the end of the sorted sequence. And so on, until the number of all data elements to be sorted is zero. Selection sort is an unstable sorting method.

Demonstration:

The code is as follows:

@Test
public void SelectionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 0; i <p>Running results: </p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

The implementation is also very simple, first of all An index variable is defined in the outer loop to store the value of i. This is to avoid repeated comparisons, because after each round of comparison, the first i elements are already sorted, so there is no need to compare again, just start from Just start i. The subsequent comparisons are all based on the element at the index position. If the element at the index position is the minimum value after the comparison, there is no need to exchange, just don't move. And if an element smaller than the element at index is found, then assign the index of the element to index, and then continue to compare until the comparison is completed. The index obtained after the comparison is completed is the minimum value in the array, then at this time Just swap the element at index position with the element at position i.

Insertion sort

Insertion sort is a simple, intuitive and stable sorting algorithm. If there is an already sorted data sequence, and it is required to insert a number into the sorted data sequence, but the data sequence is still ordered after the insertion, a new sorting method - insertion is required. Sorting method, the basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus one. The algorithm is suitable for sorting a small amount of data. The time complexity is is O(n^2). It is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array, except for the last element (making the array one more space to have an insertion position), and the second part only contains this one element (i.e. the element to be inserted). After the first part is sorted, this last element is inserted into the sorted first part.

The basic idea of ​​insertion sort is: at each step, a record to be sorted is inserted into the appropriate position in the previously sorted array according to the size of its key value, until all are inserted.

Demo:

The code is as follows:

@Test
public void InsertionSort() {
	int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
	for (int i = 1; i = 0 && insertValue <p>Running result:</p><pre class="brush:php;toolbar:false">[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

So here, because the array elements We are not sure, so we can only regard the first element of the array as an ordered sequence, so starting from the second element of the array is the element we need to find the insertion position. So the outer loop starts from 1, then saves arr[i], which is the current second element, and then finds the previous element subscript of the element to be inserted, which is i-1. At this time, through a while Loop to compare.

When insertIndex is less than 0, the loop should be exited, because it has been compared with all previous elements. During the comparison process, if the element to be inserted is smaller than the previous element, the previous element is moved backward, that is, the value of the previous element is directly assigned to the position of the element to be inserted. Because the element to be inserted has been saved at the beginning, you only need to assign the value of the element to be inserted to its previous element. Because insertIndex performs a self-decrement operation in the while loop, its previous element subscript should be insertIndex 1. And if the value of the element to be inserted is greater than the previous element, then it will not enter the while loop, so that the position after insertIndex 1 is still its own position, so the value does not change after the assignment, and so on for subsequent operations.

The above is the detailed content of Simple sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!