八种排序算法与代码实现(Java代码实现)

简介: 八大排序算法是:1、直接插入排序;2、希尔排序;3、简单选择排序;4、堆排序;5、冒泡排序;6、快速排序;7、归并排序;8、桶排序/基数排序。

选择排序

1.遍历整个序列,将最小的数放在最前面。
2.遍历剩下的序列,将最小的数放在最前面。
3.重复第二步,直到只剩下一个数。
  /**
     * 选择排序
     * @param arr 待排序的数组
     */
    public void selectSort(int[] arr){
        for (int i=0;i<arr.length;++i){
            for (int j=i+1;j< arr.length;++j){
                if (arr[i]>arr[j]){
                    arr[i]^=arr[j];
                    arr[j]^=arr[i];
                    arr[i]^=arr[j];
                }
            }
        }
    }

基数排序(桶排序)

1.将所有的数的个位数取出,按照个位数进行排序,构成一个序列。
2.将新构成的所有的数的十位数取出,按照十位数进行排序,构成一个序列。
注意:负数不行,小数不行
    public void radixSort(int[] arr) {

        int maxArr = arr[0];
        //首先获取数组中最大数的位数
        for (int i = 0; i < arr.length; i++) {
            if (maxArr < arr[i]) {
                maxArr = arr[i];
            }
        }
        //用特殊的方法获取整数的位数
        int maxLength = (maxArr + "").length();

        //准备开始排序
        //首先创建10个桶,用来存放数据
        int[][] bucket = new int[10][arr.length];
        //每个水桶的索引(即 每个水桶 里面有多少个数据)
        int[] bucketOfElement = new int[bucket.length];

        for (int l = 0, n = 1; l < maxLength; l++, n *= 10) {
            int currentnum = 0;
            //将arr数组中的数  进行分开,分到对应的桶中
            for (int i = 0; i < arr.length; i++) {
                currentnum = arr[i] / n % 10;
                bucket[currentnum][bucketOfElement[currentnum]] = arr[i];
                bucketOfElement[currentnum]++;
            }

            //依次将桶中的数据 合到数组中
            int indexArr = 0;
            int indexBucket = 0;
            for (int j = 0; j < bucketOfElement.length; j++) {
                while (bucketOfElement[j] != 0) {
                    arr[indexArr] = bucket[j][indexBucket];
                    indexArr += 1;
                    indexBucket += 1;
                    bucketOfElement[j]--;
                }
                indexBucket = 0;
            }
        }
    }




希尔排序

1.将数的个数设为n,取奇数k=n/2,将下标差值为k的书分为一组,构成有序序列。
2.再取k=k/2 ,将下标差值为k的书分为一组,构成有序序列。
3.重复第二步,直到k=1执行简单插入排序。

    public static int[] shellSort(int[] arr) {
        int temp = 0;
        //插入时 采用交换法
        for (int l = arr.length / 2; l > 0; l /= 2) {
            //遍历各组中所有的元素,(共有 l 组,每组有数个元素)。 l 为步长
            for (int i = l; i < arr.length; ++i) {
                for (int j = i; j - l >= 0; j -= l) {
                    //如果当前的元素大于 加上步长后的那个元素的话就 交换位置
                    if (arr[j] < arr[j - l]) {
                        temp = arr[j];
                        arr[j] = arr[j - l];
                        arr[j - l] = temp;
                    }
                }
            }
        }
        return arr;
    }




归并排序

1.选择相邻两个数组成一个有序序列。
2.选择相邻的两个有序序列组成一个有序序列。
3.重复第二步,直到全部组成一个有序序列。
/**
     * 归并排序
     * @param arr 需要排序的数组
     * @param left 数组左边的索引
     * @param right 数组右边的索引
     */
    public void mergetSort(int[] arr , int left ,int right){
        if (left<right){
            int mid = (left+right)/2;
            //向坐递归
            mergetSort(arr,left,mid);
            //向右递归
            mergetSort(arr,mid+1,right);
            //合并递归后的
            merget(arr,left,mid,right);
        }
    }
    
    /**
     * 合并的方法
     *
     * @param arr   需要排序的数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间序列的索引
     * @param right 右边序列的索引
     */
    public void merget(int[] arr,int left,int mid,int right){

        int l =left;//初始化l,左边有序序列的初始索引
        int m = mid+1; //初始化m,右边有序序列的初始索引
        int index=0;//指向tempArr数组的当前索引
        //做中转的数组
        int[] tempArr=new int[right-left+1];
        //比较两个素组
        //先把左右两边  有序的  按照规则填充到temp数组中
        //直到 有一边的数组已经处理完毕
        while (l<=mid&&m<=right){
            //如果左边有序序列的当前元素 小于右边的有序序列的当前元素
            //即将左边的当前元素,填充到team
            //让后 l++   index++
            if (arr[l]<arr[m]){
                tempArr[index]=arr[l];
                l++;
            }else{  //反之 将右边的当前元素  填充到team数组中
                tempArr[index]=arr[m];
                m++;
            }
            index++;
        }
        //把剩余数组 依次填充到tempArr 数组中
        
        //如果左边有剩余,就把左边的全部加进去
        while (l<=mid){
            tempArr[index]=arr[l];
            l++;
            index++;
        }
        //如果右边有剩余,就把右边的全部加进去
        while(m<=right){
            tempArr[index]=arr[m];
            m++;
            index++;
        }
        //将tempArr中 有序的元素,添加到 arr数组中
        int i=0;
        while (left<=right){
            arr[left]=tempArr[i];
            i++;
            left++;
        }
    }




插入排序

1.将第一个数和第二个数排序,然后构成一个有序序列
2.将第三个数插入进去,构成一个新的有序序列。
3.对第四个数、第五个数……直到最后一个数,重复第二步。
    /**
     * 插入排序
     *
     * @param arr 需要排序的数组
     */
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i]<arr[j]){
                    arr[j]^=arr[i];
                    arr[i]^=arr[j];
                    arr[j]^=arr[i];
                }
            }
        }
    }




冒泡排序

1.将序列中所有元素两两比较,将最大的放在最后面。
2.将剩余序列中所有元素两两比较,将最大的放在最后面。
3.重复第二步,直到只剩下一个数。
   /**
     * 冒泡排序
     *
     * @param arr 待排序的数组
     */
    public void bubbleSort(int[] arr) {
        for (int i = arr.length; i > 0; --i) {
            for (int j = 1; j < i; ++j) {
                if (arr[j] < arr[j - 1]) {
                    //交换位置
                    arr[j] ^= arr[j - 1];
                    arr[j - 1] ^= arr[j];
                    arr[j] ^= arr[j - 1];
                }
            }
        }
    }




堆排序

思路:
1.将序列构建成大顶堆。
2.将根节点与最后一个节点交换,然后断开最后一个节点。
3.重复第一、二步,直到所有节点断开。
/**
     * 堆排序
     *
     * @param arr 待排序的数组
     */
    public void headSort(int[] arr) {
        int len = arr.length - 1;
        //利用循环 排成大顶堆 (叶子结点 小于父节点 满足a[i]>a[i*2+1]&&a[i]>a[i*2+2]条件)
        for (int i = len / 2 - 1; i >= 0; --i) {
            swap(arr, i, len);
        }
        int temp = 0;
        //排完序之后堆顶一定是最大的数,让后把最大的数放到数组最后面断开节点
        for (; len > 0; len--) {
            temp = arr[len];
            arr[len] = arr[0];
            arr[0] = temp;
            swap(arr, 0, len - 1);
        }
    }

public void swap(int[] arr, int k, int len) {

        for (int i = k * 2 + 1; i <= len; i = i * 2 + 1) {
            if (i < len && arr[i] < arr[i + 1]) i++;

            if (arr[i] > arr[k]) {
                int temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                k = i;
            }
        }
    }




快速排序

思路:
1.选择第一个数为p,小于p的数放在左边,大于p的数放在右边。
2.递归的将p左边和右边的数都按照第一步进行,直到不能递归。
 /**
     * 快速排序
     *
     * @param arr   需要排序的数组
     * @param left  0
     * @param right 数组的长度-1
     */
    public void fastSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int mid = (l + r) / 2;
        while (l < r) {
            //在左边找到大于的值
            while (arr[l] < arr[mid]) l++;
            //在右边找到小于的值
            while (arr[r] > arr[mid]) r--;
            //如果 l>= r ,则说明 mid左边全是小于arr[mid]的数,右边全是大于arr[mid]的数
            if (l >= r) break;
            //交换位置
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完之后, 发现arr[l] == arr[mid] 则r-- ,前移
            if (arr[l] == arr[mid]) {
                r -= 1;
            }
            //如果交换完之后, 发现arr[r]==arr[mid]  则l--,往后移
            if (arr[r] == arr[mid]) {
                l += 1;
            }
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l++;
            r--;
        }
        //向右递归
        if (l < right) fastSort(arr, l, right);
        //向左递归
        if (r > left) fastSort(arr, left, r);
    }
目录
相关文章
|
9天前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
26 2
|
9天前
|
存储 Java API
键值对魔法:如何优雅地使用Java Map,让代码更简洁?
键值对魔法:如何优雅地使用Java Map,让代码更简洁?
55 2
|
2天前
|
XML 安全 Java
Java反射机制:解锁代码的无限可能
Java 反射(Reflection)是Java 的特征之一,它允许程序在运行时动态地访问和操作类的信息,包括类的属性、方法和构造函数。 反射机制能够使程序具备更大的灵活性和扩展性
15 5
Java反射机制:解锁代码的无限可能
|
4天前
|
存储 安全 Java
系统安全架构的深度解析与实践:Java代码实现
【11月更文挑战第1天】系统安全架构是保护信息系统免受各种威胁和攻击的关键。作为系统架构师,设计一套完善的系统安全架构不仅需要对各种安全威胁有深入理解,还需要熟练掌握各种安全技术和工具。
29 10
|
1天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
7 3
|
6天前
|
搜索推荐 Java 数据库连接
Java|在 IDEA 里自动生成 MyBatis 模板代码
基于 MyBatis 开发的项目,新增数据库表以后,总是需要编写对应的 Entity、Mapper 和 Service 等等 Class 的代码,这些都是重复的工作,我们可以想一些办法来自动生成这些代码。
16 6
|
6天前
|
Java
通过Java代码解释成员变量(实例变量)和局部变量的区别
本文通过一个Java示例,详细解释了成员变量(实例变量)和局部变量的区别。成员变量属于类的一部分,每个对象有独立的副本;局部变量则在方法或代码块内部声明,作用范围仅限于此。示例代码展示了如何在类中声明和使用这两种变量。
|
7天前
|
存储 Java API
优雅地使用Java Map,通过掌握其高级特性和技巧,让代码更简洁。
【10月更文挑战第19天】本文介绍了如何优雅地使用Java Map,通过掌握其高级特性和技巧,让代码更简洁。内容包括Map的初始化、使用Stream API处理Map、利用merge方法、使用ComputeIfAbsent和ComputeIfPresent,以及Map的默认方法。这些技巧不仅提高了代码的可读性和维护性,还提升了开发效率。
23 3
|
7天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
17 1
|
6天前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
13 0