Java基础（12）-排序和查找

目录

一、冒泡排序

思想

代码实现

实例

二、选择排序

排序思想

代码实现

实例：对数组{21,54,21,2,4,87,24,82,4,5}进行排序

三、快速排序

排序思想

代码实现

实例,对数组{21,54,21,2,4,87,24,82,4,5}进行快速排序

四、二分查找

算法思想

代码实现

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用二分查找算法查找 5 这个元素。

五、基本查找

算法思想

代码实现

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用基本查找对 54 这个元素进行查找

一、冒泡排序

思想

冒泡排序的思想是循环遍历数组，相邻元素两两比较，大的元素后移，所以第一趟循环就确定了最大索引处的元素（为最大值），第二趟确定倒数第二个元素，以此类推。

经过观察，发现完成冒泡排序需要 数组长度-1 趟，而每一趟需要比较 趟数-1 次。

代码实现

package utils.sort;
​
public class BubbleSortUtils {
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j-1]>arr[j]){
                    int t=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=t;
                }
            }
        }
    }
}

实例

对整型数组{21，54，65，21，8，93，2，32，20，58，92}进行冒泡排序。

import utils.sort.BubbleSortUtils;
​
import java.util.Arrays;
​
public class Test {
    public static void main(String[] args) {
        int[] arr={21,54,65,21,8,93,2,32,20,58,92};
        BubbleSortUtils.bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

二、选择排序

排序思想

1. 从0索引开始，依次和后面的元素进行比较，小的元素往前放，第一次排序完成以后，最小值出现在了最小索引处；
2. 第一次比较的时候是从0索引处开始比较了 数组长度-1次 ，第二次排序的时候是从1索引开始，比较了数组长度-2次，第三次排序的时候是从2索引开始，比较了数组长度-3次，以此类推，直到排序完成。
3. 总共比较了数组长度-1次。

代码实现

package org.util;
​
public class SelectSortUtils {
    public static void SelectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int a=i;
            for (int j = i; j < arr.length; j++) {
                if(arr[a]>arr[j]){
                    a=j;
                }
            }
            int t=arr[a];
            arr[a]=arr[i];
            arr[i]=t;
        }
    }
}

实例：对数组{21,54,21,2,4,87,24,82,4,5}进行排序

import org.util.SelectSortUtils;
​
import java.util.Arrays;
​
public class Test {
    public static void main(String[] args) {
        int[] arr={21,54,21,2,4,87,24,82,4,5};
        SelectSortUtils.SelectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

三、快速排序

排序思想

挖坑填数法

1. 将基准数挖出形成第一个坑；
2. 由后向前找比他小的数，找到后挖出此数填到前一个坑中；
3. 由前向后找比他大或者等于他的数，找到后也挖出此数填到前一个坑中；
重复执行2、3步骤。

代码实现

package org.util;
​
public class QuickSortUtils {
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int index = getIndex(arr, start, end);
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);
        }
    }
    public static int getIndex(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        int x = arr[i];
        if (i < j) {
            while (i < j) {
                while (i < j && arr[j] >= x)
                    j--;
                if (arr[j] < x) {
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && arr[i] < x)
                    i++;
                if (arr[i] > x) {
                    arr[j] = arr[i];
                    j--;
                }
            }
        }
        arr[i] = x;
        return i;
    }
}

实例,对数组{21,54,21,2,4,87,24,82,4,5}进行快速排序

import org.util.QuickSortUtils;
​
import java.util.Arrays;
​
public class Test {
    public static void main(String[] args) {
        int[] arr={21,54,21,2,4,87,24,82,4,5};
        QuickSortUtils.quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

四、二分查找

算法思想

前提是数组元素必须是有序的。

算法的思想：每次一都查找中间索引的那个元素，比较大小就能减少一半的元素。

代码实现

package org.locate;

public class BinaryLocate {
    public static int locate(int[] arr, int x) {
        return binaryLocate(arr, 0, arr.length - 1, x);
    }

    public static int binaryLocate(int[] arr, int start, int end, int x) {
        int centerIndex = (start + end) / 2;
        while (start<=end) {
            if (arr[centerIndex] == x) {
                 return centerIndex;
            } else if (arr[centerIndex] > x) {
                 end=centerIndex-1;
            } else {
                 start=centerIndex+1;
            }
            centerIndex=(start+end)/2;
        }
        return -1;
    }
}

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用二分查找算法查找 5 这个元素。

import org.locate.BinaryLocate;

public class Test2 {
    public static void main(String[] args) {
        int[] arr={2, 2, 2, 4, 5, 21, 24, 54, 82, 87};
        System.out.println(BinaryLocate.locate(arr, 21));
    }
}

五、基本查找

算法思想

使用循环对数组进行遍历，用数组元素的每一项和所查元素进行比较，找到需要查找的元素。

代码实现

package org.locate;

public class PrimaryLocate {
    public static int primaryLocate(int[] arr,int ele){
        for (int i = 0; i < arr.length - 1; i++) {
            if(ele==arr[i]){
                return i;
            }
        }
        return -1;
    }
}

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用基本查找对 54 这个元素进行查找

import org.locate.BinaryLocate;
import org.locate.PrimaryLocate;

public class Test2 {
    public static void main(String[] args) {
        int[] arr={2, 2, 2, 4, 5, 21, 24, 54, 82, 87};
        System.out.println(PrimaryLocate.primaryLocate(arr,54));
    }
}