精华内容
下载资源
问答
  • 【Python算法作业】“比较大小并计数,得到升序排列索引位置”的方法进行【升序排序】 # 【1.3.1】“比较大小并计数,得到升序排列索引位置”的方法进行【升序排序】 """ 算法思想:对于待排序的数组中的每一个...

    【Python算法作业】“比较大小并计数,得到升序排列索引位置”的方法进行【升序排序】

    # 【1.3.1】“比较大小并计数,得到升序排列索引位置”的方法进行【升序排序】
    """
    算法思想:对于待排序的数组中的每一个元素,统计小于它的元素的个数,
              然后利用这个信息,将各个元素放到有序数组的相应位置上。
    """
    
    def ConvertTo__NumCountList_in_List(L):
      '''
      生成数值列表对应的“数值、到它为止(包含它)出现次数”列表的列表
      输入: 数值列表L
      输出: 嵌套列表,每个列表元素还是一个包含 {数值、到它为止(包含它)出现次数} 的列表
      '''
      # 对L列表中的每个元素,先进行 float 数值化,再将每个数值放到自己的列表里(代码: [float(L[i])] )
      #                      所有 包含单个数值的列表 ,合在一起,是整个大的列表
      listL_Num_Count = [[float(L[i])] for i in range(len(L))]
      
      # 第1个元素,统计到它为止,出现的次数是 1
      listL_Num_Count[0].append(1)
      for i in range(1, len(L)):
        # 对于第i个元素,统计到它为止(包含它)出现的次数,该【统计数值】追加为 数值所在列表 的第2个元素
        count = (L[:i]).count(float(L[i]))
        listL_Num_Count[i].append(count + 1)
    
      return listL_Num_Count
    
    def ComparisonCountingSort(L_Num_Count):
      """用比较计数对数组进行排序
      输入: 列表L_Num_Count,列表的每个元素是包含2个元素的列表:{数值、到它为止(包含它)出现次数}
      输出: 从小到大升序排列的结果
      """
      # 创建额外的数组,数组的值用于记录整个列表中 比该元素小 的元素的个数
      #     计算出来该值后,该值就是最后升序排序时,元素对应的位置索引
      #     smallCountList 数组的每个元素初始化为 0
      smallCountList = [0 for ii in range(len(L_Num_Count))]
      
      # 【for循环开始:】smallCountList[i] 计算得到的是 输入的第i个元素 在升序排序后的索引值
      for i in range(len(L_Num_Count) - 1):
        for j in range(i + 1, len(L_Num_Count)):
          if(L_Num_Count[i][0] < L_Num_Count[j][0]):
            smallCountList[j] += 1
          else:  # 注意这里包含两种情况: 第i个元素【大于】或【等于】第j个元素
            smallCountList[i] += 1
      # 【for循环结束!】smallCountList[i] 计算得到的是 输入的第i个元素 在升序排序后的索引值
    
      # 根据 索引值,将 L_Num_Count 的每个元素(还是包含2个元素的列表) 存放到 输出的升序排序数组里
      sortAscending = [[0,0] for i in range(len(L_Num_Count))]
      for k in range(len(L_Num_Count)):
        sortAscending[smallCountList[k]][0] = L_Num_Count[k][0]  # {数值、到它为止(包含它)出现次数} 中的 【数值】
        sortAscending[smallCountList[k]][1] = L_Num_Count[k][1]  # {数值、到它为止(包含它)出现次数} 中的 【出现次数】
    
      return sortAscending
    
    
    def ComparisonCountingSort_steady(L_Num_Count):
      """用比较计数对数组进行排序【稳定版:相同元素排序后,仍保持原来的相对位置】
      输入: 列表L_Num_Count,列表的每个元素是包含2个元素的列表:{数值、到它为止(包含它)出现次数}
      输出: 从小到大升序排列的结果
      """
      # 创建额外的数组,数组的值用于记录整个列表中 比该元素小 的元素的个数
      #     计算出来该值后,该值就是最后升序排序时,元素对应的位置索引
      #     smallCountList 数组的每个元素初始化为 0
      smallCountList = [0 for ii in range(len(L_Num_Count))]
      
      # 【for循环开始:】smallCountList[i] 计算得到的是 输入的第i个元素 在升序排序后的索引值
      for i in range(len(L_Num_Count) - 1):
        for j in range(i + 1, len(L_Num_Count)):
          # 【稳定版:相同元素排序后,仍保持原来的相对位置】: 注意下面 if 语句【 <= 】中的【=】情况,就是用于保证“算法稳定”的!
          if(L_Num_Count[i][0] <= L_Num_Count[j][0]):
            smallCountList[j] += 1
          else:  # 稳定版:注意这里只包含1种情况: 第i个元素【大于】第j个元素
            smallCountList[i] += 1
      # 【for循环结束!】smallCountList[i] 计算得到的是 输入的第i个元素 在升序排序后的索引值
    
      # 根据 索引值,将 L_Num_Count 的每个元素(还是包含2个元素的列表) 存放到 输出的升序排序数组里
      sortAscending = [[0,0] for i in range(len(L_Num_Count))]
      for k in range(len(L_Num_Count)):
        sortAscending[smallCountList[k]][0] = L_Num_Count[k][0]  # {数值、到它为止(包含它)出现次数} 中的 【数值】
        sortAscending[smallCountList[k]][1] = L_Num_Count[k][1]  # {数值、到它为止(包含它)出现次数} 中的 【出现次数】
    
      return sortAscending
    
    
    if __name__ == '__main__':
      strA = input("请输入要排序的一系列数(用空格分隔):")  # 假设输入 1 3 9 8 6 3 1 2 4 1 8 9 10
      A = strA.split()  # A 是一个list列表
      # 输入转化为 一个数值列表
      listA_onlyNum = [float(A[i]) for i in range(len(A))]
      print("您输入的{}个数值为:{}".format(len(listA_onlyNum), listA_onlyNum))
      
      listA_Num_Count = ConvertTo__NumCountList_in_List(listA_onlyNum)
      print("【温馨提示】:你输入的序列的每个元素,已经标记其出现的次数:")
      print(listA_Num_Count)
    
      print("使用【1.3.1】题目中的算法[ComparisonCountingSort]进行排序:")
      sortedAscend = ComparisonCountingSort(listA_Num_Count)
      print("升序排序结果:{}".format(sortedAscend))
      print("☆☆☆显然:[ComparisonCountingSort]算法是【不稳定】的!")
      
      print("只需要将 if 判断语句中的【小于】改成 【小于等于】,新的[ComparisonCountingSort_steady]算法就是稳定的!")
      print("使用[ComparisonCountingSort_steady]算法进行排序的结果:")
      sortedAscend_steady = ComparisonCountingSort_steady(listA_Num_Count)
      print(sortedAscend_steady)
    
      print("主程序运行结束。")

    测试结果:

    测试日志①:
    请输入要排序的一系列数(用空格分隔):1 3 9 8 6 3 1 2 4 1 8 9 10
    您输入的13个数值为:[1.0, 3.0, 9.0, 8.0, 6.0, 3.0, 1.0, 2.0, 4.0, 1.0, 8.0, 9.0, 10.0]
    【温馨提示】:你输入的序列的每个元素,已经标记其出现的次数:
    [[1.0, 1], [3.0, 1], [9.0, 1], [8.0, 1], [6.0, 1], [3.0, 2], [1.0, 2], [2.0, 1], [4.0, 1], [1.0, 3], [8.0, 2], [9.0, 2], [10.0, 1]]
    使用【1.3.1】题目中的算法[ComparisonCountingSort]进行排序:
    升序排序结果:[[1.0, 3], [1.0, 2], [1.0, 1], [2.0, 1], [3.0, 2], [3.0, 1], [4.0, 1], [6.0, 1], [8.0, 2], [8.0, 1], [9.0, 2], [9.0, 1], [10.0, 1]]
    ☆☆☆显然:[ComparisonCountingSort]算法是【不稳定】的!
    只需要将 if 判断语句中的【小于】改成 【小于等于】,新的[ComparisonCountingSort_steady]算法就是稳定的!
    使用[ComparisonCountingSort_steady]算法进行排序的结果:
    [[1.0, 1], [1.0, 2], [1.0, 3], [2.0, 1], [3.0, 1], [3.0, 2], [4.0, 1], [6.0, 1], [8.0, 1], [8.0, 2], [9.0, 1], [9.0, 2], [10.0, 1]]
    主程序运行结束。

    测试日志②:
    请输入要排序的一系列数(用空格分隔):60 35 81 98 14 47
    您输入的6个数值为:[60.0, 35.0, 81.0, 98.0, 14.0, 47.0]
    【温馨提示】:你输入的序列的每个元素,已经标记其出现的次数:
    [[60.0, 1], [35.0, 1], [81.0, 1], [98.0, 1], [14.0, 1], [47.0, 1]]
    使用【1.3.1】题目中的算法[ComparisonCountingSort]进行排序:
    升序排序结果:[[14.0, 1], [35.0, 1], [47.0, 1], [60.0, 1], [81.0, 1], [98.0, 1]]
    ☆☆☆显然:[ComparisonCountingSort]算法是【不稳定】的!
    只需要将 if 判断语句中的【小于】改成 【小于等于】,新的[ComparisonCountingSort_steady]算法就是稳定的!
    使用[ComparisonCountingSort_steady]算法进行排序的结果:
    [[14.0, 1], [35.0, 1], [47.0, 1], [60.0, 1], [81.0, 1], [98.0, 1]]
    主程序运行结束。

    展开全文
  • 这里我们来介绍一种简单的基于非比较排序算法——Counting Sort 计数排序,其时间复杂度可以达到线性级别基本思想Counting Sort 计数排序,顾名思义,就是统计待排序数组元素的出现次数。其基本思想比较简单:根据...
    之前文章介绍的一些排序算法都是基于比较来进行排序的,故它们在平均情况下的时间复杂度最好也不过是线性对数级别。这里我们来介绍一种简单的基于非比较的排序算法——Counting Sort 计数排序,其时间复杂度可以达到线性级别

    53fdfeb548229497c5c6e87207dc185d.png

    基本思想

    Counting Sort 计数排序,顾名思义,就是统计待排序数组元素的出现次数。其基本思想比较简单:

    1. 根据待排序元素的数值范围大小k(max-min+1),建立一个k大小的频数统计数组counts。对于counts数组而言,其索引范围 0 ~ k-1,正好可以对应到待排序元素的取值范围min~max上

    2. 统计待排序元素element的次数,并其存储到counts数组中,即counts[ elemet-min ] = countValue

    3. 待计数统计完成后遍历counts数组,根据次数值来输出原待排序元素值,此时即完成排序

      这里给出计数排序在Java下的实现:

    /**

    * 计数排序

    */

    public class CountingSort {

    /**

    * 升序排列 (非稳定)

    */

    public static void sort1() {

    // 获取测试用例

    int[] array = getTestCase();

    int size = array.length;

    System.out.println("before sort: " + Arrays.toString(array) );

    // 求取最值

    int[] minMax = getMinMax(array);

    int min = minMax[0];

    int max = minMax[1];

    // 根据数据范围创建统计数组

    int k = max-min+1;

    int[] counts = new int[ k ];

    // 统计原数组中元素出现的次数

    for(int i=0; i<size; i++) {

    int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引

    counts[dataInCountIndex] +=1; // 统计该值次数

    }

    int j = 0; // 有序的数据的插入位置

    for(int i=0; i<k; i++) {

    int originalData = i + min; // 还原 原排序数组的数据值

    while( counts[i]>0 ) {

    array[j] = originalData;

    counts[i]--; // 该数值出现的次数减1

    j++; // 更新有序数据的插入位置

    }

    }

    System.out.println("after sort: " + Arrays.toString(array) );

    }

    /**

    * 求指定数组的最值

    * @param array

    * @return [0]: 最小值; [1]: 最大值;

    */

    private static int[] getMinMax(int[] array) {

    int min = array[0];

    int max = array[0];

    for(int i=1; i<array.length; i++) {

    if( array[i]>max ) {

    max = array[i];

    }

    if( array[i]<min ) {

    min = array[i];

    }

    }

    int[] minMax = new int[]{min,max};

    return minMax;

    }

    /**

    * 获取测试用例

    */

    private static int[] getTestCase() {

    int[] caseArray = {-1,1,-1,1,2};

    return caseArray;

    }

    }

    测试结果如下:

    06a18767b4a8d218a79a2ca8f453fed3.png

    稳定的计数排序

    基本原理

    上面的计数排序算法是非稳定的,而一般我们所说的计数排序都是稳定的。那么如何保证计数排序的稳定性呢?其实很简单,只需在统计完待排序元素的频数后,对counts作累加计算(counts[i] = counts[i-1] + counts[i]),即计算统计数组中指定索引位置上的元素在排序后的位置;然后倒序遍历原数组,根据counts数组中的排序位置来将待排序元素放入合适的位置,同时将counts数组相应的值减1,以使下一个重复的排序元素可以放在前一位的位置上,以保证稳定性

    算法图解

    下图即是通过稳定的计数排序对 -1,1,-1,1,2 序列进行升序排列的图解过程

    1. 建立counts数组

    6db4f7097c2d64e162e2b2e635e84cdd.png

    2. 倒序遍历原待排序数组,按升序排列

    ac160a25ed7e0e369c649794fb6f0a68.png

    Java实现

    这里给出计数排序在Java下的实现:

    /**

    * 计数排序

    */

    public class CountingSort {

    ...

    /**

    * 升序排列 (稳定)

    */

    public static void sort2() {

    // 获取测试用例

    int[] array = getTestCase();

    int size = array.length;

    System.out.println("before sort: " + Arrays.toString(array) );

    // 求取最值

    int[] minMax = getMinMax(array);

    int min = minMax[0];

    int max = minMax[1];

    // 根据数据范围创建统计数组

    int k = max-min+1;

    int[] counts = new int[ k ];

    // 统计原数组中元素出现的次数

    for(int i=0; i<size; i++) {

    int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引

    counts[dataInCountIndex] +=1; // 统计该值次数

    }

    // 计算统计数组的累计值,即计算 统计数组中指定索引位置上的元素在排序后的位置

    // 如果该索引位置上有重复元素,则为重复元素所占的最大排序位置

    for(int i=1; i<k; i++) {

    counts[i] = counts[i-1] + counts[i];

    }

    int[] sortedArray = new int[size]; // 排序结果数组

    // 倒序遍历原数组,保证稳定性

    for(int i=size-1; i>=0; i--) {

    int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引

    // 计算其排序后的位置, 因为数组索引从0开始计算,故应对排序位置减1

    // 例如,排在最前面的元素,排序位置为1,则其在数组中的位置索引应为0

    int sortIndex = counts[dataInCountIndex] - 1;

    sortedArray[sortIndex] = array[i]; // 将原数组元素放入排序后的位置上

    counts[dataInCountIndex]--; // 下一个重复的元素,应排前一个位置,以保证稳定性

    }

    System.out.println("after sort: " + Arrays.toString(sortedArray) );

    }

    ...

    }

    测试结果如下:

    3a8f7c9fd54acf4c81ff8763635d8ede.png

    特点

    复杂度、稳定性

    这里以稳定的计数排序进行说明:

    2d599944675be3c027cf0b38718b2047.png

    缺陷

    1. 计数排序只能适用待排序元素为整数的场景

    2. 待排序元素的数值范围(极差)过大的情况下,计数排序会浪费大量空间,故一般不推荐使用计数排序

    参考文献

    1. 算法导论 · 第3版

    展开全文
  • 冒泡算法及其改进算法,可以减少比较次数,节省时间。
    今天再次复习了最基本的排序思想:冒泡算法,以下是实现的代码:
    #include <iostream>
    using namespace std;
    int main()
    {
    	int a[]={5,2,4,3,1};
        
    	void Display(int a[],int length); 
    
    	int length = sizeof(a)/sizeof(int);  //求数组的长度方法
    
           Display(a,length);
    	int tmp;
    	for(int i=1;i<length;i++)
    			for(int j=0;j<length-i;j++)
                           {
    			if (a[j]>a[j+1])
    			{
    				tmp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=tmp;
    			}
    		}
    
           Display( a,length);
    	return 0;
    }
    
    void Display(int A[],int length)
    {
    	for(int i=0;i<length;i++)
    		cout<<A[i]<<" ";
    	cout<<endl;
    }
    

    
    运行结果:
    改进思想(来自大话数据结构):对于每趟比较交换,如果某一趟没有了交换,则表明已经是升序排列好的,无需再进行后面的比较操作。
    #include <iostream>
    using namespace std;
    typedef bool status;
    int main()
    {
    	int a[]={5,1,2,3,4,9,7,8,6};
        
    	void Display(int a[],int length); 
    
    	int length = sizeof(a)/sizeof(int);  //求数组的长度方法
    
          Display(a,length);
    
        status flag= true; 
    
    	int tmp;
    	for(int i=1;i<length&&flag;i++)
    		{       flag = false;
    			for(int j=0;j<length-i;j++)
     
    			if (a[j]>a[j+1])
    			{
    				tmp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=tmp;
    				flag = true;
    			}
    			cout<<"比较趟数:第"<<i<<"趟"<<endl;
    		}
    
       Display( a,length);
    	return 0;
    }
    
    void Display(int A[],int length)
    {
    	for(int i=0;i<length;i++)
    		cout<<A[i]<<" ";
    	cout<<endl;
    }
    
    运行结果:

       可见增加了标志后,对于已经有序的片段不再进行比较,所以趟数会减少,减小时间开支。
        上述用原来的方法需要8-1=7趟,改进后只用了3趟。
    改进后趟数的计算规律:利用“捆绑法”,讲已经有序的片段进行捆绑视为一个元素,如上述5,1,2,3,4,7,8,6==>5,{1,2,3,4},{7,8},6看做是4个元素的比较排序,故比较趟数为 4-1=3趟。由此可以类推。

    展开全文
  • 这里我们来介绍一种简单的基于非比较排序算法——Counting Sort 计数排序,其时间复杂度可以达到线性级别基本思想Counting Sort 计数排序,顾名思义,就是统计待排序数组元素的出现次数。其基本思想比较简单: 1. ...

    199c2f0a1e7df00f00bf9ad53de33960.png

    之前文章介绍的一些排序算法都是基于比较来进行排序的,故它们在平均情况下的时间复杂度最好也不过是线性对数级别。这里我们来介绍一种简单的基于非比较的排序算法——Counting Sort 计数排序,其时间复杂度可以达到线性级别

    基本思想

    Counting Sort 计数排序,顾名思义,就是统计待排序数组元素的出现次数。其基本思想比较简单: 1. 根据待排序元素的数值范围大小k(max-min+1),建立一个k大小的频数统计数组counts。对于counts数组而言,其索引范围 0 ~ k-1,正好可以对应到待排序元素的取值范围min~max上 2. 统计待排序元素element的次数,并其存储到counts数组中,即counts[ elemet-min ] = countValue 3. 待计数统计完成后遍历counts数组,根据次数值来输出原待排序元素值,此时即完成排序

    这里给出计数排序在Java下的实现:

    /**
     * 计数排序
     */
    public class CountingSort {
    
        /**
         * 升序排列 (非稳定)
         */
        public static void sort1() {
            // 获取测试用例
            int[] array = getTestCase();
            int size = array.length;
    
            System.out.println("before sort: " + Arrays.toString(array) );
    
            // 求取最值
            int[] minMax = getMinMax(array);
            int min = minMax[0];
            int max = minMax[1];
    
            // 根据数据范围创建统计数组
            int k = max-min+1;
            int[] counts = new int[ k ];
    
            // 统计原数组中元素出现的次数
            for(int i=0; i<size; i++) {
                int dataInCountIndex = array[i] - min;    // 计算原数组元素在统计数组中的索引
                counts[dataInCountIndex] +=1;             // 统计该值次数
            }
    
            int j = 0;  // 有序的数据的插入位置
            for(int i=0; i<k; i++) {
                int originalData = i + min; // 还原 原排序数组的数据值
                while( counts[i]>0 ) {
                    array[j] = originalData;
                    counts[i]--;    // 该数值出现的次数减1
                    j++;            // 更新有序数据的插入位置
                }
            }
    
            System.out.println("after sort: " + Arrays.toString(array) );
        }  
    
        /**
         * 求指定数组的最值
         * @param array
         * @return [0]: 最小值; [1]: 最大值;
         */
        private static int[] getMinMax(int[] array) {
            int min = array[0];
            int max = array[0];
            for(int i=1; i<array.length; i++) {
                if( array[i]>max ) {
                    max = array[i];
                }
                if( array[i]<min ) {
                    min = array[i];
                }
            }
            int[] minMax = new int[]{min,max};
            return minMax;
        }
    
        /**
         * 获取测试用例
         */
        private static int[] getTestCase() {
            int[] caseArray = {-1,1,-1,1,2};
            return caseArray;
        }
    }

    测试结果如下:

    22a76f551a9bd90d906ab20ab8a75853.png

    稳定的计数排序

    基本原理

    上面的计数排序算法是非稳定的,而一般我们所说的计数排序都是稳定的。那么如何保证计数排序的稳定性呢?其实很简单,只需在统计完待排序元素的频数后,对counts作累加计算(counts[i] = counts[i-1] + counts[i]),即计算统计数组中指定索引位置上的元素在排序后的位置;然后倒序遍历原数组,根据counts数组中的排序位置来将待排序元素放入合适的位置,同时将counts数组相应的值减1,以使下一个重复的排序元素可以放在前一位的位置上,以保证稳定性

    算法图解

    下图即是通过稳定的计数排序对 -1,1,-1,1,2 序列进行升序排列的图解过程

    1. 建立counts数组

    7c27b4a77c3ab2ed317698d46ad6779e.png

    2. 倒序遍历原待排序数组,按升序排列

    bfa3f2da654922782fa0c05f234436de.png

    Java实现

    这里给出计数排序在Java下的实现:

    /**
     * 计数排序
     */
    public class CountingSort {
        ...
        /**
         * 升序排列 (稳定)
         */
        public static void sort2() {
            // 获取测试用例
            int[] array = getTestCase();
            int size = array.length;
    
            System.out.println("before sort: " + Arrays.toString(array) );
    
            // 求取最值
            int[] minMax = getMinMax(array);
            int min = minMax[0];
            int max = minMax[1];
    
            // 根据数据范围创建统计数组
            int k = max-min+1;
            int[] counts = new int[ k ];
    
            // 统计原数组中元素出现的次数
            for(int i=0; i<size; i++) {
                int dataInCountIndex = array[i] - min;    // 计算原数组元素在统计数组中的索引
                counts[dataInCountIndex] +=1;             // 统计该值次数
            }
    
            // 计算统计数组的累计值,即计算 统计数组中指定索引位置上的元素在排序后的位置
            // 如果该索引位置上有重复元素,则为重复元素所占的最大排序位置
            for(int i=1; i<k; i++) {
                counts[i] = counts[i-1] + counts[i];
            }
    
            int[] sortedArray = new int[size];  // 排序结果数组
            // 倒序遍历原数组,保证稳定性
            for(int i=size-1; i>=0; i--) {
                int dataInCountIndex = array[i] - min;  // 计算原数组元素在统计数组中的索引
                // 计算其排序后的位置, 因为数组索引从0开始计算,故应对排序位置减1
                // 例如,排在最前面的元素,排序位置为1,则其在数组中的位置索引应为0
                int sortIndex = counts[dataInCountIndex] - 1;
                sortedArray[sortIndex] = array[i]; // 将原数组元素放入排序后的位置上
                counts[dataInCountIndex]--;        // 下一个重复的元素,应排前一个位置,以保证稳定性
            }
    
            System.out.println("after sort: " + Arrays.toString(sortedArray) );
        }
        ...    
    }

    测试结果如下:

    f6ec525f52f20b9bdcb69ea9fb6de998.png

    特点

    复杂度、稳定性

    这里以稳定的计数排序进行说明:

    3d410cd2c761e570b3b957f5d75485d7.png

    缺陷

    1. 计数排序只能适用待排序元素为整数的场景
    2. 待排序元素的数值范围(极差)过大的情况下,计数排序会浪费大量空间,故一般不推荐使用计数排序

    参考文献

    1. 算法导论 · 第3版
    展开全文
  • 应急问题商户反馈会员管理功能无法按到店时间、到店次数、消费金额 进行排序,一直转圈圈或转完无变化,商户要以此数据来做活动,比较着急,请尽快处理,谢谢。线上数据量merchant_member_info 7000W条数据。me...
  • 一、代码图片(升序排序)二、实现思路1. 插入排序是将未排序的数据插入到已经排序的数据中。其实仔细发现其实插入排序是冒泡排序的改进版,冒泡排序是从头开始向后面比较,基本上每次都要从头比较到尾部,而插入...
  • 这两天看了几个排序算法,一直在思考一个问题,为什么归并排序就会比插入排序等初级排序算法的复杂度小呢?因为归并排序每次都把元素往正确...对于插入排序,最坏的情况就是A>B>C>D,这样要比较次数为6次,排序过程如下
  • 冒泡排序:就是按索引逐次比较相邻的两个元素,... 一直到最后一轮,比较了1次所以比较次数为递减:从n-1 到 1那么总的比较次数为:1+2+3+……+(n-1), 以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^...
  • 如果数据都在一个数组中,那么这里面会涉及到比较次数和数据的移动,这些都会影响到算法的效率,如果是链表,就需要考虑的是指针的指向。 下面的实例代码是对一个固定的数组进行排序升序和降序) 完整的代码:...
  • 基本思想:通过对排序序列从前到后(从下标较小的元素开始),依次比较相邻的元素,如果发现逆序的交换,值较大的元素逐渐从前移到后部,就像水底的气泡一样逐渐向上冒。 冒泡排序(如果从小到大) 趟数:一共...
  • 1.冒泡排序也叫起泡排序,气泡排序。基本思路(升序为例):比较第一个和第二个,逆序(data[0]>data[1])则交换,然后比较...最大比较次数n(n-1)/2 。时间复杂度为O(n**2) 冒泡排序是稳定的。#升序例子def mppx(data...
  • //数组元素值从小到大排序$arr=array(1,42,0,3,15,7,19,26);//定义一个中间变量$temp=0;//外层循环的次数for($i=0;$i//内层之间向右相邻的两个数组元素值进行比较for($j=0;$j//当后一个数组元素值大于前一个数组原...
  • 归并排序是一种渐进最优的基于比较排序的算法,归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~NlgN 原地归并的抽象方法 public static void merge(int[] a, int lo, int mid, int...
  • 作业4 编写函数,冒泡排序。对N个整数(数据由键盘输入)进行升序排列。 def maopao(arr): ... for j in range(le-1-i): #控制每轮比较次数 if(arr[j+1]<arr[j]): arr[j],arr[j+1]=arr[j+1],arr[j]
  • 对于比较排序,大家如果感兴趣,可以查看我的博客:http://10740184.blog.51cto.com/10730184/1774508计数排序思路:我们假设升序排序排序序列为2000,2001,3000,4000遍历序列,取出最小值min,最大值max,开辟一...
  • 算法设计与分析 李春葆 1_5_1 统计求最大、最小元素的平均比较次数 题目要求题目分析功能代码(C++) ...可以利用if…else…结构只比较次数,而不排序,我是用来排序算法,将数组进行升序排序,即可得到最大
  • 3.待排序数据量分别取n=10,30,50,100,1000时,计算每种算法在排序过程中对排序码的比较次数和元素的移动次数以及它们的和,按对选择、冒泡、直接插入、希尔、快速、堆、归并等几种排序算法进行升序排序
  • 前提不能把a和b合并之后再排序,并且采用最优算法让循环执行的次数最少。 这道题是近来比较火的算法题之一,我在58以及区块链的一家公司都遇到过,而且不仅前端,也可以作为py,java面试题。 在算法当中,优化就是...
  • 冒泡排序 算法流程 假设存在一个长度为N的数组,按照从左至右的顺序升序排列。首先,通过N-1次数 javascript代码 function bubbleSort(){ var arr = arguments[0]; for(var end=arr.length-1; end>0; end-...
  • 烧饼排序:递归实现 与 递归求最小翻转次数 看到一道比较有趣的题目: ...有一堆大小不同的烧饼叠在一起,每次执行的操作...求一组 翻转的序列,使得初始的烧饼大小序列被 升序排序 翻转的序列可以有多种 例: 输入 3...
  • 统计一个数字在排序数组中出现的次数。 分析:这个题目并没有说是升序的数组,但所有的解法都是默认升序的,这就有点坑了,默认升序的话会少很多麻烦。然后这道题有挺多思想的,最暴力的就是直接遍历,复杂度O(n),...
  • 排序就是使一串无序的数字经过处理之后变得有序,可以是升序,也可以是降序,算法中的排序主要是排升序排序需要考虑的因素: 时间复杂度:算法中的基本执行次数。 空间复杂度:临时占据存储空间大小的量度。衡量...
  • 比较常用的排序算法

    2014-07-01 18:14:50
    各种算法对同一数据排序所需要的关键字比较次数和关键字移动次数,至少使用5组数据进行比较。1)插入排序:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据...
  • Java 冒泡排序

    千次阅读 多人点赞 2021-03-28 13:39:12
    特点: 升序排序中每一轮比较会把最大的数沉到最底,所以每一轮比较次数都会比上一轮少一次。 为了方便大家理解,我做了一张动图来演示这一过程。 冒泡排序动画演示: 思路分析: 如上图所示, 黄,绿,蓝,红 分别...
  • 实验要求:输入一串数组,再输入一个数字,返回比较次数以及该数字是否在数组中 二分查找的原理 首先要有一个有序的列表,如果列表无序先用排序算法对无序列表进行排序。 假设有序列表为升序的,首先找到序列的中间...
  • 选择排序算法

    2019-04-03 16:34:00
    选择排序(Selection sort)是一种相对简单的排序算法。 1 什么是选择排序 它的工作原理是根据升序或者降序的需求...针对待排序的元素进行升序排序 待排序的元素如下 arr: 23 42 5 17 35 使用变量index记录最小...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 309
精华内容 123
关键字:

升序排序比较次数