百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

八种经典排序算法总结,妈妈再也不用担心我不会了

yuyutoo 2024-10-12 01:07 8 浏览 0 评论

前言

算法和数据结构是一个程序员的内功,所以经常在一些笔试中都会要求手写一些简单的排序算法,以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法,一起学习一下。

一、冒泡排序

思路:

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素就是最大的数;
  • 排除最大的数,接着下一轮继续相同的操作,确定第二大的数...
  • 重复步骤1-3,直到排序完成。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name BubbleSort
 * @date 2020-09-05 21:38
 **/
public class BubbleSort extends BaseSort {
    
    public static void main(String[] args) {
        BubbleSort sort = new BubbleSort();
        sort.printNums();
    }
    
    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}
//10万个数的数组,耗时:21554毫秒

平均时间复杂度:O(n2)

空间复杂度:O(1)

算法稳定性:稳定

二、插入排序

思路:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在前面已排序的元素序列中,从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name InsertSort
 * @date 2020-09-05 22:34
 **/
public class InsertSort extends BaseSort {
    public static void main(String[] args) {
        BaseSort sort = new InsertSort();
        sort.printNums();
    }
    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            //当前值
            int curr = nums[i + 1];
            //上一个数的指针
            int preIndex = i;
            //在数组中找到一个比当前遍历的数小的第一个数
            while (preIndex >= 0 && curr < nums[preIndex]) {
                //把比当前遍历的数大的数字往后移动
                nums[preIndex + 1] = nums[preIndex];
                //需要插入的数的下标往前移动
                preIndex--;
            }
            //插入到这个数的后面
            nums[preIndex + 1] = curr;
        }
    }
}
//10万个数的数组,耗时:2051毫秒

平均时间复杂度:O(n2)

空间复杂度:O(1)

算法稳定性:稳定

三、选择排序

思路:

第一轮,找到最小的元素,和数组第一个数交换位置。

第二轮,找到第二小的元素,和数组第二个数交换位置...

直到最后一个元素,排序完成。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/
public class SelectSort extends BaseSort {
    public static void main(String[] args) {
        SelectSort sort = new SelectSort();
        sort.printNums();
    }
    @Override
    protected void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = nums[i];
                nums[minIndex] = temp;
                nums[i] = nums[minIndex];
            }
        }
    }
}
//10万个数的数组,耗时:8492毫秒

算法复杂度:O(n2)
算法空间复杂度:O(1)
算法稳定性:不稳定

四、希尔排序

思路:

把数组分割成若干(h)个小组(一般数组长度length/2),然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小,h/2->h/4->h/8,并且进行排序,保证有序。当h=1时,则数组排序完成。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/
public class ShellSort extends BaseSort {

    public static void main(String[] args) {
        ShellSort sort = new ShellSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int length = nums.length;
        int temp;
        //步长
        int gap = length / 2;
        while (gap > 0) {
            for (int i = gap; i < length; i++) {
                temp = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] > temp) {
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }
}
//10万个数的数组,耗时:261毫秒

算法复杂度:O(nlog2n)
算法空间复杂度:O(1)
算法稳定性:稳定

五、快速排序

快排,面试最喜欢问的排序算法。这是运用分治法的一种排序算法。

思路:

  1. 从数组中选一个数作为基准值,一般选第一个数,或者最后一个数。
  2. 采用双指针(头尾两端)遍历,从左往右找到比基准值大的第一个数,从右往左找到比基准值小的第一个数,交换两数位置,直到头尾指针相等或头指针大于尾指针,把基准值与头指针的数交换。这样一轮之后,左边的数就比基准值小,右边的数就比基准值大。
  3. 对左边的数列,重复上面1,2步骤。对右边重复1,2步骤。
  4. 左右两边数列递归结束后,排序完成。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/
public class QuickSort extends BaseSort {

    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int star, int end) {
        if (star > end) {
            return;
        }
        int i = star;
        int j = end;
        int key = nums[star];
        while (i < j) {
            while (i < j && nums[j] > key) {
                j--;
            }
            while (i < j && nums[i] <= key) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[star] = nums[i];
        nums[i] = key;
        quickSort(nums, star, i - 1);
        quickSort(nums, i + 1, end);
    }
}
//10万个数的数组,耗时:50毫秒

算法复杂度:O(nlogn)
算法空间复杂度:O(1)
算法稳定性:不稳定

六、归并排序

归并排序是采用分治法的典型应用,而且是一种稳定的排序方式,不过需要使用到额外的空间。

思路:

  1. 把数组不断划分成子序列,划成长度只有2或者1的子序列。
  2. 然后利用临时数组,对子序列进行排序,合并,再把临时数组的值复制回原数组。
  3. 反复操作1~2步骤,直到排序完成。

归并排序的优点在于最好情况和最坏的情况的时间复杂度都是O(nlogn),所以是比较稳定的排序方式。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name MergeSort
 * @date 2020-09-08 23:30
 **/
public class MergeSort extends BaseSort {

    public static void main(String[] args) {
        MergeSort sort = new MergeSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        //归并排序
        mergeSort(0, nums.length - 1, nums, new int[nums.length]);
    }

    private void mergeSort(int star, int end, int[] nums, int[] temp) {
        //递归终止条件
        if (star >= end) {
            return;
        }
        int mid = star + (end - star) / 2;
        //左边进行归并排序
        mergeSort(star, mid, nums, temp);
        //右边进行归并排序
        mergeSort(mid + 1, end, nums, temp);
        //合并左右
        merge(star, end, mid, nums, temp);
    }

    private void merge(int star, int end, int mid, int[] nums, int[] temp) {
        int index = 0;
        int i = star;
        int j = mid + 1;
        while (i <= mid && j <= end) {
            if (nums[i] > nums[j]) {
                temp[index++] = nums[j++];
            } else {
                temp[index++] = nums[i++];
            }
        }
        while (i <= mid) {
            temp[index++] = nums[i++];
        }
        while (j <= end) {
            temp[index++] = nums[j++];
        }
        //把临时数组中已排序的数复制到nums数组中
        if (index >= 0) System.arraycopy(temp, 0, nums, star, index);
    }
}
//10万个数的数组,耗时:26毫秒

算法复杂度:O(nlogn)
算法空间复杂度:O(n)
算法稳定性:稳定

七、堆排序

大顶堆概念:每个节点的值都大于或者等于它的左右子节点的值,所以顶点的数就是最大值。

思路:

  1. 对原数组构建成大顶堆。
  2. 交换头尾值,尾指针索引减一,固定最大值。
  3. 重新构建大顶堆。
  4. 重复步骤2~3,直到最后一个元素,排序完成。

构建大顶堆的思路,可以看代码注释。

动画演示:

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name HeapSort
 * @date 2020-09-08 23:34
 **/
public class HeapSort extends BaseSort {

    public static void main(String[] args) {
        HeapSort sort = new HeapSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        heapSort(nums);
    }

    private void heapSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        //构建大根堆
        createTopHeap(nums);
        int size = nums.length;
        while (size > 1) {
            //大根堆的交换头尾值,固定最大值在末尾
            swap(nums, 0, size - 1);
            //末尾的索引值往左减1
            size--;
            //重新构建大根堆
            updateHeap(nums, size);
        }
    }

    private void createTopHeap(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //当前插入的索引
            int currIndex = i;
            //父节点的索引
            int parentIndex = (currIndex - 1) / 2;
            //如果当前遍历的值比父节点大的话,就交换值。然后继续往上层比较
            while (nums[currIndex] > nums[parentIndex]) {
                //交换当前遍历的值与父节点的值
                swap(nums, currIndex, parentIndex);
                //把父节点的索引指向当前遍历的索引
                currIndex = parentIndex;
                //往上计算父节点索引
                parentIndex = (currIndex - 1) / 2;
            }
        }
    }

    private void updateHeap(int[] nums, int size) {
        int index = 0;
        //左节点索引
        int left = 2 * index + 1;
        //右节点索引
        int right = 2 * index + 2;
        while (left < size) {
            //最大值的索引
            int largestIndex;
            //如果右节点大于左节点,则最大值索引指向右子节点索引
            if (right < size && nums[left] < nums[right]) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            //如果父节点大于最大值,则把父节点索引指向最大值索引
            if (nums[index] > nums[largestIndex]) {
                largestIndex = index;
            }
            //如果父节点索引指向最大值索引,证明已经是大根堆,退出循环
            if (largestIndex == index) {
                break;
            }
            //如果不是大根堆,则交换父节点的值
            swap(nums, largestIndex, index);
            //把最大值的索引变成父节点索引
            index = largestIndex;
            //重新计算左节点索引
            left = 2 * index + 1;
            //重新计算右节点索引
            right = 2 * index + 2;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
//10万个数的数组,耗时:38毫秒

算法复杂度:O(nlogn)
算法空间复杂度:O(1)
算法稳定性:不稳定

八、桶排序

思路:

  1. 找出最大值,最小值。
  2. 根据数组的长度,创建出若干个桶。
  3. 遍历数组的元素,根据元素的值放入到对应的桶中。
  4. 对每个桶的元素进行排序(可使用快排,插入排序等)。
  5. 按顺序合并每个桶的元素,排序完成。

对于数组中的元素分布均匀的情况,排序效率较高。相反的,如果分布不均匀,则会导致大部分的数落入到同一个桶中,使效率降低。

动画演示(来源于五分钟学算法,侵删):

实现代码:

/**
 * @author Ye Hongzhi 公众号:java技术爱好者
 * @name BucketSort
 * @date 2020-09-08 23:37
 **/
public class BucketSort extends BaseSort {

    public static void main(String[] args) {
        BucketSort sort = new BucketSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        bucketSort(nums);
    }

    public void bucketSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        //找出最大值,最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int length = nums.length;
        //桶的数量
        int bucketCount = (max - min) / length + 1;
        int[][] bucketArrays = new int[bucketCount][];
        //遍历数组,放入桶内
        for (int i = 0; i < length; i++) {
            //找到桶的下标
            int index = (nums[i] - min) / length;
            //添加到指定下标的桶里,并且使用插入排序排序
            bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]);
        }
        int k = 0;
        //合并全部桶的
        for (int[] bucketArray : bucketArrays) {
            if (bucketArray == null || bucketArray.length == 0) {
                continue;
            }
            for (int i : bucketArray) {
                //把值放回到nums数组中
                nums[k++] = i;
            }
        }
    }

    //每个桶使用插入排序进行排序
    private int[] insertSortArrays(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return new int[]{num};
        }
        //创建一个temp数组,长度是arr数组的长度+1
        int[] temp = new int[arr.length + 1];
        //把传进来的arr数组,复制到temp数组
        for (int i = 0; i < arr.length; i++) {
            temp[i] = arr[i];
        }
        //找到一个位置,插入,形成新的有序的数组
        int i;
        for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) {
            temp[i + 1] = temp[i];
        }
        //插入需要添加的值
        temp[i + 1] = num;
        //返回
        return temp;
    }
}
//10万个数的数组,耗时:8750毫秒

算法复杂度:O(M+N)

算法空间复杂度:O(M+N)

算法稳定性:稳定(取决于桶内的排序算法,这里使用的是插入排序所以是稳定的)。

总结

讲完这些排序算法后,可能有人会问学这些排序算法有什么用呢,难道就为了应付笔试面试?平时开发也没用得上这些。

我觉得我们应该换个角度来看,比如高中时我们学物理,化学,数学,那么多公式定理,现在也没怎么用得上,但是高中课本为什么要教这些呢?

我的理解是:第一,普及一些常识性的问题。第二,锻炼思维,提高解决问题的能力。第三,为了区分人才。

回到学排序算法有什么用的问题上,实际上也一样。这些最基本的排序算法就是一些常识性的问题,作为开发者应该了解掌握。同时也锻炼了编程思维,其中包含有双指针,分治,递归等等的思想。最后在面试中体现出来的就是人才的划分,懂得这些基本的排序算法当然要比不懂的人要更有竞争力。

建议大家看完之后,能找时间动手写一下,加深理解。


本文为阿里云原创内容,未经允许不得转载。

相关推荐

国产RISC-V终端Sipeed Lichee Console4A上架,1699元起

IT之家12月11日消息,国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A,售价1699元(不带LM4A模块)-3299元。Li...

H3C交换机常用配置命令

1、配置主机名...

ThinkPad老版Bios中英文对应详解

ThinkPad老版Bios中文对应详解。解决方案:...

澳大利亚Console Connect与非洲数据中心达成战略合作,增强整个非洲的数据连接

据techafricanews网11月13日报道,在2024年非洲科技节上,澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议,该协议致力于提升非洲大陆关键...

多功能调焦 腾龙TAP-in Console延期发售

最新消息传出,腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日,腾龙的这款调焦器功能类似于适马的USBDock调焦底座,...

关于交换机上存在的不同接口介绍(一)

生活中常见的电子设备有很多,其中明交换机主要起到的是连接的作用,上面有非常多的接口,下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型,它属于双绞线以...

颜值更高?微软新推精英版Xbox One手柄

本月,微软的XboxOne升级了更强大的版本——XboxOneEliteconsole(精英版?),升级版的控制手柄功能更强大,可以主导你的客厅;从曝光的图片上看得出,新版XboxOneE...

“全球首个”:Console Connect为全球物联网项目推出连接解决方案

据DevelopingTelecoms2月27日报道,在MWC2023上,全球网络即服务(NaaS)平台ConsoleConnect推出了“全球首个”私有连接解决方案,可帮助企业在全球范围内动态...

密码遗忘专题——Console口密码遗忘

如果忘记了Console口密码,用户可以通过以下两种方式来设置新的Console口密码:方法一:通过STelnet/Telnet登录设备修改Console口密码。...

为锐捷路由器交换机开启web和telnet,实现轻松管理

笔者上一篇文章写了关于锐捷二层交换机配置教程,那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样,今天的教程也是基于命令行,比较简单,适合新手小白进行学习。准备工作配置前准备:con...

C# - 类文件构成,C#基本语法,Console属性与方法 007

类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...

Console OS系统帮你在PC上自由切换Windows和安卓应用

通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏,需要时之间切换回Windows进行其他工作,ConsoleOS能够完全利用你的PC硬件配置,该系统可以安装在PC的内置硬盘里,也可以...

交换机通过串口线console口登录设备

一、功能简介:PC端通过设备的Console口登录,实现对第一次上电的设备进行基本配置和管理。...

(每日持续更新)jdk api之Console基础、应用、实战

博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整...

KFC推出“真正的次世代主机”KFConsole!真4K/120帧

今天KFCGaming官方推特发布了一则“主机”宣传片,正式公布了旗下名为KFConsole的全新主机产品。并宣称:游戏的未来就在这里,介绍真正的次世代主机!根据官方介绍,本款KFC主机功能强大,支...

取消回复欢迎 发表评论: