【数据结构与算法】三种简单排序算法，包括冒泡排序、选择排序、插入排序算法

目录

冒泡排序算法

选择排序算法

插入排序算法

快速排序算法

二分查找算法 

---

冒泡排序算法

冒泡排序他是通过双重循环对每一个值进行比较，将小的值向后移动，以达到最终排序的结果，他的时间复杂度为O(n^2)。

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        int l =arr.length;
        for (int i = 0; i 1 ; i++) {
            for (int j = 0; j 1 ; j++) {
                if (arr[j]>arr[j+1]){
                    int temp =arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }

---

选择排序算法

选择排序也是进行两次循环遍历，获取最大或最小的值，然后进行交换。他的时间复杂度也为O(n^2)。

    /**
     * 选择排序算法
     * @param arr
     */
    public static void selectSort(int[] arr){
        int l =arr.length;
        for (int i = 0; i 1 ; i++) {
            int minIndex =i;
            for (int j = i+1; j 
                if (arr[j]
                    minIndex=j;
                }
            }
            int temp =arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=temp;
        }
    }

---

插入排序算法

插入排序是将一个数在前面已经排好的有序列表中进行遍历，插入到符合顺序的地方。以此来获得一个长度+1的有序列表。他的时间复杂度也为O(n^2)。

    /**
     * 插入排序算法
     * @param arr
     */
    public static  void  insertSort(int[] arr){
        int l =arr.length;
        for (int i = 1; i 
            int insert=arr[i];
            int j =i-1;
            while (j>=0&&arr[j]>insert){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=insert;
 
        }
    }

---

快速排序算法

快速排序算法通过一个方法将数组分为两个子数组，这两个数组的值分别为大于pivot的和小于pivot的，在通过对这两个数组进行递归，最终形成一个有序数组。他的时间复杂度相对于前面几个要低一些，为O(nlogn)。

    /**
     * 快速排序算法
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low
            int pivot =partition(arr,low,high);
            quickSort(arr,low,pivot-1);
            quickSort(arr,pivot+1,high);
        }
    }
 
    /**
     *将数组分为两个子数组
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
 
    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

---

二分查找算法 

二分查找算法必须是在有序数组中，才能实现，他的实现思路就是，通过对查找数组的中间值，判断该值大于还是小于想要查找的数。如果大于则在该数的左半区进行二分查找，如果小于在是查找右半区，直到这个中间值等于你要查找的数为止。他的时间复杂度为O(log2n)

/**
 * 二分查找
 * @author CC
 * @version 1.0
 * @since2023/10/17
 */
public class Search {
    public static void main(String[] args) {
        int[] nums ={1,5,7,8,11,16,21,33,66,121};
        System.out.println(binarySearch(nums, 21));
    }
 
    public static int binarySearch(int[] nums,int target){
        if (nums==null||nums.length==0){
            return -1;
        }
 
        int l =0,r=nums.length-1;
        while (l<=r){
            int mid =l+(r-l)/2;
            if (nums[mid]==target){
                return mid;
            }else if (nums[mid]>target){
                r=mid-1;
            }else if (nums[mid]
                l=mid+1;
            }
        }
        return -1;//没找到
    }
}

---

未完待续......