The basic idea of Bubble Sorting is to treat the
sorting sequence from front to back (from elements with smaller subscripts) Start), compare the values of adjacent elements in turn, and exchange them if a reverse order is found, so that the elements with larger values gradually move from the front to the back, just like bubbles under water, gradually rising up.
Because during the sorting process, each element is constantly approaching its own position. If
has not been exchanged during a comparison, it means that the sequence is in order.
Illustration of the process of bubble sort algorithm
Original array: 3, 9, -1, 10, 20
First pass of sorting
(1) 3, 9, -1, 10, 20 //If the adjacent elements are in reverse order, swap them
(2 ) 3, -1, 9, 10, 20
(3) 3, -1, 9, 10, 20
(4) 3, -1, 9, 10, 20
Second sorting
(1) -1, 3, 9, 10, 20 //Exchange
(2) -1, 3, 9, 10, 20
(3) -1, 3, 9, 10, 20
Three-pass sorting
(1) -1, 3, 9, 10, 20
(2) -1, 3, 9, 10, 20
The fourth pass of sorting
(1) -1, 3, 9, 10, 20
Summary bubbling Sorting rules
(1) Perform a total of array size - 1 large loop
(2)The number of sorting times for each pass is gradually decreasing
(3) If we find that no exchange occurs in a certain sorting pass, we can end the bubble sorting early. This is the optimization
import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub int arr[]= {3,9,-1,10,-2}; //第i+1趟排序,将最大的数排在最后 int temp=0;//临时变量 for(int i=0;i<arr.length-1;i++) {//定义第几轮排序 for(int j=0;j<arr.length-1-i;j++) { if(arr[j+1]<arr[j]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println("输出第"+(i+1)+"趟排序的结果"); System.out.println(Arrays.toString(arr)); } } }
running result:
Output the first sorting result
[3, -1, 9, -2, 10]
Output the first sorting result The result of the 2nd pass of sorting
[-1, 3, -2, 9, 10]
Output the result of the 3rd pass of sorting
[-1, -2, 3, 9, 10]
Output the results of the 4th sorting
[-2, -1, 3, 9, 10]
Sort ideas:
Original array: 101, 34, 119, 1
First round of sorting: 1, 34, 119, 101
Second round of sorting: 1, 34, 119, 101
Third round of sorting: 1, 34, 101, 119
Instructions:
1. The total array size of selection sorting is - 1 round of sorting
2. Each round of sorting is another cycle, the rules of the cycle (code)
2.1 First assume that the current number is the minimum number
2.2 Then compare it with each subsequent number. If a smaller number is found than the current number, re-determine the minimum number and Get the subscript
2.3 When traversing to the end of the array, get the minimum number of this round and the subscript
2.4 Exchange [in code Continue talking]
import java.util.Arrays; public class QuickSort { public static void main(String[] args) { //int []arr={ 8,3,2,1,7,4,6,5}; int [] arr={101,34,109,1}; quicksort(arr); } public static void quicksort(int []arr){ for(int j=0;j<arr.length-1;j++) { int minindex=j;//假定当前下标为最小值下标 int minnumber=arr[j];//假定当前元素为最小值 for (int i = 1+j; i < arr.length; i++) { if (arr[i] < minnumber) {//若假定最小值并不是最小的 minnumber = arr[i];//重置minnumber minindex = i;//重置minindex } } //将最小值交换 arr[minindex] = arr[j]; arr[j] = minnumber; System.out.println("第"+(j+1)+"轮"); System.out.println(Arrays.toString(arr)); } } }
The above is the detailed content of How to write code to implement bubble sort and selection sort in java. For more information, please follow other related articles on the PHP Chinese website!