Implement insertion sort using java code and pseudocode

Introduction to insertion sorting:

I believe most people have played poker. Many people like to take a card into their hand when they are dealt a card, and order them in order. Come and place your cards. We start with an empty left hand and the cards are on the table. We then take one card at a time from the table and insert it into its place in the left hand. To find the correct position of a card, we compare it with every card already in the hand from right to left.

Recommended java related free video tutorials: java free video tutorials

Pseudo code:

INSERTION-SORT(A)	//A是数组
 for j = 2 to A.length
key = A[j]
//(将A[j]插入排序序列A[1..j-1])
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

java code:

//升序排序
public void InsertSortAscending(int[] A){
		for(int j = 1;j < A.length;j++){
			int key = A[j];
			//将A[j]插入排序序列A[1..j-1]
			int i = j - 1;
			while(i >= 0 && A[i] > key){
				A[j+1] = A[i];
				i = i - 1;
			}
			A[i+1] = key;
		}
}

Let’s take a look at the running steps of insertion sort

Use array A[2,4,7,1,3,6] as an example

Each In the for loop, the yellow rectangle is the value of A[j]. In the while loop on line 7, it is compared with the value of the blue rectangle on the left. The blue arrow indicates that the array is moved one position to the right on line 8, and the yellow arrow indicates where the keyword is moved on line 11.

The first cycle: as shown in the figure below:

The second cycle: as shown in the figure below:

Note: Here A[2] is greater than A[1], because A[1] is definitely greater than A[0], so there is no need to compare A[2] with A[1] size. The while loop will exit because the condition is not met.

The third cycle: as shown in the figure below:

The fourth cycle: as shown in the figure below:

The fifth cycle: as shown in the figure below:

The A array is now as shown in the figure:

In the sixth loop, j is 6, which does not satisfy the loop j

Recommended java related article tutorials: java entry program

The above is the detailed content of Implement insertion sort using java code and pseudocode. For more information, please follow other related articles on the PHP Chinese website!