常见八大排序算法

今天我们带来数据结构中常见的8大排序算法。

排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性
冒泡排序O(n方)O(n方)O(n方)O(1)稳定
插入排序O(n方)O(n方)O(n方)O(1)稳定
选择排序O(n方)O(n方)O(n方)O(1)不稳定
希尔排序O(n1.3方到1,5方)O(n)O(n方)O(1)不稳定
堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定
快速排序O(n log n)O(n log n)

O(n方)

O(n log n)不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定
计数排序O(n + k)O(n + k)O(n + k)O(k)不稳定

一，冒泡排序

思路：1，从头到尾比较相邻的元素，2，重复第一步n-1次

代码实现：

public void BubbleSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        for (int i = 0; i < str.length; i++) {
            for (int j = 0; j < str.length-1-i; j++) {
                if(str[j]<str[j+1]){
                    swap(str,j,j+1);
                }
            }
        }
        System.out.println(Arrays.toString(str));
    }

swap是交换，

private void swap(int[] str,int i,int j){
        int tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }

代码优化： 优化也不会优化到多好基本还是O(n方的复杂度)

 public void BubbleSortLevel(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        for (int i = 0; i < str.length; i++) {
            boolean a = false;
            for (int j = 0; j < str.length-1-i; j++) {
                if(str[j]<str[j+1]){
                    swap(str,j,j+1);
                    a = true;
                }
            }
            if(!a){
                break;
            }
        }
        System.out.println(Arrays.toString(str));
    }

二，插入排序

思路； 1，定义两个下标i,j，tmp，i从1开始向后遍历，把初始的下标值赋给tmp 2，j每次从i前面开始向前遍历，比较j下标的元素和tmp的值。

代码实现：

public void InsertSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int j=0;
        int tmp=0;
        for (int i = 1; i < str.length; i++) {
            tmp = str[i];
            for (j = i-1; j >=0 ; j--) {
                if(str[j]<tmp){
                    str[j+1] = str[j];
                }
                else {
                    break;
                }
            }
            str[j+1] = tmp;
        }
        System.out.println(Arrays.toString(str));
    }

三，选择排序

思路： 1，定义两个下标i，j；i从左向右遍历：2，我们创建一个tmpIndex记录i下标的值，j每次都在i的左边，与tmpIndex的值进行比较，记录新的tmpIndex的值，与i下标交换，重复这个步骤。

代码实现：

public void ChooseSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int j= 0;
        int tmpIndex = 0;
        for (int i = 0; i < str.length; i++) {
            tmpIndex = i;
            for (j = i+1; j < str.length; j++) {
                if(str[j]<str[tmpIndex]){
                    tmpIndex = j;
                }
            }
            swap(str,i,tmpIndex);
        }
        System.out.println(Arrays.toString(str));
    }

四，希尔排序

思路： 希尔排序实际就是多次进行快速排序，但是我们每次是不同的几组数进行排序，我们初始一个gap，gap的取值不一，我们一数组长度/2来赋给gap,每次相邻为gap的元素进行插入排序，再对gap/2，直到gap为1，我们的思路是插入排序对越有序的数组排序越有序

代码实现： 

    public void ShellSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int gap = str.length/2;
        while (gap>=1){
            ShellSort__InsertSort(str,gap);
            gap/=2;
        }
        System.out.println(Arrays.toString(str));
    }
    private void ShellSort__InsertSort(int[] str,int gap){
        int tmp = 0;
        int j = 0;
        for (int i = gap; i < str.length; i++) {
            tmp = str[i];
            for (j = i-gap; j >= 0; j-=gap) {
                if(str[j]<tmp){
                    str[j+gap] =str[j];
                }
                else {
                    break;
                }
            }
            str[j+gap] = tmp;
        }
    }

五，堆排序

思路： 以升序为例，降序建小根堆，升序建大根堆，

1，建堆  2，栈顶元素与尾元素互换，再进行向下调整  3，直到重复步骤2直到0下标。

代码实现： 

public void HeapSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        CreateHeap(str);
        for (int i = str.length-1; i >=0 ; i--) {
            swap(str,i,0);
            ShiftDown(str,0,i);
        }
        System.out.println(Arrays.toString(str));
    }

    private void CreateHeap(int[] str){
        int c = str.length-1;
        int p = (c-1)/2;
        while (p>=0){
            ShiftDown(str,p,str.length);
            p--;
        }
        System.out.println(Arrays.toString(str));
    }

    private void ShiftDown(int[] str, int parent,int usdSize){
        int child = 2*parent+1;
        while (child<usdSize){
            if(child+1<usdSize && str[child]<str[child+1]){
                child++;
            }
            if(str[child]>str[parent]){
                swap(str,child,parent);
                parent = child;
                child = 2*parent+1;
            }
            else {
                break;
            }
        }
    }

六，快速排序

思路： 1，选择一个基准，定义两个下标，一个从右往左走（先走），一个从左往右走，右边遇到小于基准的与左边大于基准的交换，

2，找到基准，从基准左边和右边递归，重复1的过程。

代码实现（递归实现）：

public void QuickSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));
    }
    private void QuickSortChild(int[] str,int start,int end){
        if(start>end){
            return;
        }
        int left = start;
        int right = end;
        int part = partition(str,left,right);
        QuickSortChild(str,start,part-1);
        QuickSortChild(str,part+1,end);
    }
    private int partition(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }

代码优化（递归实现）：（三数取中法）

public void QuickSort2(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));
    }
    private void QuickSortChild2(int[] str,int start,int end){
        if(start>end){
            return;
        }
        int left = start;
        int right = end;
        int mid = middle(left,(left+right)/2,right);
        swap(str,start,mid);
        int part = partition(str,left,right);
        QuickSortChild(str,start,part-1);
        QuickSortChild(str,part+1,end);
    }
    private int partition2(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }
    private int middle(int left,int middle,int right){
        int[] arr = new int[]{left,middle,right};
        Arrays.sort(arr);
        return arr[1];
    }

 代码实现（非递归实现）：

public void QuickSort3(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        QuickSortChild3(str,0,array.length-1);
        System.out.println(Arrays.toString(str));

    }
    private void QuickSortChild3(int[] str,int start,int end){
        Deque<Integer> stack = new ArrayDeque<>();
        int part = partition3(str,start,end);
        if (part+1<end){
            stack.push(end);
            stack.push(part+1);
        }
        if(part-1>start){
            stack.push(part-1);
            stack.push(start);
        }
        while (!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            part = partition3(str,start,end);
            if (part+1<end){
                stack.push(end);
                stack.push(part+1);
            }
            if(part-1>start){
                stack.push(part-1);
                stack.push(start);
            }
        }
    }

    private int partition3(int[] str,int start,int end){
        int left = start;
        int right = end;
        int cmp = str[left];
        while (left<right){
            while (left<right && str[right]<=cmp){
                right--;
            }
            while (left<right && str[left]>=cmp){
                left++;
            }
            if(left<right){
                swap(str,left,right);
            }
        }
        swap(str,start,left);
        return left;
    }

七，归并排序

思路： 1，我们把数据平均分为两个部分定义左中右三个下标，左边递归，右边递归，

2，当左下标大于等于右递下标归停止，我们使用合并数组的方法，把每层递归后有序的左右子树有序化

代码实现：

public void MergeSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        MergeSortChild(str,0,str.length-1);
        System.out.println(Arrays.toString(str));

    }

    private void MergeSortChild(int[] str,int left, int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        MergeSortChild(str,left,mid);
        MergeSortChild(str,mid+1,right);

        MergeSort__new(str,left,mid,right);
    }
    private void MergeSort__new(int[] str,int left,int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] arr = new int[right-left+1];
        int i=0;
        while (s1<=e1 && s2<=e2){
            if(str[s1]<=str[s2]){
                arr[i] = str[s1];
                i++;
                s1++;
            }
            if(str[s2]<str[s1]){
                arr[i] = str[s2];
                i++;
                s2++;
            }
        }
        while (s1<=e1){
            arr[i] = str[s1];
            i++;
            s1++;
        }
        while (s2<=e2){
            arr[i] = str[s2];
            i++;
            s2++;
        }

        for (int k = 0; k < i; k++) {
            str[k+left] = arr[k];
        }
    }

 

八，计数排序

计数排序适合排那些一定范围的大量数据，比如1-100的考试成绩

思路： 1，我们遍历原数组，找出最大值最小值，用他们的差值大小构建一个计数数组，

2，把原数组出现的数字-min放到计数数组里，有一个计数数组就加一，循环遍历计数数组，直到计数数组全部元素都为0

代码实现： 

public void CountIngSort(int[] array){
        int[] str = Arrays.copyOf(array,array.length);
        int max = str[0];
        int min = str[0];
        for (int i = 0; i <str.length ; i++) {
            if(str[i]>max){
                max = str[i];
            }
            if(str[i]<min){
                min = str[i];
            }
        }
        int[] count = new int[max-min+1];

        for (int i = 0; i < str.length; i++) {
            int a = str[i];
            count[a-min]+=1;
        }
        int j = 0;
        int i = 0;
        while (i<count.length) {
            while (count[i]!=0){
                str[j] = i+min;
                j++;
                count[i]--;
            }
            i++;
        }
        System.out.println(Arrays.toString(str));
    }

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/892260.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Opencv形态学的膨胀操作、开运算与闭运算、梯度运算、礼帽与黑帽操作

Opencv形态学的膨胀操作、开运算与闭运算、梯度运算、礼帽与黑帽操作

文章目录 一、膨胀操作二、开运算与闭运算三、梯度运算四、礼帽与黑帽操作 一、膨胀操作 膨胀操作也就是根据图片将边缘的一些细节给丰富&#xff0c;处理的程度取决于卷积核的大小还有膨胀次数。也就是腐蚀操作的相反操作&#xff08;腐蚀操作参考我的上一篇文章 点击跳转&am…
阅读更多...
音视频编辑码部分常识

音视频编辑码部分常识

音视频编辑码常识 基本概念 实时音视频通讯 音视频处理 网络传输。包括采集、编码、网络传输、解码、播放等环节 视频播放器播放一个互联网上的视频文件&#xff0c;需要经过以下几个步骤&#xff1a;解协议&#xff0c;解封装&#xff0c;解码视音频&#xff0c;视音频同…
阅读更多...
C++初阶(二)--C++入门（引用篇）

C++初阶(二)--C++入门（引用篇）

目录 一、引用的基本概念与特性 1.定义与声明 2.特性 二、引用的进阶用法 1.函数参数传递&#xff1a; 2.引用作为函数返回值&#xff08;重点&#xff09; 引用作为返回值的优点 引用作为返回值的注意事项 代码示例 注意事项的进一步说明 三、传值和传引用效率比较 …
阅读更多...
华三服务器R4900 G5在图形界面使用PMC阵列卡（P460-B4）创建RAID，并安装系统（中文教程）

华三服务器R4900 G5在图形界面使用PMC阵列卡（P460-B4）创建RAID，并安装系统（中文教程）

环境以用户需求安装Centos7.9&#xff0c;服务器使用9块900G硬盘&#xff0c;创建RAID1和RAID6&#xff0c;留一块作为热备盘。 使用笔记本通过HDM管理口&#xff08;&#xff09;登录 使用VGA&#xff08;&#xff09;线连接显示器和使用usb线连接键盘鼠标&#xff0c;进行窗…
阅读更多...
10月报名 | 海克斯康Adams二次开发培训

10月报名 | 海克斯康Adams二次开发培训

您好&#xff01;感谢您长期以来对优飞迪科技与海克斯康的关注与支持。我们诚邀您参加10月31日-11月1日的海克斯康Adams二次开发培训&#xff0c;本次培训将通过讲解和实操结合的方式&#xff0c;帮助用户了解Adams二次开发技术&#xff0c;学习Adams命令语言&#xff0c;掌握如…
阅读更多...
[自然语言处理]RNN

[自然语言处理]RNN

1 传统RNN模型与LSTM import torch import torch.nn as nntorch.manual_seed(6)# todo:基础RNN模型 def dem01():参数1&#xff1a;input_size 每个词的词向量维度&#xff08;输入层神经元的个数&#xff09;参数2&#xff1a;hidden_size 隐藏层神经元的个数参数3&#xff1a…
阅读更多...
基于Python的博客系统

基于Python的博客系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…
阅读更多...
智能化企业新人培训：AI助理如何加速新员融入与成长

智能化企业新人培训：AI助理如何加速新员融入与成长

在当今这个快速变化的时代&#xff0c;企业新人的培训不再仅仅局限于传统的教室环境&#xff0c;而是越来越多地融入了先进的技术&#xff0c;特别是人工智能&#xff08;AI&#xff09;。AI助理&#xff0c;作为这一变革的先锋&#xff0c;正在以独特的方式重塑企业新人培训的…
阅读更多...
废水处理（一）——MDPI特刊推荐

废水处理（一）——MDPI特刊推荐

特刊征稿 01 期刊名称&#xff1a; Removing Challenging Pollutants from Wastewater: Effective Approaches 截止时间&#xff1a; 摘要提交截止日期&#xff1a;2024年11月30日 投稿截止日期&#xff1a;2025年5月31日 目标及范围&#xff1a; 该主题是分享去除有毒物…
阅读更多...
TQRFSOC开发板47DR 100G光口ping测试

TQRFSOC开发板47DR 100G光口ping测试

本例程实现TQRFSOC开发板使用100G光口与100G网卡进行ping测试。TQRFSOC开发板有两个100G光口&#xff0c;都将进行测试&#xff0c;所使用的100G网卡同样是我们生产的&#xff0c;有需要的可以配套进行购买。本例程提供两个启动文件&#xff0c;分别对应两个光口&#xff0c;通…
阅读更多...
4D-fy: Text-to-4D Generation Using Hybrid Score Distillation Sampling技术路线

4D-fy: Text-to-4D Generation Using Hybrid Score Distillation Sampling技术路线

这篇文章分为四部分&#xff0c;首先从2021年的CLIP说起。 这篇论文的主要工作是提出了一种名为 CLIP&#xff08;Contrastive Language-Image Pre-training&#xff09; 的模型&#xff0c;它通过自然语言监督学习视觉模型&#xff0c;以实现视觉任务的零样本&#xff08;zer…
阅读更多...
「规模焦虑」如影随形，库迪咖啡想靠便捷店突围能行吗？

「规模焦虑」如影随形，库迪咖啡想靠便捷店突围能行吗？

作者 | 辰纹 来源 | 洞见新研社 “我有一个广东的小兄弟&#xff0c;做了9年的奶茶&#xff0c;后来因为觉得咖啡是一个上升期的赛道&#xff0c;所以毅然决然拿了45万加盟了库迪咖啡&#xff0c;结果全亏损完了&#xff0c;相当于只买了一个配方。” 抖音博主茶饮圈大山哥分…
阅读更多...
MyBatis XML映射文件

MyBatis XML映射文件

XML映射文件 XML映射文件的名称与Mapper接口名称一致&#xff0c;并且将XML映射文件和Mapper接口放置在相同包下&#xff08;同包同名&#xff09;XML映射文件的namespace属性为Mapper接口全限定名一致XML映射文件中SQL语句的id与Mapper接口中的方法名一致&#xff0c;并保持返…
阅读更多...
C语言_指针_进阶

C语言_指针_进阶

引言&#xff1a;在前面的c语言_指针初阶上&#xff0c;我们了解了简单的指针类型以及使用&#xff0c;下面我们将进入更深层次的指针学习&#xff0c;对指针的理解会有一个极大的提升。从此以后&#xff0c;指针将不再是难点&#xff0c;而是学习底层语言的一把利器。 本章重点…
阅读更多...
ubuntu 开放 8080 端口快捷命令

ubuntu 开放 8080 端口快捷命令

文章目录 查看防火墙状态开放 80 端口开放 8080 端口开放 22端口开启防火墙重启防火墙**使用 xhell登录**&#xff1a; 查看防火墙状态 sudo ufw status [sudo] password for crf: Status: inactivesudo ufw enable Firewall is active and enabled on system startup sudo…
阅读更多...
Linux性能调优，还可以从这些方面入手

Linux性能调优，还可以从这些方面入手

linux是目前最常用的操作系统&#xff0c;下面是一些常见的 Linux 系统调优技巧&#xff0c;在进行系统调优时&#xff0c;需要根据具体的系统负载和应用需求进行调整&#xff0c;并进行充分的测试和监控&#xff0c;以确保系统的稳定性和性能。同时&#xff0c;调优过程中要谨…
阅读更多...
第二十一节 图像旋转

第二十一节 图像旋转

void QUickdemo::roate_demo(Mat& image) { Mat dst, M; int w image.cols; int h image.rows; M getRotationMatrix2D(Point2f(w / 2, h / 2), 45, 1.0);--M getRotationMatrix2D(Point2f(w / 2, h / 2), 45, 1.0);&#xff1a;使用getRotationMatrix…
阅读更多...
Linux学习网络编程学习（TCP和UDP）

Linux学习网络编程学习（TCP和UDP）

文章目录 网络编程主要函数介绍1、socket函数2、bind函数转换端口和IP形式的函数 3、listen函数4、accept函数网络模式&#xff08;TCP&UDP&#xff09;1、面向连接的TCP流模式2、UDP用户数据包模式 编写一个简单服务端编程5、connect函数编写一个简单客户端编程 超级客户端…
阅读更多...
jmeter入门：脚本录制

jmeter入门：脚本录制

1.设置代理。 网络连接-》代理-》手动设置代理. ip&#xff1a; 127.0.0.1&#xff0c; port&#xff1a;8888 2. add thread group 3. add HTTP(s) test script recorder, target controller chooses Test plan-> thread Group 4. click start. then open the browser …
阅读更多...
Windows环境下Qt Creator调试模式下qDebug输出中文乱码问题

Windows环境下Qt Creator调试模式下qDebug输出中文乱码问题

尝试修改系统的区域设置的方法&#xff1a; 可以修复问题。但会出现其它问题&#xff1a; 比如某些软件打不开&#xff0c;或者一些软件界面的中文显示乱码&#xff01; 暂时没有找到其它更好的办法。
阅读更多...
最新文章

Copyright @ 2022~2023