精华内容
下载资源
问答
  • 思路其实也很简单:1、生成两列,分别是需要排序字段的前半部分和后半部分2、如果没有-分隔,则填充为03、分别生成的两列进行排序,先按照前半部分排序,再按照后半部分排序。4、排序好的dataframe选取需要用的...

    修改后的问题,稍微复杂,选用pandas进行操作,代码如下。

    思路其实也很简单:

    1、生成两列,分别是需要排序字段的前半部分和后半部分

    2、如果没有-分隔,则填充为0

    3、分别对生成的两列进行排序,先按照前半部分排序,再按照后半部分排序。

    4、排序好的dataframe选取需要用的数据,转成原来的dict的形式。

    In [23]: a = [

    ...: {"id":863,"hostname":"hdfs"},

    ...: {"id":822,"hostname":"admin"},

    ...: {"id":865,"hostname":"Spark-1"},

    ...: {"id":1074,"hostname":"Spark-10"},

    ...: {"id":867,"hostname":"Spark-2"},

    ...: {"id":1014,"hostname":"Spark-11"}

    ...: ]

    In [24]: import pandas as pd

    In [25]: df = pd.DataFrame(a)

    In [26]: df["first"] = df["hostname"].apply(lambda x: x.split("-")[0])

    In [27]: df["second"] = df["hostname"].apply(lambda x: int(x.split("-")[1])

    if len(x.split("-")) > 1 else 0)

    In [28]: df

    Out[28]:

    hostname id first second

    0 hdfs 863 hdfs 0

    1 admin 822 admin 0

    2 Spark-1 865 Spark 1

    3 Spark-10 1074 Spark 10

    4 Spark-2 867 Spark 2

    5 Spark-11 1014 Spark 11

    In [29]: df.sort_values(["first","second"], ascending=[True, True])

    Out[29]:

    hostname id first second

    2 Spark-1 865 Spark 1

    4 Spark-2 867 Spark 2

    3 Spark-10 1074 Spark 10

    5 Spark-11 1014 Spark 11

    1 admin 822 admin 0

    0 hdfs 863 hdfs 0

    In [30]: new_df = df.sort_values(["first","second"],

    ascending=[True, True])[["id", "hostname"]].reset_index(drop=True)

    In [31]: new_df

    Out[31]:

    id hostname

    0 865 Spark-1

    1 867 Spark-2

    2 1074 Spark-10

    3 1014 Spark-11

    4 822 admin

    5 863 hdfs

    In [32]: new_df.to_dict(orient="records")

    Out[32]:

    [{'id': 865, 'hostname': 'Spark-1'},

    {'id': 867, 'hostname': 'Spark-2'},

    {'id': 1074, 'hostname': 'Spark-10'},

    {'id': 1014, 'hostname': 'Spark-11'},

    {'id': 822, 'hostname': 'admin'},

    {'id': 863, 'hostname': 'hdfs'}]

    修改前的答案:

    In [3]: a

    Out[3]:

    [{'id': 865, 'hostname': 'Spark-1'},

    {'id': 1074, 'hostname': 'Spark-10'},

    {'id': 1014, 'hostname': 'Spark-11'},

    {'id': 867, 'hostname': 'Spark-2'}]

    In [4]: a.sort(key = lambda x:int(x["hostname"].split("-")[1]))

    In [5]: a

    Out[5]:

    [{'id': 865, 'hostname': 'Spark-1'},

    {'id': 867, 'hostname': 'Spark-2'},

    {'id': 1074, 'hostname': 'Spark-10'},

    {'id': 1014, 'hostname': 'Spark-11'}]

    展开全文
  • 最近学了几天基础的数据结构的知识,...归并排序的原理:归并排序是将一个集合分成两部分:part1和part2,分别part1和part2进行排序(使用递归法,直到子集合的大小为1,则停止将集合拆分,此时因为子集合中只有一个...

    最近学了几天基础的数据结构的知识,越学越为自己的智商捉急了,再看看好多大牛的一些关于算法的博客,真心觉得差距是这么这么大。好了,废话不多少了,接下来我简要讲述一下两个基本的排序:归并排序和快速排序:

    1. 归并排序

    归并排序的原理:归并排序是将一个集合分成两部分:part1和part2,分别对part1和part2进行排序(使用递归法,直到子集合的大小为1,则停止将集合拆分,此时因为子集合中只有一个元素,所以,这个子集合也就相当于已经拍好了顺序),最后将这两部分排好顺序的集合合并为一。

    在编写代码的时候有几个注意点:

    1. 如何将集合分成两部分,各大小都为多少?

      集合的第一部分为list.length/2;集合的第二部分为list.length-list.length/2;

    2. 集合的递归调用什么时候停止?

      当子集合的大小为1时,则停止对集合划分,故在方法的一开始应该加上一个判断

      If(list.length > 1){

      };

    代码实现:

    public static void mergeSort(int[] list){

            if(list.length > 1){

                int[] half1 = new int[list.length/2];

                int[] half2 = new int[list.length - list.length/2];

                System.arraycopy(list, 0, half1, 0, half1.length); //将集合的前半部分复制到half1

                mergeSort(half1);

                System.arraycopy(list, list.length/2, half2, 0, half2.length); //将集合的后半部分复制到half2

                mergeSort(half2);

                

                int[] temp = merge(half1,half2); //将两个集合合并

                System.arraycopy(temp, 0, list, 0, temp.length);

            }

        }

    上段代码的merge方法的作用是将两个集合合并为一个并返回。

    代码实现:

    private static int[] merge(int[] list1, int[] list2){

            int[] temp = new int[list1.length + list2.length];

            int currentPosition1 = 0; //遍历list1时使用的下标变量

            int currentPosition2 = 0; //遍历list2时使用的下标变量

            int currentPositionTemp = 0; //合并两个list时使用的下标变量

     

            //将两个集合中的元素copy到临时变量中

    while(currentPosition1 < list1.length && currentPosition2 < list2.length){             if(list1[currentPosition1] < list2[currentPosition2]){ //将小的元素放到前面。

                    temp[currentPositionTemp++] = list1[currentPosition1++];

                }else

                {

                    temp[currentPositionTemp++] = list2[currentPosition2++];

                }

            }

            //运行到此处时,list1list2中的至少其中一个list已经全部复制到临时集合中,但有可能list1中元素的数量小于list2中元素

    //的数量,因此,需要将list1或者list2中的剩余的数据复制到临时集合中。

            while(currentPosition1 < list1.length){

                temp[currentPositionTemp++] = list1[currentPosition1++];

            }

            while(currentPosition2 < list2.length){

                temp[currentPositionTemp++] = list2[currentPosition2++];

            }

            return temp;

        }

     

    测试代码:

    public static void main(String[] args) {

            // TODO Auto-generated method stub

            int[] list = {1,29,1,2,90,1,0};

            mergeSort(list);

            for(int temp : list){

                System.out.print(temp + " ");

            }

            System.out.println();

        }

    运行结果:

     

     

    1. 快速排序

      快速排序的原理:快速排序在数组中选择一个称为主元(pivot)的元素将数组分成两个部分,使得第一部分的所有元素小于或等于主元(pivot),而第二部分的所有元素均大于主元(pivot)。然后对第一部分递归得应用快速排序算法,然后对第二部分递归得应用快速排序算法。

      Pivot的英文意思为中心点,所以,快速排序可以理解为找中心点,然后根据中心点,将数组分成两部分,一部分小于或等于中心点,另一部分大于中心点,然后按照此方法对两个部分分别执行,最后就将数组排好了顺序。

      为了简单起见,接下来我的代码实现中,将数组的第一个元素作为中心点(pivot)。

    代码如下:

    说明:此段代码的功能是根据集合的第一个元素作为中心点(pivot)将集合分成两个部分,返回中间点pivot的下标

    private static int partition(int[] list, int first, int last){

    //参数firstlast用于指定,将集合的哪一段按照pivot分成两部分。

            int pivot = list[first]; //取第一个元素作为集合的中心点(pivot)

            int low = first + 1;

            int high = last;

            

            while(high > low){

    //找到从前向后数第一个大于pivot的元素,然后找到从后向前数第一个小于pivot的元素,将他们两个互换

                while(low <= high && list[low] <= pivot)

                    low++;

                

                while(low <= high && list[high] > pivot){

                    high--;

                }

                if(high > low){

                    int temp = list[high];

                    list[high] = list[low];

                    list[low] = temp;

                }

            }

    //经过上面一个循环之后,下标小于low的元素均小于pivot,小标大于high的元素均大于pivot

     

            //high的下标从后向前遍历,直到找到当前下标的值小于等于pivot为止

            while(high > first && list[high] >= pivot){

                high--;

            }

            

            if(pivot > list[high]){//if成立,表示pivot的值不是集合中最小的值,此时将pivot的值放到list[high]的位置上

                list[first] = list[high];

                list[high] = pivot;

                return high;

            }else{ //此种情况表示,pivot为集合中最小的元素,因此,pivot值的小标也就是first

                return first;

            }

        }

    quicksort()代码如下:

    private static void quickSort(int[] list, int first, int last){

            if(last > first){

                int pivotIndex = partition(list,first,last);

                quickSort(list,first,pivotIndex -1);

                quickSort(list,pivotIndex+1,last);

            }

        }

    此时,定义一个只有一个集合作为参数的公共方法:

    public static void quickSort(int[] list){

            quickSort(list,0,list.length-1);

        }

     

     

    测试代码:

    public static void main(String[] args) {

            // TODO Auto-generated method stub

            int[] list = {12,3,2,1,5,2};

            quickSort(list);

            for(int temp : list){

                System.out.print(temp + " ");

            }

            System.out.println();

        }

     

    运行结果:

    转载于:https://www.cnblogs.com/inghzhang/p/3890901.html

    展开全文
  • 排序算法之快速排序

    2020-09-21 22:34:24
    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...

    快速排序
    首先我们来看看百度百科上是怎么说快速排序的:

    快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

    简单的来说,就是先确定一个key,然后分别把比key大和比key小的数分配到两边,然后递归求解,这样得到的结果一定是一个有序列。

    看图理解快一点

    假设一开始的序列是这样的,我们假设要排成一个递增序列,我一般都是取中间的值为key值
    在这里插入图片描述我们分别在key的左边和右边的序列分别设立两个指针指向头尾。

    然后我们分别判断它们与key值的大小,如果beg对应的值小于key则将执行beg++,对右边的序列也一样,像是上面的图,我们不需要移动beg和end指针。然后我们交换beg和end对应的值,就有了下图

    在这里插入图片描述
    重复上一过程直到beg不小于end,然后递归key的左右两边的序列,如下图

    在这里插入图片描述
    重复刚才说的,下面就不多说了

    在这里插入图片描述

    在这里插入图片描述
    这样我们就排序好了,原理懂了代码就简单了

    void QuickSort(int arr[],int low, int high)
    {
        int temp;
        int beg = low;
        int end = high;
        int mid = arr[(low + high) / 2];
        do
        {
            while (arr[beg] < mid) //查找左半部分比mid大的数
            {
                beg++;
            }
            while (arr[end] > mid) //查找右半部分比mid小的数
            {
                end--;
            }
            if (beg <= end)
            {
                swap(arr[beg], arr[end]);
                beg++;
                end--;
            }
        } while (beg <= end);
        if (low < end)
        {
            QuickSort(arr,low, end);
        }
        if (beg < high)
        {
            QuickSort(arr,beg, high);
        }
    }
    

    这是我的第三篇博客了,如果有不足的地方请指出来便于我改进

    展开全文
  • 其中一部分的所有数据都比另外一部分的所有数据都要小,【可以在这思考一下怎么做- ,或许已经知道怎么做了,等下就验证一下是否是自己想的一样】,然后在按此方法这两部分数据分别进行快速排序,整个排序过程可以...

    快速排序

    快速排序简单介绍

    快速排序:QuickSort 是对冒泡排序的一种改进。
    基本思想
    通过一趟排序将要排序的数据分割成两个独立的部分,其中一部分的所有数据都比另外一部分的所有数据都要小,【可以在这思考一下怎么做- ,或许已经知道怎么做了,等下就验证一下是否是自己想的一样】,然后在按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据有序。

    图解分析快速排序的思想

    在这里插入图片描述

    我们对于分析的步骤进行拆解


    中心思想:从左右两边同时进行检索处理,若左右两边存在位于中轴值两侧的数据,进行交换,否则维持原来位置


    1.第一步,我们通过原始数组获取一个分组的位置下标和对应的值,将原始数组分为两部分,如上图所示,我们对应的下标Index = (left+right)/ 2【left表示为数组的初始左下标,right表示右下标】对应上边例子的index=2,对应的数据为9,我们建立两个指针,一个从左遍历向9逼近,一个从右向9开始逼近,我们将比9小的放在左边部分,比9大的放在右边部分。我们得到一个第二层的这样的数组。

    1. 我们对于分成两部分的数组是不能确保其有序性,我们将对应的两部分在进行如1的操作处理【已经分组的左右两部分不可同时处理】,最终将对应的分组依次从左至右联立起来就得到了我们最终的结果。

    代码实现

    这个因为递归处理,我们就不用一步一步的进行拆解,我们在中间打印一下验证是否如分析结果

    /**
         *
         * @param arr 代操作的数组
         * @param left 数组的左下标
         * @param right 数组的右下标
         */
        public static void quickSort(int[] arr,int left,int right){
            int l =left;
            int r = right;
            // 表示对应的中轴数
            int pivot = arr[(left+right)/2];
            // 临时变量用于操作交换的数
            int temp = 0;
    
            while(l < r){
                //在中轴值的左边一直找
                while(arr[l]<pivot){//在中轴值的左边找,直到找到>=pivot值,就退出
                    l+=1;
                }
                while(arr[r]>pivot){//从右开始
                    r-=1;
                }
                //如果l>=r 说明pivot的左右两边的值
                if(l>=r){
                    break;
                }
                temp =arr[l];
                arr[l]=arr[r];
                arr[r]=temp;
    
                //如果交换完之后,发现arr[l]==pivot 值相等,r--, --前移,想象一下如果中间有多个相同的值,不然会遗漏重复数据
                if(arr[l]==pivot){
                    r--;
                }
                //如果交换完之后,发现arr[r]==pivot 值相等,l++, 后移
                if(arr[r]==pivot){
                    l++;
                }
            }
    
    		//可以在这试着打印看下我们第一次的分组是否符合预期,不进行递归的时候验证一下
    		System.out.println(“看下每次的分组”+Arrays.toString(arr));
            //如果左右下标指向同一个位置,我们要错位处理
            if(l==r){
                l+=1;
                r-=1;
            }
    		
            // 左递归,我们需要最后分组的最前端的,这个可以对理解一下
            if(left<r){
                quickSort(arr,left,r);
    
            }
            if(right>l){
                quickSort(arr,l,right);
            }
    
        }
    

    测试代码(可直接copy使用验证)

    public class QuickSort {
        public static void main(String[] args) {
            int[] arr = {12,4,9,112,-6,5};
            quickSort(arr,0,arr.length-1);
    
            System.out.println("arr快排的结果为"+ Arrays.toString(arr));
        }
    
        /**
         *
         * @param arr 代操作的数组
         * @param left 数组的左下标
         * @param right 数组的右下标
         */
        public static void quickSort(int[] arr,int left,int right){
            int l =left;
            int r = right;
            // 表示对应的中轴数
            int pivot = arr[(left+right)/2];
            // 临时变量用于操作交换的数
            int temp = 0;
    
            while(l < r){
                //在中轴值的左边一直找
                while(arr[l]<pivot){
                    l+=1;
                }
                while(arr[r]>pivot){
                    r-=1;
                }
                //如果l>=r 说明pivot的左右两边的值
                if(l>=r){
                    break;
                }
                temp =arr[l];
                arr[l]=arr[r];
                arr[r]=temp;
    
                //如果交换完之后,发现arr[l]==pivot 值相等,r--, --前移
                if(arr[l]==pivot){
                    r--;
                }
                //如果交换完之后,发现arr[r]==pivot 值相等,l++, 后移
                if(arr[r]==pivot){
                    l++;
                }
            }
    
            //如果左右下标指向同一个位置,我们要错位处理
            if(l==r){
                l+=1;
                r-=1;
            }
            // 左递归,我们需要最后分组的最前端的
            if(left<r){
                quickSort(arr,left,r);
    
            }
            if(right>l){
                quickSort(arr,l,right);
            }
    
        }
    }
    

    结果
    在这里插入图片描述
    效率测试

    同样我们拿8W个随机数据进行排序测试

    测试代码如下

    public static void main(String[] args) {
    
            int[] arr = new int[80000];
            for (int i = 0; i < arr.length; i++) {
                arr[i]=(int)(Math.random()*800000);
            }
    
            System.out.println("快速排序~~");
            Date dateStart = new Date();
            SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
            System.out.println("Front of Execute:"+simpleDateFormat.format(dateStart));
    
            quickSort(arr,0,arr.length-1);
            Date dateEnd = new Date();
            System.out.println("Front of Execute:"+simpleDateFormat.format(dateEnd));
    
        }
    

    8W个随机数排列的效率
    8W 个数据感知不够,顺便测试一下80W个数据的效率
    在这里插入图片描述
    效率应该是感知不到的。相较于其他算法超过1S的处理,快速排序的优势显而易见咯。

    展开全文
  • 归并排序代码实现

    2019-08-17 16:35:51
    描述: 归并排序 - 外部排序(内存有限制,数据无法一次性放入内存,怎么对数据进行排序) JDK库里面的Java代码,涉及排序都优先采用快排(空间复杂度更好一点) 外部排序的问题(文件的操作): 现在有50亿个整数,...
  • 同时也将filter功能与computed属性进行对比,说明各自的适用场景,也为vue2.0版本中即将删除的部分filter功能做准备。需求分析还是先从需求入手,想想实现这样一个功能需要注意什么、大致流程如何、有哪些应用场景...
  • 排序应用于开发中,我们的业务无时无刻不跟排序有关,往往处理数据的时候第一步就是排序,下面将对排序进行详细的介绍。 1. 选择排序 概念:对于给定的一组记录,经过第一轮之后得到最小的元素,然后将该记录与第一...
  • 欢快地安排了大半个晚上来做这次线上期末考,最后发现每种题型做...1-1 N个不同的数据采用冒泡排序进行从大到小的排序,当元素基本有序时交换元素次数肯定最多。 1-2 一棵平衡二叉树,所有非叶结点的平衡因子都..
  • 若本题数据中所有的key都可以在byte的量级进行排序,例如有2个key,他们的排序根据他们第一个不同的byte进行排序。那我们之前选择的数据结构有影响吗?若只有部分key可以又会怎么样? * 问题D:基于Java的思想...
  • 平常在写查询SQL的时候,依赖“SELECT * FROM tableA ORDER BYcolumn1 DESC,column2 ASC "这种...举个例子,浙江省政府目前全省各市的排列是”杭宁温湖嘉绍金衢舟台丽“,这时该怎么合理设计返回正确顺序的数据呢...
  • 今天我们就谈一个会让我们头疼的问题:如何查询的结果进行排名。没错,是排名,不是排序,跟Order By有点关系,但可以认为是另一个问题。排名函数不但可以实现排序,还能够生成排序的排名序...
  • 课程整体进行介绍,让您切实感受到前端工程师学习数据结构与算法的必要性。 1-1 课程导学 试看 1-2 学习姿势 1-3 说明与承诺 第2章 基础算法之“字符串类” 字符串作为JS最基本的数据类型,掌握好字符串类型的...
  • 一、基础问答部分 描述一下计算机网络的七层 ...实现一个函数clone 可以Javascript中的五种主要数据类型(Number、string、Object、Array、Boolean)进行复制 三、框架部分 请说一下react diff 原理
  • 根据上面索引的定义,可以知道索引其实是一种数据结构,主要用于提高表中的查询效率,除此之外,索引还是数据库随机高速读取和记录进行有效排序的基础。 不使用索引情况下数据的读取 除了像 Redis 这样的内存型...
  • 0147. 链表进行插入排序 0150. 逆波兰表达式求值 0152. 乘积最大子数组 0199. 二叉树的右视图 0200. 岛屿数量 0201. 数字范围按位与 0208. 实现 Trie (前缀树) 0209. 长度最小的子数组 0211. ...
  • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。 快排是冒泡...
  • 快排回顾

    2019-03-20 22:37:17
    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...
  • 蛋疼

    2011-09-23 21:16:00
    快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到...
  • 这里演示的功能按钮只是测试,虽然是“添加”或“修改”按钮,但不能报表数据进行编辑,关于数据编辑功能的演示,请参看“数据编辑篇” </i></font>]]> <![CDATA[ <font color='red'> 注意:...
  • 递归

    千次阅读 2015-08-15 14:07:36
    通过一趟排序将要排序的数据分割成前后两部分,其中前边部分的所有数据都比后边部分的所有数据都要小,然后再按此方法这两部分数据分别进行一次分割,这样进行下去直到不能再分,以此达到整个数据变成有序序列。...
  • OBIEE中的TOPN分析

    2013-04-18 17:55:00
    TOPN的意思: 在某个系统中,有时候需要根据一定的规则对数据进行排序,并从排序列表中选取出最大或最小的N个数据,这就是一个TOP-N算法。 实现方式: 但是在利用TOPN进行分析时会存在很多细节问题,例如:如果有...
  • 它们利用 Github 提供的项目话题 topics 数据对源源不断的 Github 项目做聚类分析,从而汇总出类似于 Design 设计,Frontend 前端,Backend 后端,Tools 工具,Devops 开发运维࿰...
  • Pandas由浅入深(二)

    2020-06-20 19:39:35
    ##按照狗名字出现的次数对数据进行排序 df_sorted = df.sort_values(by="Count_AnimalName") ##取前100条 df_sorted[:100] 那么问题来了: 我们具体要选择某一列该怎么选择呢?df[" Count_AnimalName "] 我们要同时...
  • Bitmap位图大法

    2020-11-03 16:15:36
    Bitmap是位图的意思,使用位数字表示数据的状态,可以大量数据进行快速的查找,统计。 面试过程中很多都会涉及到大量数据少量内存来进行判断该元素是否存在?判断某一个ip重复次数最多,进行排序找出前100的...
  • 防止指令重排序 首先看下以下线程A和线程B的部分...从常规的理解来看,上面的代码是不会出问题的,但是JVM可以它们在不改变数据依赖关系的情况下进行任意排序以提高程序性能(遵循as-if-serial语义,即不管怎么排序

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 138
精华内容 55
关键字:

怎么对部分数据进行排序