精华内容
下载资源
问答
  • 时间复杂度 最优:O(nlog(n)) 最差:O(n^2) 平均:O(nlog(n))合并排序合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。 稳定:...

    快速排序

    稳定:否
    时间复杂度
    最优:O(nlog(n))
    最差:O(n^2)
    平均:O(nlog(n))

    合并排序

    合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。
    稳定:是
    时间复杂度:
    最优:O(nlog(n))
    最差:O(nlog(n))
    平均:O(nlog(n))

    桶排序

    桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序,或递归调用桶排序。
    时间复杂度
    最优:Ω(n + k)
    最差: O(n^2)
    平均:Θ(n + k)

    基数排序

    基数排序类似于桶排序,将元素分发到一定数目的桶中。不同的是,基数排序在分割元素之后没有让每个桶单独进行排序,而是直接做了合并操作。
    时间复杂度
    最优:Ω(nk)
    最差: O(nk)
    平均:Θ(nk)

    附一张查的图表:
    排序算法时间复杂度

    展开全文
  • 基数排序的思想 基数排序基数排序的思想是把位数相同的一组数组...注意:基数排序每次位的比较可以使用线性排序的方式,比如桶排序或者计数排序,因为它们的时间复杂度为O(n),而且每轮的比较需要保证每次比较数...

    基数排序的思想

    基数排序,基数排序的思想是把位数相同的一组数组依次从后往前比较其每一位上的大小,经过几轮比较使得数据达到有序的做法。比较的次数跟数据的位数有关系。比如要比较一组手机号码从小到大排列,可以比较手机号每一位大小,然后比较11次,手机号达到有序。

    注意:基数排序每次位的比较可以使用线性排序的方式,比如桶排序或者计数排序,因为它们的时间复杂度为O(n),而且每轮的比较需要保证每次比较数据的稳定性,不然基数排序就无法完成。

    图解

    代码

    package com.study.algorithm.sort;
    
    public class RadixSort {
    
        /**
         * 基数排序
         *
         * @param arr
         */
        public static void radixSort(int[] arr) {
            int max = arr[0];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                }
            }
    
            // 从个位开始,对数组arr按"指数"进行排序
            for (int exp = 1; max / exp > 0; exp *= 10) {
                countingSort(arr, exp);
            }
        }
    
        /**
         * 计数排序-对数组按照"某个位数"进行排序
         *
         * @param arr
         * @param exp 指数
         */
        public static void countingSort(int[] arr, int exp) {
            if (arr.length <= 1) {
                return;
            }
    
            // 计算每个元素(位0~9)出现的个数
            int[] c = new int[10];
            for (int i = 0; i < arr.length; i++) {
                c[(arr[i] / exp) % 10]++;
            }
    
            // 计算排序后的位置
            for (int i = 1; i < c.length; i++) {
                c[i] += c[i - 1];
            }
    
            // 临时数组r,存储排序之后的结果
            int[] r = new int[arr.length];
            for (int i = arr.length - 1; i >= 0; i--) {
                r[c[(arr[i] / exp) % 10] - 1] = arr[i];
                c[(arr[i] / exp) % 10]--;
            }
    
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r[i];
            }
        }
        public static void printArr(int[] arr,int n){
            for (int i = 0; i < n ; i++) {
                System.out.print("["+arr[i]+"]");
            }
        }
        public static void main(String[] args) {
            int[] arr={11255 ,45652,22545,54454,55211,45686,12125,45654};
            radixSort(arr);
            printArr(arr,8);
    
        }
    }

    基数排序的时间复杂度

    基数排序每一位的比较可以使用线性排序,比如桶排序或者计数排序,当然需要保证如计数排序的稳定性。每次排序时间复杂度O(n),那么如果有k位,则时间复杂度为O(k*n),如果k不大比如手机号11位,那么时间复杂度就是O(n)

    基数排序的稳定性

    基数排序是稳定排序算法

    基数排序是原地排序算法吗?

    基数排序基于线性排序如计数排序,所以不是原地排序算法。

    基数排序的应用场景

    基数排序对数据有要求,要能够将数据分割成独立的位。每一位的数据范围不能太大,要能够使用线性排序来实现。基数排序数据的长度要相等,不等的话需要补齐。

    展开全文
  • 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket ...其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

            基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。


    算法分析


         主要思想:

            基数排序的实现虽然有很多,但是基本思想就是把元素从个位排好序,然后再从十位排好序,,,,一直到元素中最大数的最高位排好序,那么整个元素就排好序了。

                    比如:2,22,31,1221,90,85,105

            个位排序:90,31,1221,2,22,85,105

            十位排序:2,105,1221,22,31,85,90

            百位排序:2,22,31,85,90,105,1221

            千位排序:2,22,31,85,90,105,1221

             注意:每次排序都是在上次排序的基础上进行排序的,也就是说此次排序的位数上他们相对时,就不移动元素(即顺序参数上一个位数的排序顺序)


        主要步骤:

            1、把所有元素都分配到相应的桶中

           2、把所有桶中的元素都集合起来放回到数组中

           3、依次循环上面两步,循环次数为最大元素最高位数


        代码分析:

            参考下图

         1、竖  0~9:表示桶个数(每个位数上的数字都在0到9之间);

         2、行 0~length:0 表示在某个桶内有多少个元素;

         3、比如:所有元素中个位为5的有两个元素,5 , 95;那么在下图中存放,分别是:(5,0) = 2;(5,1) = 5;(5,2)= 95;



    代码实现

     #include<stdio.h>
     #include<stdlib.h>
     
     #define LEN 10
                              
     // 打印数组元素
     void print_array(int *array, int length)
     {
         int index = 0;
         printf("array:\n");
         for(; index < length; index++){
             printf(" %d,", *(array+index));
         }
         printf("\n\n");
     }
     
    // 得到数组元素中最大数,并且计算其位数个数
     void getPosCount(int *array, int length, int *posCount)
     {
         int max, index;
         for (max = *array, index = 0; index < length; index++){
             if ( max < *(array + index)) max = *(array + index);
         }
     
         *posCount = 0;
         while(max){
             max = max / 10;
             (*posCount)++;
         }
     }
                              
    void radixSort(int *array, int length)
     {
         int* tmpArray[LEN];// 定义桶个数 0~9 共10个
         int index, pos, posCount, element, elementNum, tmp, log = 1;  
     
         for (element = 0; element < LEN; element++){// 每个桶最大能装length个元素,预防所有元素都是同一个数
             tmpArray[element] = (int*)malloc((sizeof(int))*(length + 1));
             tmpArray[element][0] = 0;// 初始化为0
         }
     
         getPosCount(array, length, &posCount);// 把最高位数存放到posCount中
     
         for (pos = 0; pos < posCount; pos++){// 从个位 ~ 十位 ~ 百位 。。。依次排序
     
             for (element = 0; element < length; element++){// 把元素放到桶里  分配动作
                 tmp = ++tmpArray[ (array[element] / log ) % 10][0];
                 tmpArray[ (array[element] / log) % 10][tmp] = array[element];
             }
     
             for (index = 0, element = 0; (element < LEN) && (index < length); element++){
                 for (elementNum = 1; elementNum <= tmpArray[element][0]; elementNum++)
                     array[index++] = tmpArray[element][elementNum];
                 tmpArray[element][0] = 0;
             }
             log = log * 10;
         }
     }
                              
     int main(void)
     {
         int array[] = {2,  5, 337, 24, 10000, 5, 30, 123, 3, 9, 100, 1};
         //int array[] = {2,  5, 3, 4, 1, 5, 0, 2, 3, 9, 1, 7, 8, 6};
         //int array[] = {2,  5, 3, 4, 1, 5, 5, 55555, 9, 5, 7, 5, 6};
         int length = (sizeof(array)) / (sizeof(array[1]));
         print_array(array, length);
         radixSort(array, length);
         print_array(array, length);
     
         return 0;
     }

            运行结果:

            


    时间复杂度

            该算法所花的时间基本是在把元素分配到桶里和把元素从桶里串起来;把元素分配到桶里:循环 length 次;
           把元素从桶里串起来:这个计算有点麻烦,看似两个循环,其实第二循环是根据桶里面的元素而定的,可以表示为:k×buckerCount;其中 k 表示某个桶中的元素个数,buckerCount  则表示存放元素的桶个数;
           有几种特殊情况:
           第一、所有的元素都存放在一个桶内:k = length,buckerCount = 1;
           第二、所有的元素平均分配到每个桶中:k = length/ bukerCount,buckerCount = 10;(这里已经固定了10个桶)
           所以平均情况下收集部分所花的时间为:length (也就是元素长度 n)

           综上所述:
           时间复杂度为:posCount * (length  + length) ;其中 posCount 为数组中最大元素的最高位数;简化下得:O( k*n ) ;其中k为常数,n为元素个数;

    空间复杂度

            该算法的空间复杂度就是在分配元素时,使用的桶空间;所以空间复杂度为:O(10 × length)= O (length)

    计数法基数排序


         主要思想:

            因为基数排序是根据个位是排序好,然后再根据十位数排序好,依次类推,当最后一个位数排序好时,所有的元素顺序都排序好了。又根据计数排序的算法可以得知,在限制元素的情况下,可以知道计数排序的时间复杂度为  O(n);所有如果利用计数排序的原理的实现基数排序,那么时间复杂度是不是可以降低呢?

             注意:如果不知道计数排序的,可以先大概了解下:http://blog.csdn.net/yuzhihui_no1/article/details/44561487

    代码实现

    #include<stdio.h>
    #include<stdlib.h>
     
     void print_array(int *array, int length)
     {
         int index = 0;
         printf("array:\n");
         for(; index < length; index++){
             printf(" %d,", *(array+index));
         }
         printf("\n\n");
     }
    
     void getCount(int *array, int length, int *count)
     {
         int max, index;
    
         for (max = *array, index = 0; index < length; index++){
             if ( max < *(array + index)) max = *(array + index);
         }
     
         *count = 0;
         while(max){
             max = max / 10;
             (*count)++;
         }
     }
     
     void radixSort(int *array, int length)
     {
         int *tmpArray = (int*)malloc(sizeof(int)*(10));
         int tmp[length];
         int i, j, count, log = 1;
     
         getCount(array, length, &count);
         for (j = 0; j < count; j++){ // 循环最大位数次
     
             for (i = 0; i < 10; i++)tmpArray[i] = 0;// 初始化数组
     
             for (i = 0; i < length; i++) tmpArray[ (array[i] / log) % 10 ]++;// 元素值对应桶标记
     
             for (i = 1; i <= 10; i++) tmpArray[i] += tmpArray[i-1];// 统计大于各元素的个数
     
             for (i = length - 1; i >= 0; i--){ // 按照指定位数对元素进行排序
                 tmp[tmpArray[ (array[i] / log) % 10] - 1] = array[i];
                 tmpArray[ (array[i] / log) % 10 ]--;
             }
     
             for (i = 0; i < length; i++) array[i] = tmp[i];// 把排序好的元素放回到元素数组中
             log = log * 10;
         }
     
         free(tmpArray);// 释放内存
     }
     
     int main(void)
     {
         //int array[] = {2,  5, 337, 24, 10000, 5, 30, 123, 3, 9, 100, 1};
         int array[] = {2,  5, 3, 4, 1, 5, 0, 2, 3, 9, 1, 7, 8, 6};
         int length = (sizeof(array)) / (sizeof(array[1]));
         print_array(array, length);
         radixSort(array, length);
         print_array(array, length);
     
         return 0;
     }

            运行结果:

            


    时间复杂度

     
    

            这个时间复杂度比较好计算:count * length;其中 count 为数组元素最高位数,length为元素个数;所以时间复杂度:O( k*n )


    空间复杂度

            空间复杂度是使用了两个临时的数组:10 + length;所以空间复杂度:O(n)


            转载请注明作者和原文出处,原文地址:http://blog.csdn.net/yuzhihui_no1/article/details/44594415
            若有不正确之处,望大家指正,共同学习!谢谢!!!


    展开全文
  • 时间复杂度O(N)的排序:计数排序,桶排序,基数排序 时间复杂度O(N)的排序:计数排序,桶排序,基数排序 1. 计数排序 2. 桶排序 3. 基数排序 4. 本文代码链接:https://github.com/aninstein/HappyPython 1. ...

    时间复杂度O(N)的排序:计数排序,桶排序,基数排序



    1. 计数排序

    计数排序,顾名思义,这个排序的主要作用并不是排序,而是进行计数。
    计数排序用于数据量内容固定,且数据范围较小的情况,对需要排序的数列进行计数;比如对学生考试分数进行排序,分数值是一个固定的范围0-100,且数据范围不大,则可以使用计数排序。
    计数排序步骤:

    1. 如果数据内容是正整数,则可以创建一个数组,如果是其他类型的数据,则可以创建一个map
    2. 遍历需要排序的数据,按照下标或者map的key,计算同一个数据出现的次数
    3. 遍历数组或者map,按照排序结果生成数据
    def count_sort(data, start=0, end=100):
        """
        计数排序
        :param data:
        :param start: 数据范围起始
        :param end: 数据范围结束
        :return:
        """
        count_list = [0 for i in range(end-start)]
        for i in data:
            count_list[i-start] += 1
    
        ret_data = []
        for i, count in enumerate(count_list):
            if not count:
                continue
            ret_data.extend([i+start] * count)
        return ret_data
    

    输出结果:

    input: [1, 4, 5, 1, 5, 8, 7, 5, 9, 6, 7, 4, 5, 6, 7, 0]
    output: [0, 1, 1, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 7, 8, 9]
    

    2. 桶排序

    桶排序,先准备好一个数据范围,先把相关的数据分在不同的“桶”中,再对桶中的小批量数据进行输出排序输出。

    1. 准备好固定的数据范围,比如输入数据范围是:1-10000,我们可以准备100个桶,即第一个桶范围是1-100,第二个桶是101-200···
    2. 遍历数据,把对应范围的数据放到桶中
    3. 遍历桶,取出桶中的数据,然后进行排序输出

    有此我们可以把桶排序的算法分为三部分:

    • 生成桶:针对数据范围生成合适的桶这个操作是决定桶排序的时间复杂度的主要因素
    • 把数据放进对应的桶中:数据放入桶中的操作算法有很多,比如:
      • 除了if/else if语句
      • switch/case语句
      • 向下取整求取浮点数范围的方法
      • 除以10、100、1000这样的大范围数划分范围
    • 对于已经放进桶中的数据进行排序:因为此时桶中的数据内容已经相对来说比较小了,可以使用插入排序等排序方法,当然要是不嫌麻烦也可以使用快排等时间复杂度为O(nlogn)的方法

    桶排序适用于:

    • 数据内容不固定,可以是浮点的也可以是整型的,只需要动态计算桶的大小即可
    • 数据的范围有限
    # -*- coding: utf-8 -*-
    # author: www.lichangan.com
    
    """
    桶排序
    1)在额外空间充足的情况下,尽量增大桶的数量
    2)使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
      个人理解,如果都是整数还可以用计数排序来计数统计然后排序,但是如果是一个连续空间内的排序,即统计的是一个浮点类型的数组成的数组,那么,就无法开辟一个对应的空间使其一一对应的存储。此时,我们需要新建一个带有存储范围的空间,来存储一定范围内的元素
    空间复杂度:O(n)
    时间复杂度: O(n)
    稳定
    """
    
    
    def bucket_sort(arr, max_num):
        """
        本算法是对浮点数进行排序,此处的放入桶中的方法为对浮点数取整
        """
        buf = {i: [] for i in range(int(max_num)+1)}  # 不能使用[[]]*(max+1),这样新建的空间中各个[]是共享内存的
        arr_len = len(arr)
        for i in range(arr_len):
            num = arr[i]
            buf[int(num)].append(num)  # 将相应范围内的数据加入到[]中
        arr = []
        for i in range(len(buf)):
            if buf[i]:
                arr.extend(sorted(buf[i]))  # 这里还需要对一个范围内的数据进行排序,然后再进行输出
        return arr
    
    
    if __name__ == "__main__":
        lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
        print(bucket_sort(lis, max(lis)))
    

    输出结果:

    input: [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
    output: [1.55, 2.1, 2.12, 2.2, 2.7, 2.9, 3.1, 3.3, 3.5, 4.2, 4.456, 5.2, 5.33, 6.0, 6.12]
    

    3. 基数排序

    基数排序(LDS),只适用于整型排序,或者有固定小数点位数的浮点型数据排序,其概念就是,根据不同位数的数字进行排序,最终得到排序结果。

    1. 先从最小的位数开始进行排序,对于排序的结果存于对应的队列中
    2. 遍历0-9的栈,把数据弹出成为新的数列
    3. 对下一个位数的数据重复上述操作
    4. 直到所有的位数的都被轮完,从队列里面取出的数据即有序数据
    def radix_sort(data):
    
        if not data:
            return []
        max_num = max(data)  # 获取当前数列中最大值
        max_digit = len(str(abs(max_num)))  # 获取最大的位数
    
        dev = 1  # 第几位数,个位数为1,十位数为10···
        mod = 10  # 求余数的除法
        for i in range(max_digit):
            radix_queue = [list() for k in range(mod * 2)]  # 考虑到负数,我们用两倍队列
            for j in range(len(data)):
                radix = int(((data[j] % mod) / dev) + mod)
                radix_queue[radix].append(data[j])
    
            pos = 0
            for queue in radix_queue:
                for val in queue:
                    data[pos] = val
                    pos += 1
    
            dev *= 10
            mod *= 10
        return data
    

    结果:

    input: [58, 14, 5, 16, 78, 2, 123, 158, 753, 32, 1, 9, 5]
    output: [1, 2, 5, 5, 9, 14, 16, 32, 58, 78, 123, 158, 753]
    
    展开全文
  • 要求: 在线性时间复杂度 和 空间复杂度 线性时间复杂度 >> O(n)O(n)O(n) 快排,归并复杂均为 O(nlongn)O(nlongn)O(nlongn) >> 不属于线性时间复杂度。 所以这道题解法必然要用 >> 桶排序 ( O(n)...
  • 文章目录一、写在前言二、排序(一)基数排序1、思路讲解2、代码实现三、排序算法时间复杂度比较四、结束语 一、写在前言 我哭了,写的博客没有保存,睡了一觉之后电脑不知道怎么关机了。啊啊啊啊蓝瘦想哭,木有心情...
  • 什么是基数排序? (一)基数排序的思想:把待排序的整数按位分,分为个位,十位.....从小到大依次将位数进行排序。实际上分为两个 过程:分配和收集。  分配就是:从个位开始,按位数从小到大把数据排好,分别...
  • 排序时间复杂度

    2019-07-02 17:09:59
    冒泡,简单选择,直接插入, o(n方) 希尔 o(n的1.5次方) 快排,堆,归并 o(n log n) 桶,基数,计数 o(n)
  • 算法的选择有很多,这里我们选择使用 基数排序,这是一种时间复杂度为 O(n) 的排序算法,关于它的介绍,也可以参考我的这一篇博文:https://blog.csdn.net/afei__/article/details/82971310 不考虑大小写的话,我们...
  • 常用排序算法–冒泡排序及改进和插入排序时间复杂度分析 常用排序算法冒泡排序及改进和插入排序时间复杂度分析 排序及常见排序算法 插入排序时间复杂度分析 冒泡排序 冒泡排序的改进 排序及常见排序...
  • **时间复杂度(维基百科)** ![维基百科](https://img-ask.csdn.net/upload/201909/02/1567419774_573153.png) 对{123,423,412,023}进行基数排序,B是10,蓝色部分N是10^3 对{as,qe,sd,fa,as,ws}进行基数排序...
  • 排序 时间复杂度

    千次阅读 2010-10-03 12:30:00
    冒泡排序是稳定的,算法时间复杂度是O(n ^2)。 2.2 选择排序(Selection Sort) 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,...
  • 现在分情况讨论每种情况下的大小 平均情况: n平方>n1.3次方>nlog2n,证明如下: ...至于基数排序,可以参考下这篇文章:https://cloud.tencent.com/developer/news/387473(大哥,兄弟我第一次写博客,...
  • 此句表示时间复杂度为O(nlogn)的排序,“快”表示快速排序,“些”表示希尔排序,“归”表示归并排序,“队”表示堆排序,其他排序均为O(n²),特殊的基数排序为O(nlog(r)m)。 注:快排的最坏情为O(n²),此时待排序...
  • 本文我们将继续介绍一种线性时间复杂度的排序算法--基数排序,这种排序算法的时间复杂度为Θ(d(n+k)),这种排序基于我们之前将的计数排序,其中n表示待排序列的规模,d表示待排序列的最大位数,k表示每一位数的范围...
  • 排序时间复杂度

    千次阅读 2017-10-31 10:31:35
    排序方法 最好情况 最坏情况 平均情况 稳定性  冒泡排序 O(n) O(n2) O(n2) 稳定 快速排序
  • 2、 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数 二、 辅助记忆 1、时间复杂度记忆 冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为O(n * n)O(n * n)(一遍找...
  • 排序大体分为两类:比较排序和非比较排序一 各个排序的基本实现1.直接插入排序和希尔排序//整体思路:往一段有序区间插入元素,end标记为有序区间的最后一个元素下标,要插入的元素下标为end+1此处就称tmp,先把他...
  • 常用排序算法复杂度

    2017-09-22 16:11:37
    常用排序算法时间复杂度、空间复杂度总结。包括:冒泡排序、快速排序、选择排序、堆排序、插入排序、Shell排序、归并排序、基数排序
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2018-12-31 14:09:13
    排序算法分类  排序大的分类可以分为两种:内排序和外排序。  放在内存的称为内排序,...排序算法的时间复杂度和空间复杂度 排序算法 平均时间复杂度 最坏时间复杂度 ...
  • 桶、计数、基数排序算法中,除了桶排序在桶粒度大于1时要通过比较排序外,其他两种排序都不需要使用比较就能使数列完成排序,这也是为什么时间复杂度可以达到线性O(n)的原因。 桶排序 桶排序的求解思路为找出数列...
  • 【算法复习3】时间复杂度 O[n] 的排序 桶排序 计数排序基数排序桶排序(Bucket sort)时间复杂度O(n)苛刻的数据计数排序(Counting sort)基数排序(Radix sort)评论区大佬的总结 桶排序(Bucket sort) 将要排序的...
  • 2 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数。 辅助记忆 时间复杂度记忆- 冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为O(n2)O(n2)(一遍找元素O(n)O(n),...
  • 文章目录1 冒泡排序2 选择排序3 插入排序4 归并排序5 快速排序6 堆排序7 桶排序8 基数排序9 外部排序 1 冒泡排序 时间复杂度:O(n*n) 稳定性:稳定 空间复杂度:O(1) 2 选择排序 时间复杂度:O(n*n) 稳定性:不稳定 ...
  • 线性时间的排序算法 大学时学过的一些排序算法,像插入排序(直接插入排序,折半插入排序,...本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序。它们将突破比较排序的Ω(nlgn)下界,以线性时间运行。...
  • 排序算法复杂度

    千次阅读 2019-11-25 15:27:58
    时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 插入 稳定 希尔 不稳定 选择 不稳定 堆 ...
  • 八种排序算法的时间复杂度复杂度

    万次阅读 多人点赞 2018-09-21 15:17:21
    基数排序是稳定的 选择排序、快速排序、希尔排序、堆排序是不稳定的   2、时间复杂度 最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度最小O(n*log2n),其他都是O(n2) 排序法 平均时间 ...
  • 算法的时间复杂度与初始序列无关的是:选择排序、堆排序、归并排序、基数排序 算法的排序趟数与初始序列无关的是:插入排序、选择排序、基数排序 堆排序 (1)堆是一颗完全二叉树; (2)小(大)顶堆中的每一个节点都不...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,782
精华内容 11,112
关键字:

基数排序时间复杂度