二分查找+冒泡排序+选择排序+插入排序+单边快排+双边快排

二分查找

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

package com.example.demo.sf;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 16:26
 * @Decsription: 二分查找
 * @Version: 1.0
 */
public class BinarySearch {
    public static void main(String[] args) {
        // 数组已经排序
        int[] array = {1, 2, 5, 6, 8, 11, 13, 15, 17, 20, 22, 24, 26, 28, 30, 32, 35, 38, 41, 46, 53, 56, 58};
        int target = 22;
        System.out.println(getBinarySearch(array,target));
    }

    public static int getBinarySearch(int[] array, int target) {
        int l = 0, r = array.length - 1, m;
        while (l <= r) {
            // m = (l + r) / 2; // 中间位置
            m = (l + r) >>> 1;
            if (array[m] == target) {
                return m; // 找到返回
            } else if (array[m] > target) {
                r = m - 1; // 如果中间大于目标说明位置在左边，更改右边界
            } else {
                l = m + 1; // 如果中间小于目标说明位置在右边，更改左边界
            }
        }
        return -1;
    }
}

冒泡排序

算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

package com.example.demo.sf;

import java.util.Arrays;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 19:20
 * @Decsription: 冒泡排序
 * @Version: 1.0
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        bubbleSort(array);
    }

    public static void bubbleSort(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            boolean swaped = false;
            // 每排序一次，就成功一个值，此时就减少一次内循环
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    swaped = true;
                }
            }
            // 如果本轮内循环一次交换也没有发生，说明整体排序已经完成
            if(!swaped){
                break;
            }
            System.out.println("冒泡排序第" + j + "轮：" + Arrays.toString(arr));
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

package com.example.demo.sf;

import java.util.Arrays;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 19:50
 * @Decsription: 选择排序
 * @Version: 1.0
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        selectionSort(array);
    }

    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int s = i; // 最小值的坐标
            for (int j = s + 1; j < arr.length; j++) {
                if (arr[s] > arr[j]) {
                    s = j;
                }
            }
            if (s != i) {
                swap(arr, s, i);
            }
            System.out.println("选择排序第" + i + "轮：" + Arrays.toString(arr));
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

插入排序

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌  。

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。

package com.example.demo.sf;

import org.jetbrains.annotations.NotNull;

import java.util.Arrays;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 20:03
 * @Decsription: 插入排序
 * @Version: 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        insertSory(array);
    }

    public static void insertSory(int @NotNull [] arr) {
        for (int i = 1; i < arr.length; i++) {
            int t = arr[i]; // 待插入元素
            int j = i - 1; // 代表已排序区域索引
            while (j >= 0) {
                if (t < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break; // 索引 j 之前都是排序好的
                }
                j--;
            }
            arr[j + 1] = t;
            System.out.println("插入排序第" + i + "轮：" + Arrays.toString(arr));
        }
    }
}

快速排序

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

单边快排

package com.example.demo.sf;

import java.util.Arrays;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 21:07
 * @Decsription: 单边快排
 * @Version: 1.0
 */
public class QuickSort1 {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] arr, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(arr, l, h);
        quickSort(arr, l, p - 1); // 左边
        quickSort(arr, p + 1, h); // 右边
    }

    public static int partition(int[] arr, int l, int h) {
        int pv = arr[h]; // 基准点元素
        int i = l;
        for (int j = l; j < h; j++) {
            if (arr[j] < pv) {
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;
            }
        }
        if (i != h) {
            swap(arr, h, i);
        }
        System.out.println("单边排序：" + Arrays.toString(arr));
        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

双边快排

package com.example.demo.sf;

import javafx.beans.binding.When;

import java.util.Arrays;

/**
 * @Auther: Java小强
 * @Date: 2022/1/24 - 21:07
 * @Decsription: 双边快排
 * @Version: 1.0
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] arr, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(arr, l, h);
        quickSort(arr, l, p - 1); // 左边
        quickSort(arr, p + 1, h); // 右边
    }

    public static int partition(int[] arr, int l, int h) {
        int pv = arr[l]; // 基准点元素
        int i = l;
        int j = h;
        while (i < j) {
            // j 从右找小的
            // 内层两个循环都要加i<j，例如数组为[5,1,2,3,6,7,8,9]，j会找到3，i会找到6，这时不能交换
            // 必须从右开始找，例如[5,3,7,2,9,8,1,4]，第一次会相交在8，如果此时外层交换，会将8和5交换
            while (i < j && arr[j] > pv) {
                j--;
            }
            // i 从左找大的
            // 从左找时如果和基准点相等，那应该取下一个，否则会把基准点换走
            while (i < j && arr[i] <= pv) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, l, j); // 此时 i j 已经一致
        System.out.println("双边排序：" + Arrays.toString(arr));
        return j;
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

推荐您阅读更多有关于“ 二分查找 冒泡排序 选择排序 插入排序 单边快排 双边快排 ”的文章

猜你喜欢

• 1-24HTTP POST数据和数据接收
• 1-24常用SpringJPA主键生成策略，UUID和自增
• 1-24Apache Commons Jar包下载
• 1-24IIS服务器返回Bad Request (Invalid Hostname)解决办法
• 1-24SpringJPA 慎重 findAll() 切记分页