Sorting method: bubble sort, quick sort

Method classification

• select sort: directly select sort and heap sort
• exchange sort: bubble sort, quick sort
• insert sort: direct insert sort, half insert sort, Shell sort
• merge sort
• bucket sort
• cardinality sort

Bubble sorting

method

  1. Compare adjacent elements. If the first one is bigger than the second, exchange them. (start with the first element and compare them in pairs)
  2. Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.
  3. Repeat the above steps for all elements except the last one.
  4. Continue to repeat the above steps for fewer and fewer elements at a time until no pair of numbers need to be compared.

thinking

int[] arr = {4,85,24,36,7,56};  //Define array
//The following procedure is not the final result and is only for organizational thinking
//1. Compare adjacent elements. If the first one is bigger than the second, exchange them.
	if(arr[i] < arr[i + 1]){
		int temp = arr[i];
		arr[i] = arr[i + 1];
		arr[i + 1] = temp;
	}
//2. Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.
	//Start with the first number and perform the first round of sorting
	for(i = 0;i < arr.length - 1;i++){   
	//Because the array definition starts from 0, the range of i is i < = arr.length - 1, that is, i < arr.length
	//In the for loop, if the i-th is larger than the I + 1st, I < arr.length - 1
		if(arr[i] < arr[i + 1]){
			int temp = arr[i];
			arr[i] = arr[i + 1];
			arr[i + 1] = temp;
		}
	}

	//Output array arr
	for(int j : arr){
		System.out.println(j);
	}

//3. Repeat the above steps for all elements except the last one.
//4. Continue to repeat the above steps for fewer and fewer elements each time until there is no pair of numbers to compare.
	//Because after each sorting, the unsorted items in the array will be less than one bit, so it is necessary to loop nesting, and the number of items in each loop will be reduced by one bit
	for(int x = arr.length - 1;x >= 0;x--){
		for(i = 0;i < x;i++){
			if(arr[i] < arr[i + 1]){
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
			}
		}
	}

Combined:

public class maopao {
    public static void main(String[] args) {
        int[] arr = {4,85,24,36,7,56};
        for(int x = arr.length - 1;x >= 0;x--){
            for(int i = 0;i < x;i++){
                if(arr[i] > arr[i + 1] ){
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        for(int j : arr){
            System.out.println(j);
        }
    }
}
4
7
24
36
56
85

Quick sort

method

(1) First, set the first number as the cardinality, and divide the array into left and right parts through the cardinality.
(2) Gather the data greater than or equal to the boundary value to the right of the array, and the data less than the boundary value to the left of the array. At this time, all elements in the left part are less than or equal to the boundary value, while all elements in the right part are greater than or equal to the boundary value.
(3) Then, the data on the left and right can be sorted independently. For the array data on the left, you can take another cardinality and divide this part of the data into left and right parts. Similarly, place the smaller value on the left and the larger value on the right. The array data on the right can also be processed similarly.
(4) By repeating the above process, we can see that this is a recursive definition. After the left part is arranged recursively, the right part is arranged recursively. When the data of the left and right parts are sorted, the sorting of the whole array is completed.

Examples

thinking

// 1. Define data and initialize
	int[] arr = {7,1,5,6,3,9,13,11};
// 2. Quick sort entry. This method is used to sort arrays, so you need to pass an array to this method
    public static void  quick(int[] arr){
        if(arr  == null || arr.length == 0 || arr.length == 1){
        //Return when the sorting length is 0 or empty, there is no need to return
            return;
        }else{
        //When the array does not comply with the above, execute the sort function
            sort(arr,0,arr.length -1);
        }
    }
//3. Define sort function: sort function: sort all elements in the specified interval
//Core algorithm of quick sorting
public static void sort(int[] arr,int left,int right){
	if(left > right){
		return;
	}
	int base = arr[left];
	int i = left;
	int j = right;
	while(i != j){
		//Starting from the left, compare the elements with the base element one by one until you find an element larger than the base element
		while(arr[i] < base && i < j){
			i++;
		}
		//Starting from the right, compare the elements with the base element one by one until you find an element smaller than the base element
		wlile(arr[j] > base && i < j){
			j--;
		}
		//If i < j, exchange the elements corresponding to i and j
		if(i < j){
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//Divide the array into two parts, and then carry out the above process respectively
	sort(arr,0,i);
	sort(arr,i + 1;right);
}

Program integration:

public class kuaisu {
    public static void main(String[] args) {
        int[] arr = {7,1,5,6,3,9,13,11};
        quick(arr);
        for(int x : arr){
            System.out.println(x);
        }
    }
    //Quick sort entry. This method is for array sorting, so you need to pass an array to this method
    public static void  quick(int[] arr){
        if(arr  == null || arr.length ==0 || arr.length == 1){
            return;
        }else{
            sort(arr,0,arr.length -1);
        }
    }
    // Core algorithm of quick sorting
    public static void sort(int[] arr,int left,int right){
        int len  = arr.length;
        if(left > right){
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;
        while(i != j ){
            // Start from the left and use the left element to compare with the base element until you find an element larger than the base element
            while(arr[i] < base && i < j){
                i++;
            }
            // Start from the right and compare the elements on the right with the reference element in turn until you find an element smaller than the reference element
            while(arr[j] > base && i < j){
                j--;
            }
            if(i < j ){
                int temp = arr[i];
                arr[i]= arr[j];
                arr[j] = temp;
            }
        }
        sort(arr,0,i -1);
        sort(arr,i + 1 , right);
    }
}
1
3
5
6
7
9
11
13

Tags: Java

Posted by Hellbringer2572 on Tue, 03 May 2022 01:39:06 +0300