后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 编程语言 > 其他编程其他编程

冒泡排序、选择排序、直接插入排序、快速排序、折半查找>从零开始学JAVA系列

2021-04-18 18:37:03其他编程人已围观

简介目录冒泡排序、选择排序、直接插入排序冒泡排序选择排序选择排序与冒泡排序的注意事项小案例,使用选择排序完成对对象的排序直接插入排序(插入排序)快速排序(比较排序中效率

目录
  • 冒泡排序、选择排序、直接插入排序
    • 冒泡排序
    • 选择排序
    • 选择排序与冒泡排序的注意事项
    • 小案例,使用选择排序完成对对象的排序
    • 直接插入排序(插入排序)
    • 快速排序(比较排序中效率最高的一种排序)
    • 折半查找(使用时有限制,只能是排序好了的数组)
    • 补充一下递归的优点与缺点

冒泡排序、选择排序、直接插入排序

冒泡排序

import java.util.Arrays;

/**
 * @author dengqixing
 * @date 2021/4/17
 */
public class BubbleSort {
    public static void main(String[] args) {
        // 1、定义无序数组
        int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
//        int[] arr = {12, 21, 23, 26, 44, 58, 59, 89, 94, 98};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
        // 外循环,至少比较数组长度减一,因为最后一个元素无需再进行比较
        for (int i = 0; i < arr.length - 1; i++) {
            // 默认序列是有序的
            boolean flag = true;
            // 内循环,由于每次比较都会有一个最大或最小的数被放在最边缘的位置,所以每次循环时都需要对应的减少比较的次数
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                    // 如果第一次小循环进行过交换,说明序列不是有序的,否则说明是有序的
                    flag = false;
                }
            }
            // 这么做如果数组已经是有序了,则无需继续进行比较,减少循环次数,增加效率
            if (flag) {
                break;
            }
        }

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

class SelectSort {
    public static void main(String[] args) {
        // 1、定义无序数组
        int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
        // 外循环,需要 n - 1的循环次数
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            // 进行交换
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
}

选择排序与冒泡排序的注意事项

  • 冒泡排序至多需要n-1趟循环,最少一趟循环;其中n为长度
  • 选择排序一定需要n-1躺循环,一趟也不能少
  • 冒泡排序中最多的操作就是比较和交换,一趟循环中可能发生多次交换;
  • 选择排序中最多的操作就是比较,一趟比较结束后发现更小(或更大)的值才进行交换
  • 所以更推荐使用冒泡。

小案例,使用选择排序完成对对象的排序

class SelectSort2 {
    public static void main(String[] args) {
        // 1、定义无序数组
        Comparable[] arr = {new Person(14,"李四"),new Person(18,"李四"),new Person(16,"李四")};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
       selectSort(arr);

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    private static void selectSort(Comparable[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex].compareTo(arr[j]) > 0) {
                    minIndex = j;
                }
            }
            // 进行交换
            if (minIndex != i) {
                Comparable temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}


class Person implements Comparable<Person> {
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }


    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public int compareTo(Person p) {
        return Integer.compare(this.getAge(), p.getAge());
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

直接插入排序(插入排序)

public static void insertSort(int[] arr) {
        // 默认第一个元素是有序序列,所以从1开始
        for (int i = 1; i < arr.length; i++) {
            // 临时变量存储当前需要插入的数据
            int temp = arr[i];
            // 存储有序序列的元素下标位置
            int j = i - 1;
            // 如果当前的元素小于需要比较的元素
            while (j >= 0 && temp < arr[j]) {
                // 将当前正在比较的元素放入其后面的位置
                arr[j + 1] = arr[j];
                // 继续往左进行数据比较
                j--;
            }
            // 循环结束后,将其比较的元素放在最后比较的一个元素的后面
            arr[j + 1] = temp;
        }
    }

快速排序(比较排序中效率最高的一种排序)

原理:

  • 首先得到一个无序序列
  • 随机选取其中一个数为基准数(一般默认为最左侧的第一个元素)
  • 然后会有两个指针分别在当前需要比较的序列的最左侧和最右侧
  • 先从最右侧开始往左移动比较,一旦碰到了大于或者相等于基准数的元素,则继续向左移动,直到指针所指向的元素小于基准数,就停下(还有一个条件,左边的索引必须小于右边的索引)
  • 然后从最左侧开始向右移动比较,一旦碰到了小于或者相等于基准数的元素,则继续向右移动,直到指针所指向的元素大于基准数,就停下(左边的索引必须小于右边的索引)
  • 如果左指针与右指针相等(也就是相遇了),则将其相遇位置的元素与基准数进行交换
  • 最后再将基准数左边的序列再次进行快速排序
  • 将基准数右边的序列再次进行快速排序
public static void main(String[] args) {
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            // 随机存入1到10万之间的数字
            arr[i] = (int)(Math.random() * 100000)+1;
        }

        // 排序
        long start = System.currentTimeMillis();
        quickSort(arr, 0 , arr.length -1);
        long end = System.currentTimeMillis();
	//19357毫秒,排序1亿个数字的序列竟只用了19秒,
	冒泡排序在10万数据时就已耗时15秒左右,快速排序在10万数据时耗时只有20-30毫秒
        System.out.println("运行时间为 :" + (end - start));
}

    public static void quickSort(int[] arr, int left, int right) {
        // 如果左边索引比右边索引还要大,是不合法的,直接return结束方法
        if (left > right) {
            return;
        }
        // 获得基准数(默认选择最左边的数)与左右2个下标索引数
        int base = arr[left];
        int i = left;
        int j = right;

        // 当i和j不相遇的时候,才进行循环检索
        while (i != j) {
            // 从右边开始检索,如果找到了小于基准数的数,就停下
            // 如果检索到比基准数大的或者相等的,就继续检索
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 从左开始检索,如果找到了大于基准数的数,就停下
            // 如果检索到比基准数小的或者相等的,就继续检索
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 到这说明i和j都停下了,交换它们两的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 到这说明 i 和 j相遇了,就将相遇位置的值与基准数交换
        arr[left] = arr[i];
        arr[i] = base;

        // 然后将排序后左边的序列再次进行排序
        quickSort(arr, left , i -1);
        // 将右边的序列再次进行排序
        quickSort(arr, i + 1, right);
    }
}

折半查找(使用时有限制,只能是排序好了的数组)

// 非递归二分查找
    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 递归二分查找
    public static int binarySearch2(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int index = binarySearch(arr, key, low, high);
        return index;
    }

    private static int binarySearch(int[] arr, int key, int low, int high) {
        if (low > high) {
            return -1;
        }
        // 计算中间索引
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (key < arr[mid]) {
            return binarySearch(arr, key, low, mid - 1);
        } else {
            return binarySearch(arr, key, mid + 1, high);
        }
    }

补充一下递归的优点与缺点

  • 优点:编码简单,适合处理相同业务逻辑的问题
  • 缺点:占用内存空间多,每递归一次都会在栈空间中开辟新空间执行方法

文章来源:查看

Tags:排序   折半   冒泡   插入   从零开始

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)

相关文章

后台-插件-广告管理-内容页广告位三(手机)

随机图文

后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计13614篇文章
  • 浏览统计468次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们