Share the ideas and example codes of several sorting algorithms in Java

Bubble sort

Basic idea: In a set of numbers to be sorted, for all the numbers in the range that are not currently sorted, sort the two adjacent numbers in order from top to bottom. Compare and adjust so that larger numbers sink and smaller numbers rise.
That is: Whenever two adjacent numbers are compared and it is found that their ordering is opposite to the ordering requirements, they are swapped.
The result of the first comparison and sorting: the largest data will be sorted to the largest index
The result of the second comparison and sorting: because the largest data has been placed in the largest index in the first time place, so the data to be compared this time is -1 more than the number of elements in the array, and the second largest data will also be ranked at the second largest index
The result of the third comparison sorting : It’s almost the same as the second time, except that the data to be compared this time is 2 less than the number of elements in the array,
The fourth time: 3 less...
In summary , to sort the data in the array from small to large, the total number of comparisons will be -1 times greater than the length of the array, and as the number of comparisons increases, the data to be compared each time decreases.

public class Demo4 {  
  
    public static void main(String[] args) {  
    int number[]={49,38,65,97,76,13,27,14,10};  
    for(int i=0;i<number.length-1;i++){  
        for(int j=0;j<number.length-1-i;j++){  
        if(number[j]>number[j+1]){  
            int tmp=number[j];  
            number[j]=number[j+1];  
            number[j+1]=tmp;  
        }  
        }  
        for (int j = 0; j < number.length; j++) {  
        System.out.print(number[j]+"\t");  
          
        }  
        System.out.println("排序"+(i+1)+"次后的结果");  
          
    }  
  
    }  
  
}

Selection sorting

Basic method:
Start from the 0 index, compare with the following elements in sequence, put the smaller ones forward, the first time is completed, the minimum value appears at the minimum index at , find the second smallest value for the second time.
How to implement it specifically?
First of all, in the first round, the data on index 0 is compared with the data on each subsequent index in turn, until it encounters data that is smaller than it. At this time, this small data replaces the original data on index 0. , and then the replaced data continues to be compared with the data on the index behind its original index position. In other words, after the first round, the data on index 0 must be the smallest data on this array
In the second round, the data on the 1 index is compared with the subsequent data. At this time, the data participating in the comparison is one less than the original one.
In the third round, there will be one less, so the value of j in the first round of the cycle will be + 1, which is the index subscript starting from j + 1.

public class Demo5 {  
  
    public static void main(String[] args) {  
    int number[]={49,38,65,97,76,13,27,14,10};  
    for(int i=0;i<number.length;i++){  
        for(int j=i+1;j<number.length;j++){  
        if(number[i]>number[j]){  
            int tmp=number[i];  
            number[i]=number[j];  
            number[j]=tmp;  
        }  
        }  
        for (int j = 0; j < number.length; j++) {  
        System.out.print(number[j]+"\t");  
        }  
        System.out.println("第"+(i+1)+"次排序后的结果");  
          
    }  
      
  
    }  
  
}

Insertion sort

Insertion sort is to insert the elements currently to be sorted into an already sorted list. A very vivid example is to grab a playing card with the right hand and insert it into the sorted playing cards held in the left hand.
The worst running time of insertion sort is O(n2), so it is not the optimal sorting algorithm.
If the input array is already sorted, insertion sort occurs optimally, and its running time is a linear function of the input size.
If the input array is sorted in reverse order, the worst case will occur. The average case is the same as the worst case, and its time cost is Θ(n2).

public class Demo6 {  
  
    public static void main(String[] args) {   
        //定义一个整型数组   
        int[] nums = new int[]{4,3,-1,9,2,1,8,0,6};   
        //打印没有进行排序的数组   
        System.out.println("没有排序之前的结果:" + Arrays.toString(nums));   
        for(int index=0; index<nums.length; index++) {   
          //获得需要插入的数值   
          int key = nums[index];   
          //取得下标值   
          int position = index;   
          //循环比较之前排序好的数据，找到合适的地方插入   
          while(position >0 && nums[position-1] > key) {   
            nums[position] = nums[position-1];   
            position--;   
          }   
          nums[position] = key;   
        }   
        //打印排序后的结果   
        System.out.println("排序后的结果:" + Arrays.toString(nums));   
      }   
  
}

The above is the detailed content of Share the ideas and example codes of several sorting algorithms in Java. For more information, please follow other related articles on the PHP Chinese website!