首页 > 其他分享 >数据结构---排序(下)

数据结构---排序(下)

时间:2024-11-07 22:48:44浏览次数:3  
标签:right int mid --- length 排序 array 数据结构 left

一.快速排序补充

快速排序的分治部分还有其他方法,如挖坑法,快慢指针法。

1.挖坑法(重要)

思路:先将基准位置元素用tmp保存,假定基准位置没有值(有个坑),然后分别从前后向中间遍历,右边大于基准就减减,遇到小于基准的就放到基准值位置的坑中,左边亦然,遍历整个数组后,将基准值填入最后一个左边遍历值。

    //挖坑法
    public static int partition2(int[] array,int start,int end) {
        int pivot = array[start];
        int i = start;
        while(start < end) {
            while(start < end && array[end] >= pivot) {
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= pivot) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = pivot;
        return start;
    }

细节注意:填坑不是互换

2.快慢指针法

通过建立两个指针,一个满足小于基准值++,另一个在前一个指针不大于基准时++,大于后不再++;从而与前一个快指针换位。

//快慢指针法
    public static int partition3(int[] array,int start,int end) {
        int prev = start;
        int cur = start+1;
        while(cur <= end) {
           if(array[cur] < array[start] && array[cur] != array[++prev]) {
               swap(array,prev,cur);
           }
           cur++;
        }
        //把最后一个小于[prev]的值换到开头
        swap(array,prev,start);
        return prev;//start不行
    }

3.非递归法快速排序实现

思路:反复利用栈的push,pop来实现递归的效果。核心就是把分别把要排序的数据的left,right压入栈,在排序时弹出用于排序。

    public static void quickSort2(int[] array) {
        int left = 0;
        int right = array.length-1;
        int par = partition3(array,left,right);
        Stack<Integer> stack = new Stack<>();
        if(par > left+1) {
            //left+1是为了保证最少左边右一个元素
            stack.push(left);
            stack.push(par-1);
        }
        if(par < right-1) {
            //right-1是为了
            stack.push(par+1);
            stack.push(right);
        }
        while(!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            par = partition3(array,left,right);
            if(par > left+1) {
                //left+1是为了保证最少左边右一个元素
                stack.push(left);
                stack.push(par-1);
            }
            if(par < right-1) {
                //right-1是为了
                stack.push(par+1);
                stack.push(right);
            }
        }
    }
时间复杂度: O(N*logN) 空间复杂度: O(logN) 稳定性:不稳定

二.归并排序(递归)

思想:

采用分治法的一个非常典型的应用,将数组分解成若干子列,先使若干子列有序,再进行合并操作递归使整个数组有序。

 1.分解

     利用中间值mid递归分解

    public static void mergeSortFunc(int[] array,int left,int right) {
        if(left == right) {
            return;
        }
        int mid = (left + right) / 2;
        //分解
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        
    }

最终分解结果是各子列被分解为长度不超过2的单元

2.合并

先对最终子列排序,之后沿用这个方法递归得数组。

    public static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2= right;
        int k = 0;
        int[] tmpArray = new int[right - left + 1];
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArray[k++] = array[s1++];
            }else {
                tmpArray[k++] = array[s2++];
            }
        }
        while(s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmpArray[k++] = array[s2++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            array[i + left] = tmpArray[i];
        }
    }

总代码:

    public static void mergeSort1(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    public static void mergeSortFunc(int[] array,int left,int right) {
        if(left == right) {
            return;
        }
        int mid = (left + right) / 2;
        //分解
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    public static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2= right;
        int k = 0;
        int[] tmpArray = new int[right - left + 1];
        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmpArray[k++] = array[s1++];
            }else {
                tmpArray[k++] = array[s2++];
            }
        }
        while(s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmpArray[k++] = array[s2++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            array[i + left] = tmpArray[i];
        }
    }

时间复杂度:O(n*logN)

空间复杂度:O(n)

 稳定性:稳定性

三.归并排序(非递归)

思路:手动分组,利用for循环将数组分解成若干子列,在分解过程中排好序,再循环回原数组。

分解:

    public static void mergeSort2(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                if(right >= array.length) {
                    right = array.length-1;
                }
            }
            gap *= 2;
        }
    }

注意:mid,right可能会越界。

合并:因为分解是从最小子列开始,所以可以在每次循环中排序合并。

    public static void mergeSort2(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

四.计数排序(了解)

将要统计元素大小作为数组下标,通过统计要排序的元素的个数,然后按顺序打印统计数组元素遍的数组下标,完成排序。

    public static void countSort(int[] array) {
        int min = array[0];
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < min) {
                min = array[i];
            }
            if(array[i] > max) {
                max = array[i];
            }
        }
        int len = max - min + 1;
        int[] tmpArray = new int[len];
        //制作计数数组
        for (int i = 0; i < array.length; i++) {
            tmpArray[array[i] - min]++;
        }
        //完成排序
        int Index = 0;
        for (int i = 0; i < len; i++) {
            while(tmpArray[i] != 0) {
                array[Index++] = i + min;
                tmpArray[i]--;
            }
        }
    }

标签:right,int,mid,---,length,排序,array,数据结构,left
From: https://blog.csdn.net/a15670247200/article/details/143532894

相关文章

  • Linux基础 -- (1)
    声明:本文的学习内容来源于B站up主“泷羽sec”的公开分享,所有内容仅限于网络安全技术的交流学习,不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题,请联系本人,我将立即删除相关内容。本文旨在帮助网络安全爱好者提升自身安全技能,并严格遵守国家法律法规。任何人利用本文......
  • Windows基础 -- 常用cmd命令
    声明:本文的学习内容来源于B站up主“泷羽sec”的公开分享,所有内容仅限于网络安全技术的交流学习,不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题,请联系本人,我将立即删除相关内容。本文旨在帮助网络安全爱好者提升自身安全技能,并严格遵守国家法律法规。任何人利用本文......
  • 26文科跨考北大软微刷题日记-DAY2
    昨天学校期中考试,今天更新。完成进度:1.语法基础课第二讲(if条件)课后习题已做完2.打算今晚再看一下408数据结构的6.3_1图的广度优先遍历和6.3_2图的深度优先遍历做题总结:1.如何描述“一个数是另一个数的整数倍”if(a%b==0)2.若出现像python中的字典样式的,如何通过不用......
  • CrewAI-Multimodal-Agent
    CrewAI-Multimodal-Agenthttps://github.com/mdwoicke/CrewAI-Multimodal-Agent #AICrewforReviewingMarkdownSyntax##IntroductionThisprojectisanexampleusingtheCrewAIframeworktoautomatetheprocessreviewingamarkdownfileforsyntaxiss......
  • HC-SR04超声波传感器详解(STM32)
    HC-SR04是一款广泛使用的超声波传感器,它通过发射和接收超声波来测量距离。本文将详细介绍HC-SR04的工作原理、引脚描述、STM32的接线方式以及如何通过STM32控制HC-SR04来测量距离。一、HC-SR04传感器介绍HC-SR04超声波传感器的主要参数如下:工作电压:DC5V工作电流:3.3mA工......
  • CC-ADMIN后台简介一个基于 Spring Boot 2.1.3 、SpringBootMybatis plus、JWT、Shiro
    说明此文章为转发的,方便日后查看。系统演示环境http://www.cc-admin.top/#/home简介CC-ADMIN前端简介现在市面的上后台管理系统很多,不差你这一个,为啥又来个轮子?答:材料不一样。本轮子的选材是在考察过antv、element之后选择了quasar,前两个很优秀,尤其是antv的外观我特......
  • 26文科跨考北大软微刷题日记-DAY1
    这其实是2024年11月5号完成的,今天刚想起来自己还有个博客园账号(你敢信这是我大一在网上搜政治经济学期末考题时发现的宝藏网站),就一并发到园子里了。汇报下本人情况以及考研408进度:1.末九经济学大三,高中物化生。自认为经济学太虚浮(他们都在妄想拟合现实,而且很多假设都是他们的yy......
  • SP15637 GNYR04H - Mr Youngs Picture Permutations 解析
    SP15637GNYR04H-MrYoungsPicturePermutations解析题目链接分析题目性质大意就是给\(k\)排然后每个数列单调,每个横列单调,求满足这样排列的方案数。我们发现:与其为每个位置分配某个学生不如考虑将每个学生分给某个位置。思路根据以上,不妨设:\(f_{a_1,a_2,a_3,a_4,a_5}......
  • 洛谷P3870[TJOI20009]-开关
    时间复杂度越高的算法能模拟的结构就越多...题目大意:给定一串长度为n,元素只能为0或1的序列,默认该序列元素全为0.接下来需要进行m次操作,操作分为两种:1.把区间\([a,b]\)中的所有元素值取反.2.求区间\([a,b]\)中元素值为1的元素数量.每一次调用操作1时,每次一行输出一个......
  • 【YOLOv11改进 - 注意力机制】EMA(Efficient Multi-Scale Attention):基于跨空间学习的高
    介绍摘要通道或空间注意力机制在许多计算机视觉任务中表现出显著的效果,可以生成更清晰的特征表示。然而,通过通道维度缩减来建模跨通道关系可能会对提取深度视觉表示带来副作用。本文提出了一种新颖高效的多尺度注意力(EMA)模块。该模块着重于保留每个通道的信息并减少计算开销,我......