Foreword:
Bubble sort, selection sort, and insertion sort are all sorting algorithms with a time complexity of n^2. They are also the basis for us to learn other sorting algorithms later. Next, I will explain these three sorting algorithms to you in as much detail as possible. Time and optimization plan, if you have gained something, please leave a big like.
Bubble sort:
Basic code:
/**
* Ordinary bubble sort
* Double for loop, the outer loop controls the total number of exchanges, and the inner loop controls the range of the current loop exchange;
* This method places the largest value in the current loop range at the end of this range every time it is exchanged;
* @param nums array to be sorted
*/
public static void bubblingSort01(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
for (int j = 0; j < nums.length - i - 1; j + + ) {
if (nums[j] > nums[j + 1]){
swap(nums,j,j + 1);
}
}
}
}
public static void swap(int [] array,int m,int n){
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
Question: From the {6,1,2,3,5,4} example in the photo above, we can find that if our array is partially ordered, there may be situations where we do not need to perform full loop sorting. Our array is already sorted. This means that our bubble sort can be optimized. If the array elements are no longer exchanged in this loop, the loop will be ended directly (the array will not be exchanged unless it is ordered).
Optimized code:
public static void bubblingSort02(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
//Define a boolean variable, initially true. If no exchange occurs in this loop, exit the loop directly.
boolean flag = true;
for (int j = 0; j < nums.length - i - 1; j + + ) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;//Once the exchange occurs in this loop, let flag = false;
}
}
if (flag) break;
}
}
public static void swap(int[] array, int m, int n) {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
Question: From the example of {6,1,2,3,5,4} in the photo above, we can find that the range of each internal exchange will continue to shrink, getting closer and closer to 0. With this narrowing of the range, we can control it more accurately. The range of this exchange is always smaller than the subscript of the last exchange element, thereby reducing the total number of internal loops.
Further optimized code:
public static void bubblingSort03(int[] nums) {
//We use the lastSwappedIndex variable to control the swap range of the loop, thereby reducing the number of internal loops
int lastSwappedIndex = nums.length - 1;
int count = 0;
for (int i = 0; i < nums.length; i + + ) {
boolean flag = true;
int swappedIndex = lastSwappedIndex-i;
for (int j = 0; j < lastSwappedIndex; j + + ) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;
//Assign the subscript of the currently swapped element to swappedInedx;
swappedIndex = j;
}
}
if (flag) break;
//Assign the subscript of the last element to be exchanged to lastSwappedIndex, thereby reducing the range of the next loop exchange;
lastSwappedIndex = swappedIndex;
}
}
public static void swap(int[] array, int m, int n) {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
Bubble sorting is like bubbles under water constantly rising upwards. When conditions are met, it continuously exchanges adjacent array elements. Each time, the largest or smallest array is placed at the starting point or end of the current array range. .
Select sort
The idea of selection sort is to traverse the array in a double loop. After each round of comparison, find the subscript of the smallest element and exchange it to the first position.
Basic code:
/**
* Select sort 01:
* The outer loop controls the number of loops, and the inner loop looks for the minimum value within the range of this loop.
* @param nums array to be sorted
*/
public static void selectSort01(int[] nums) {
for (int i = 0; i < nums.length; i + + ) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j + + ) {
//If an element smaller than the current minimum subscript element is encountered, replace the minimum subscript
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
if (i != minIndex) {
swap(nums, i, minIndex);
}
}
}
public static void swap(int[] array, int m, int n) {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
Question: For the above selection sort, we find the minimum value of the current array range in each round of comparison. In fact, we can also find the maximum value while finding the minimum value, which requires fewer comparisons. This is binary selection. Sort, find the maximum and minimum values at the same time in each round of comparison, and exchange elements.
Optimized binary selection sorting code:
/**
* Binary selection sorting
* The outer loop controls the number of loops, and the inner loop looks for the maximum and minimum values within the range of this loop.
* Since we can find the maximum and minimum values in one loop, our outer loop can be shortened to twice the original size
* @param nums array to be sorted
*/
public static void selectSort02(int[] nums) {
for (int i = 0; i < nums.length / 2; i + + ) {
int minIndex = i;
int maxIndex = i;
for (int j = i + 1; j < nums.length-i; j + + ) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
if (nums[maxIndex] < nums[j]) {
maxIndex = j;
}
}
//If the subscripts of the maximum value and the minimum value are the same, it means that the remaining elements do not need to be sorted (values of the same size or only the middle element is left)
if (minIndex == maxIndex) break;
//Exchange the minimum value
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
//Since we exchange the minimum value first, if our maximum value subscript is equal to i, we need to update the maxIndex
if (i == maxIndex) maxIndex = minIndex;
temp = nums[maxIndex];
nums[maxIndex] = nums[nums.length - i - 1];
nums[nums.length - i - 1] = temp;
}
}
Insertion sort
Insertion sort divides the array to be sorted into two parts, one part is the sorted array, and the other part is the unsorted array. The process of insertion sort is to continuously remove elements from an unsorted array and insert them into appropriate positions in an ordered array. There are two methods for the insertion process, one is the exchange insertion method and the other is the displacement exchange method. Exchange and displacement are just different insertion methods, among which the displacement exchange method is an optimization of the exchange insertion method.
Exchange insertion method:
/**
*Exchange insertion method
* The outer for controls the number of loops and obtains the current array element to be inserted.
* The inner while loop continuously compares the array elements to be inserted with the sorted array parts to find a suitable position for the array to be inserted.
* @param nums array to be sorted
*/
public static void insertSort03(int[] nums) {
for (int i = 1; i < nums.length; i + + ) {
int j = i;
//Start with the current subscript and continue traversing forward until a suitable position is found for i
//The process of finding a suitable position for i is the process of continuous exchange of subscript i with other subscript elements.
while (j >= 1 & amp; & amp; nums[j - 1] > nums[j]) {
swap(nums, j, j - 1);
j--;
}
}
}
public static void swap(int[] array, int m, int n) {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
Problem: Through the exchange process of the exchange insertion method, we can understand that when we exchange the elements to be sorted, it may not be the final position of the elements to be sorted. We need to continue to exchange, and the number of exchanges is too many. Optimization direction: Exchange only when the elements to be sorted reach the appropriate position. The process of searching is to continuously assign elements of j-1 to elements of j to achieve backward displacement of array elements.
Displacement insertion method:
/**
* Displacement insertion method
* @param nums array to be sorted
*/
public static void insertSort04(int[] nums) {
for (int i = 1; i < nums.length; i + + ) {
int j = i;
// Declare temporary variables to store elements to be sorted
int temp = nums[i];
// j controls the range of exchange to prevent j-1 from out-of-bounds subscripts.
// Compare the elements to be sorted with the sorted array part. If the sorted array elements are larger than the array to be sorted, perform a backward shift operation on the array elements.
while (j >= 1 & amp; & amp; nums[j - 1] > temp) {
nums[j] = nums[j-1];
j--;
}
// Through the previous while loop, we have found a suitable position for j, just continue to insert it.
nums[j] = temp;
}
}
Summarize:
Bubble sort, selection sort, and insertion sort are all algorithms with a time complexity of n^2 and a space complexity of 1. The basic structure is a for loop, which is relatively simple and easy to understand.