Three simple sorting algorithms (implemented using java)

1. Bubble sorting

Algorithm idea: traverse the array to be sorted, and compare two adjacent elements each time. If their arrangement order is wrong, exchange their positions. After a trip to sort, the largest element will float to the end of the array. Repeat until the sorting is complete.

Sample demonstration:

Algorithm implementation:

 for(int i=0;i<array.length-1;i++){//Sort n-1 times at most for(int j=0;j<array.length-i-1;j++){//The number of times that need to be exchanged if(array[j]>array[j+1]){ int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } }

Algorithm time complexity: O(n2) The outer loop needs to be compared n-1 times, and the inner loop needs to be compared n times.

2. Select sorting

Algorithm idea: reselect the smallest element in the array to be sorted and exchange it with the element at the first position of the array. Then select a smallest element from the remaining elements and exchange it with the element in the second position. If the smallest element is the element in that position, exchange it with itself, and so on until the sorting is complete.

Sample demonstration:

Algorithm implementation:

 for(int i=0;i<array.length;i++){ int min=i; for(int j=i+1;j<array.length;j++){ if(array[j]<array[min]){ min=j; } } int temp=array[min]; array[min]=array[i]; array[i]=temp; }

Time complexity: O(n2) requires n2/2 comparisons and n exchanges

3. Insert sorting

Algorithm idea: start traversing from the second element of the array, compare the element with the previous element, if the element is smaller than the previous element, save the element into a temporary variable, move the previous element backwards in turn, and then insert the element into a suitable position. After each sorting is completed, the elements on the left side of the index must be ordered, but can still be moved. For arrays with fewer inversions, the more efficient the algorithm is.

Note: Inverted: 5 3 6 2 The inverted term is 5-3 5-2 3-2 6-2

Sample demonstration:

Algorithm implementation:

 for(int i=1;i<array.length;i++){ for(int j=i;j>0&&array[j]<array[j-1];j--){ int temp=array[j]; array[j]=array[j-1]; array[j-1]=temp; } }

Time complexity: O(n2) Worst case n2/2 comparison, n2/2 exchange best case N-1 comparison, 0 exchanges

The above three simple sorting algorithms (implemented using Java) are all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.