Bubble sort, selection sort, and binary lookup

This is the 13th day of my participation in Gwen Challenge

So AH Q will make a simple introduction here, hoping to deepen the understanding of bubbling sort and selection sort for friends.

The principle of bubble sort algorithm is as follows:

1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.
3. Repeat this step for all elements except the last one.
4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.

The code is as follows:

public static void bubbleSort(int[] arr) {
	//{24, 69, 57, 13, 80};
	for (int i = 0; i < arr.length - 1; i++) {// The outer loop only needs to compare arr. Length-1 times
		for (int j = 0; j < arr.length - 1 - i; j++) {	//-1 is used to prevent index overbounds,-i is used to improve efficiency, because the last edge of each sort is no longer needed to compare.
			if(arr[j] > arr[j+1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j+1] = temp; }}}}Copy the code

The principle of the selection sort algorithm is as follows:

public static void selectSort(int[] arr) {
	//{24, 69, 80, 57, 13};
	for (int i = 0; i < arr.length - 1; i++) {// Just compare arr. Length-1 times, I controls the value at which index
		for (int j = i + 1; j < arr.length; j++) {//j controls the values of the following elements
			if(arr[i] > arr[j]) {
				inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}}}Copy the code

Binary search:

The premise is that the array must be ordered. Set the value to be searched as x, the intermediate index as y, and the total length as length.

1. Determine whether the value at the array y index is equal to x, if it is equal, the index value will be obtained, if it is not equal, then judge: if the intermediate value is greater than x, the index value is 0 – [y-1] interval search; If the median value is less than x, go to the interval [y+1] — [length-1].
2. Repeat Step 1 within the redefined interval;
3. If the minimum index is found to be greater than the maximum index, the search is not possible and the search fails.

The code is as follows:

/ / int [] arr = {11,22,33,44,55,66,77};
public static int getIndex(int[] arr, int value) {
    int min = 0;
    int max = arr.length - 1;
    int mid = (min + max) / 2;

    while(arr[mid] ! = value) {// If the median value is not equal to the desired value, the loop is started
        if(arr[mid] < value) {		// When the median value is less than the desired value
            min = mid + 1;		// Minimal index changes
        }else if (arr[mid] > value){	// When the median value is greater than the desired value
            max = mid - 1;		// Maximum index change
        }
        mid = (min + max) / 2;		// The intermediate index changes regardless of the maximum or minimum change

        if(min > max) {			// If the minimum index is greater than the maximum index, there is no possibility of lookup
           return -1;		/ / return 1}}return mid;
}
Copy the code

These three pieces of knowledge are sorted out here. If you have different opinions or better ideas, please contact Ah Q: Qingqing-4132. Ah Q can invite you to join the technical group to discuss technology together. Ah Q is looking forward to your arrival!