精华内容
下载资源
问答
  • 归并排序和快速排序的时间复杂度
    2022-03-23 18:57:16

    快速排序和归并排序的时间复杂度分析
    点解链接

    更多相关内容
  • 归并排序: 引述:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列 1.两路归并排序算法思路 ①把...

    归并排序:

    引述:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列

    1.两路归并排序算法思路

    ①把 n 个记录看成 n 个长度为1的有序子表

    ②进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表

    ③重复第②步直到所有记录归并成一个长度为 n 的有序表为止

    归并图集

    2.实现步骤

    分为两个步骤

    现将数组中的元素拆分成一个一个的子集,使用合并将子集变成有序

    拆分是很简单的操作,每次都按照原有的数组元素进行一半拆分 开始元素的位置+最后一个元素的位置/2

    如何将将二个有序数列合并。只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

    import java.util.Arrays;
    
    public class MergeSort {
    	public static void main(String[] args) {
    		  int[] array = new int[10];
    	        for(int i = 0;i<array.length;i++){
    	        	array[i] = (int)(Math.random()*100);
    	        }
    	    System.out.println(Arrays.toString(array));  
    		mergeSort(array, 0, array.length - 1);
    		 System.out.println(Arrays.toString(array));
    	}
     
    	public static void mergeSort(int[] array, int left, int right) {
    		if (left < right) {
    			int center = (left + right) / 2;
    			// 将数组拆分为两份,并递归拆分子数组,直到数组中只有一个元素
    			mergeSort(array, left, center);
    			mergeSort(array, center + 1, right);
    			// 合并相邻数组
    			merge(array, left, center, right);
    			
    		}
    	}
     
    	// 合并子数组的函数
    	public static void merge(int[] array, int left, int center, int right) {
    		// 临时数组,用于排序
    		int[] tempArray = new int[array.length];
    		// 用于将排好序的临时数组复制回原数组
    		int mark = left;
    		// 第二个数组的左端
    		int mid = center + 1;
    		// 用于临时数组的下标
    		int tempLeft = left;
    		while (left <= center && mid <= right) {
    			// 从两个子数组中取出最小的放入临时数组,即按从小到大的顺序重新排布
    			if (array[left] <= array[mid]) {
    				tempArray[tempLeft++] = array[left++];
    			} else {
    				tempArray[tempLeft++] = array[mid++];
    			}
    		}
    		// 剩余部分依次放入临时数组
    		while (left <= center) {
    			tempArray[tempLeft++] = array[left++];
    		}
    		while (mid <= right) {
    			tempArray[tempLeft++] = array[mid++];
    		}
    		// 将中间数组中的内容复制回原数组
    		while (mark <= right) {
    			array[mark] = tempArray[mark++];
    		}
    	}
    }
    
    

    快速排序:

    快速排序,顾名思义,是一种速度快,效率高的排序算法。

    快排原理:

    ​ 在要排的数(比如数组array)中选择一个中心值key(比如array[0]),通过一趟排序将数组array分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。

    ​ 整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。

    ​ 一趟排序的方法:

    假设要排的数组为:array[8] ={5,2,8,9,2,3,4,9}

    ​ 选择 key = 5, 开始时 i=0,j=7

    index 0 1 2 3 4 5 6 7

    开始: 5 2 8 9 2 3 4 9

    ​ i j

    第一次找 5 2 8 9 2 3 4 9

    ​ i j

    交换: 5 2 4 9 2 3 8 9

    ​ i j

    第二次找 5 2 4 9 2 3 8 9

    ​ i j

    交换: 5 2 4 3 2 9 8 9

    ​ i j

    第三次找 5 2 4 3 2 9 8 9

    ​ ij

    调整key: 2 2 4 3 5 9 8 9

    第1步:找基准值

    所谓的基准值,顾名思义就是以它为基准进行比大小。通常来说,我们选取数组的第一个数为基准值。在数组array里基准值就是5.

    第2步:比大小

    先从数组的最右边开始往左边找比基准值小的第一个数,然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢?因为现在我们要把数组从小到大排序,所以要找出比基准值小的数放到基准值的左边,找出比基准值大的数放在基准值的右边。
    那么在数组array里,从左往右找,第一个比5大的数就是8,我们把它的坐标记为i;从右往左找,第一个比5小的数就是4,我们把它的坐标记为j。

    第3步:交换

    找到之后,如果这个时候i<j,那么就交换这两个数,因为i=2,j=6,符合条件,将4和8进行交换。现在数组变成了int[]a={5,2,4,9,2,3,8,9};
    如果j>=i,那么不做处理
    为什么还要判断i和j的大小呢?就像第二步说的,我们要找出比基准值小的数放到基准值的左边,找出比基准值的数放在基准值的右边。所以如果i<j的话,交换就达到目的了,如果i>=j,比基准值小的数就在基准值的左边,比基准值大的数已经在基准值的右边了,这时候就没必要交换了。

    第4步:继续查找

    在i<j的前提下,继续向右查找比基准值大的数,往左找比基准值小的数,然后交换。
    在我们的例子中,9和3、符合交换的条件,所以数组就变成了
    int[]a={5,2,4,3,2,9,8,9};这时候i=3,j=5

    第5步:交换基准值到合适的位置

    当查找继续进行,这时候i=j=4,已经不满足继续查找和交换的条件了,那么我们应该怎么办呢?答案就是把array[4]和基准值交换,因为i=j的时候说明已经到了一个分界线的位置,分界线左边的数比基准值小,分界线右边的数比基准值大,而这个分界线就是我们的基准值,所以把它和array[i]交换,这时候数组就变成:
    int[]a={2,2,4,3,5,9,8,9};

    第6步:重复

    对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

    import java.util.Arrays;
    
    public class QuickSort {  
        public static void main(String[] arrayrgs) {  
            //创建数组
            int[] array = new int[10];
            for(int i = 0;i<array.length;i++){
            	array[i] = (int)(Math.random()*100);
            }
            System.out.println(Arrays.toString(array));  
            //调用排序
            quickSort(array, 0 , array.length-1);  
            System.out.println(Arrays.toString(array));  
        }  
      
      
        public static void quickSort(int[] array, int start, int end) {  
            //1,找到递归算法的出口  
            if( start > end) {  
                return;  
            }  
            //2, 存储开始和末尾的位置
            int i = start;  
            int j = end;  
            //3,存储基准值
            int key = array[start];  
            //4,完成一趟排序  
            while( i< j) {  
                //4.1 ,从右往左找到第一个小于key的数  
                //要想降序只需要将> 修改成<
                while(i<j && array[j] > key){  
                    j--;  
                }  
                // 4.2 从左往右找到第一个大于key的数  
                //要想降序只需要将<= 修改成 >=
                while( i<j && array[i] <= key) {  
                    i++;  
                }  
                //4.3 交换  
                if(i<j) {  
                    int tmp = array[i];  
                    array[i] = array[j];  
                    array[j] = tmp;  
                }  
            }  
            // 4.4,调整key的位置  
            int p = array[i];  
            array[i] = array[start];  
            array[start] = p;  
            System.out.println(i);
            //5, 对key左边的数快排  
            quickSort(array, start, i-1 );  
            //6, 对key右边的数快排  
            quickSort(array, i+1, end); 
            
        }  
    }  
    

    时间复杂度

    我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示,即 T(n) 。
    此时为了 估算算法需要的运行时间 和 简化算法分析,我们引入时间复杂度的概念。

    定义:存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n)) 。

    算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。

    1.我们知道常数项对函数的增长速度影响并不大,所以当 T(n) = c,c 为一个常数的时候,我们说这个算法的时间复杂度为 O(1);如果 T(n) 不等于一个常数项时,直接将常数项省略。

    比如
    第一个 Hello, World 的例子中 T(n) = 2,所以我们说那个函数(算法)的时间复杂度为 O(1)。
    T(n) = n + 29,此时时间复杂度为 O(n)。
    

    2.我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的,同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高,所以我们直接忽略低此项。

    比如
    T(n) = n^3 + n^2 + 29,此时时间复杂度为 O(n^3)。
    

    3.因为函数的阶数对函数的增长速度的影响是最显著的,所以我们忽略与最高阶相乘的常数。

    比如
    T(n) = 3n^3,此时时间复杂度为 O(n^3)。
    

    综合起来:如果一个算法的执行次数是 T(n),那么只保留最高次项,同时忽略最高项的系数后得到函数 f(n),此时算法的时间复杂度就是 O(f(n))。为了方便描述,下文称此为 大O推导法。

    由此可见,由执行次数 T(n) 得到时间复杂度并不困难,很多时候困难的是从算法通过分析和数学运算得到 T(n)。对此,提供下列四个便利的法则,这些法则都是可以简单推导出来的,总结出来以便提高效率。

    1.对于一个循环,假设循环体的时间复杂度为 O(n),循环次数为 m,则这个循环的时间复杂度为 O(n×m)。

    void aFunc(int n) {
        for(int i = 0; i < n; i++) {         // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }
    

    此时时间复杂度为 O(n × 1),即 O(n)。

    2.对于多个循环,假设循环体的时间复杂度为 O(n),各个循环的循环次数分别是a, b, c…,则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。

    void aFunc(int n) {
        for(int i = 0; i < n; i++) {         // 循环次数为 n
            for(int j = 0; j < n; j++) {       // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
        }
    }
    

    此时时间复杂度为 O(n × n × 1),即 O(n^2)。

    3.对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度。

    void aFunc(int n) {
        // 第一部分时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("Hello, World!\n");
            }
        }
        // 第二部分时间复杂度为 O(n)
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    4.对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

    void aFunc(int n) {
        if (n >= 0) {
            // 第一条路径时间复杂度为 O(n^2)
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    printf("输入数据大于等于零\n");
                }
            }
        } else {
            // 第二条路径时间复杂度为 O(n)
            for(int j = 0; j < n; j++) {
                printf("输入数据小于零\n");
            }
        }
    }
    

    此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。

    时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析。

    一. 基础题

    void aFunc(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                printf("Hello World\n");
            }
        }
    }
    

    O(n^2)。

    二. 进阶题

    void aFunc(int n) {
        for (int i = 2; i < n; i++) {
            i *= 2;
            printf("%i\n", i);
        }
    }
    

    参考答案:
    O(log n)。

    三. 再次进阶

    long aFunc(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return aFunc(n - 1) + aFunc(n - 2);
        }
    }
    

    参考答案:
    O(2^n)。

    空间复杂度

    一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空
    间包括以下两部分。  
    (1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
    (2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))  其中n为问题的规模,S(n)表示空间复杂度。

    要注意的是递归算法的空间复杂度,假如递归深度为N*每次递归的辅助空间大小,如果每次递归的辅助空间为常数,则空间复杂度为O(N)

    空间复杂度:函数中创建对象的个数关于问题规模函数表达式,一般情况用O的渐进表示法表示。

    展开全文
  • 引言:(一)快速排序的最好情况O(nlogn...此时就和归并排序基本一致了:递归的第一层,n个数被划分为2个子区间,每个子区间的数字个数为n/2; 递归的第二层,n个数被划分为4个子区间,每个子区间的数字个数为n/4; 递

    引言:

    大家好,我是小星星,今天是三个月算法专栏第2天——快速排序和归并排序时间复杂度分析。

    一、快排时间复杂度分析

    快速排序的时间复杂度在O(nlogn)~ O(n^2)之间,下面我分别分析这两种情况:

    (一)快速排序的最好情况O(nlogn)

    快速排序的实现方式,就是在当前区间中选择一个x,区间中所有比x小的数都需要放到x的左边,而比x大的数则放到右边。在理想的情况下,我们选取的分界点刚好就是这个区间的中位数。也就是说,在操作之后,正好将区间分成了满足数字个数相等的左右两个子区间(快排是按照值的大小划分,个数可能相等,可能不等)。此时就和归并排序基本一致了:

    递归的第一层,n个数被划分为2个子区间,每个子区间的数字个数为n/2;
    递归的第二层,n个数被划分为4个子区间,每个子区间的数字个数为n/4;
    递归的第三层,n个数被划分为8个子区间,每个子区间的数字个数为n/8;
      …

    递归的第logn层,n个数被划分为n个子区间,每个子区间的数字个数为1;

    以上过程与归并排序基本一致,而区别就是,归并排序是从最后一层开始进行merge操作,自底向上;而快速排序则从第一层开始交换区间中数字的位置,是自顶向下的。但是,merge操作和快速排序的调换位置操作,时间复杂度是一样的,对于每一个区间,处理的时候,都需要遍历一次区间中的每一个元素。这也就意味着,快速排序和归并排序一样,每一层的总时间复杂度都是O(n),因为需要对每一个元素遍历一次。而且在最好的情况下,同样也是有logn层,所以快速排序最好的时间复杂度为O(nlogn)。

    (二)快速排序的最坏情况O(n^2)

    对于每一个区间,我们在处理的时候,选取的轴刚好就是这个区间的最大值或者最小值。比如我们需要对n个数排序,而每一次进行处理的时候,选取的轴刚好都是区间的最小值。于是第一次操作,在经过调换元素顺序的操作后,最小值被放在了第一个位置,剩余n-1个数占据了2~n个位置;第二次操作,处理剩下的n-1个元素,又将这个子区间的最小值放在了当前区间的第1个位置,以此类推…每次操作,都只能将最小值放到第一个位置,而剩下的元素,则没有任何变化。所以对于n个数来说,需要操作n次即n层,才能为n个数排好序。而每一次操作都需要遍历一次剩下的所有元素,这个操作的时间复杂度是O(n),所以总时间复杂度为O(n^2)。

    其实上面的过程,我们可以换一个角度理解:每次操作,找出最小值放到剩余区间的第一个位置,这不就是选择排序的实现方式吗?而选择排序的时间复杂度就是O(n ^ 2),所以上面的过程也就O(n^2)。

    二、归并排序时间复杂度分析

    归并排序的时间复杂度是O(nlogn),且这个时间复杂度是稳定的,不随需要排序的序列不同而产生波动。下面我来分析一下~

    假设我们需要对一个包含n个数的序列使用归并排序,并且使用的是递归的实现方式,那么过程如下:

    递归的第一层,将n个数划分为2个子区间,每个子区间的数字个数为n/2;
    递归的第二层,将n个数划分为4个子区间,每个子区间的数字个数为n/4;
    递归的第三层,将n个数划分为8个子区间,每个子区间的数字个数为n/8;
      …

    递归的第logn层,将n个数划分为n个子区间,每个子区间的数字个数为1;
      在整个归并排序的过程中,每一层的子区间,长度都是上一层的1/2。分析可知,当子区间的长度为1时,共划分了logn层。而归并排序的merge操作,则是从最底层开始(子区间为1的层),对相邻的两个子区间进行合并,过程如下:

    在第logn层(最底层),每个子区间的长度为1,共n个子区间,每相邻两个子区间进行合并,总共合并n/2次。n个数字都会被遍历一次,所有这一层的总时间复杂度为O(n);
      …

    在第2层,每个子区间长度为n/4,总共有4个子区间,每相邻两个子区间进行合并,总共合并2次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);
    在第1层,每个子区间长度为n/2,总共有2个子区间,只需要合并一次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);
      通过上面的过程我们可以发现,对于每一层来说,在合并所有子区间的过程中,n个元素都会被操作一次,所以每一层的时间复杂度都是O(n),共有logn层,所以归并排序的时间复杂度就是O(nlogn)。

    三、写在最后

    学习算法的重点是学习编程思维,这件事值得我们慢慢去做,做很久很久。漫漫长路,感谢有你~

    如果各位大佬发现哪里有问题的话,欢迎指出~

    如果你觉得我这篇文章对你有帮助的话,欢迎你订阅我的算法专栏并给我三连关注支持一下~,你们的支持是我更新的动力,感谢各位!

    展开全文
  • 时间复杂度: 用T(n)T(n)T(n)表示排大小为nnn的数组的时间:T(n)=2T(n/2)+nT(1)=1T(n)=2T(n/2)+n T(1)=1T(n)=2T(n/2)+nT(1)=1 关于如何解这个递归方程,这里介绍其中一种,我们假设n是2的幂: 首先,我们递推关系式的...

    归并排序

    • 归并排序:利用分治的思想,先排左边一半,再排右边一半,最后再将两边有序的合并起来。
    • 时间复杂度: 用 T ( n ) T(n) T(n)表示排大小为 n n n的数组的时间: T ( n ) = 2 T ( n / 2 ) + n T ( 1 ) = 1 T(n)=2T(n/2)+n\quad T(1)=1 T(n)=2T(n/2)+nT(1)=1

    关于如何解这个递归方程,这里介绍其中一种,我们假设n是2的幂:

    • 首先,我们递推关系式的两边同时除以n,得到: T ( n ) n = T ( n / 2 ) n / 2 + 1 \frac{T(n)} {n}=\frac{T(n/2)}{n/2}+1 nT(n)=n/2T(n/2)+1
    • 因为该方程对2的幂的任意n是成立的,于是还可以写成:
    • T ( n / 2 ) n / 2 = T ( n / 4 ) n / 4 + 1 \frac{T(n/2)}{n/2}=\frac{T(n/4)}{n/4}+1 n/2T(n/2)=n/4T(n/4)+1
    • T ( n / 4 ) n / 4 = T ( n / 8 ) n / 8 + 1 \frac{T(n/4)}{n/4}=\frac{T(n/8)}{n/8}+1 n/4T(n/4)=n/8T(n/8)+1
    • T ( 2 ) 2 = T ( 1 ) 1 + 1 \frac{T(2)}{2}=\frac{T(1)}{1}+1 2T(2)=1T(1)+1
    • 此时,我们把这些式子的左边和右边统一加起来,会发现很多项都同时消掉了,我们称之为叠缩公式
    • 最后剩下: T ( n ) n = T ( 1 ) 1 + l o g n \frac{T(n)}{n}=\frac{T(1)}{1}+logn nT(n)=1T(1)+logn,此时 T ( n ) = n l o g n + n = O ( n l o g n ) T(n)=nlogn+n=O(nlogn) T(n)=nlogn+n=O(nlogn)

    快速排序

    • 快速排序的主要思想依然是分治
      1、从待排数组中选出一个枢纽元( p i v o t pivot pivot);
      2、然后将数组分割为两个不相交集合 s 1 , s 2 s1,s2 s1,s2,左半边集合的元素都小于等于 p i v o t pivot pivot,右半边集合元素都大于等于 p i v o t pivot pivot
      3、最后,分别排序左半边、右半边。

    • 快速排序的枢纽元选择策略一般为:
      1、三数中值分割法:即选择待排数组的左段、右段和中心位置的中值作为枢纽元。
      2、待排数组的第一个元素:但是这很可能会出现极坏的情况:那就是这个元素是这个数组里面最小的或者最大的,那么其他剩余元素要么被分进 s 1 s1 s1,要么被分进 s 2 s2 s2 T C : O ( n 2 ) TC:O(n^2) TCO(n2)。这种最坏的情况出现在整个数组是预排序的(非递增、非递减)。

    • 时间复杂度的关系为: T ( n ) = T ( i ) + T ( n − i − 1 ) + c n T(n)=T(i)+T(n-i-1)+cn T(n)=T(i)+T(ni1)+cn i i i为集合 s 1 s1 s1中的元素个数,分割数组也需要线性时间)

    • 那么先来分析下快速排序的最好情况:那就是分割完数组后,集合 s 1 , s 2 s1,s2 s1,s2中元素大小都一样。
      T ( n ) = 2 T ( n / 2 ) + c n T(n)=2T(n/2)+cn T(n)=2T(n/2)+cn,那么答案和刚才分析的归并排序是一样的,等式两边同时除以 n n n,然后利用缩叠公式,最后 T ( n ) = n + k n l o g n = O ( n l o g n ) T(n)=n+knlogn=O(nlogn) T(n)=n+knlogn=O(nlogn)

    • 然后说下刚才提到的可能出现的最坏情况(即每次除了枢纽元之外的元素全在 s 1 s1 s1 s 2 s2 s2): T ( n ) = T ( n − 1 ) + c n T(n)=T(n-1)+cn T(n)=T(n1)+cn
      我们用 n − 1 n-1 n1不断替换 n n n可以得到: T ( n − 1 ) = T ( n − 2 ) + c ( n − 1 ) , T ( n − 2 ) = T ( n − 3 ) + c ( n − 3 ) . . . T ( 2 ) = T ( 1 ) + c ( 2 ) T(n-1)=T(n-2)+c(n-1),T(n-2)=T(n-3)+c(n-3)...T(2)=T(1)+c(2) T(n1)=T(n2)+c(n1),T(n2)=T(n3)+c(n3)...T(2)=T(1)+c(2),依然是等式左右两边同时相加,得到: T ( n ) = c ( 2 + 3 + . . . + n ) , T ( n ) = O ( n 2 ) T(n)=c(2+3+...+n),T(n)=O(n^2) T(n)=c(2+3+...+n)T(n)=O(n2)

    • 最后,来说下平均情况,因为对于 s 1 s1 s1,每个大小都是等可能的,所以都有 1 n \frac {1}{n} n1的可能:
      在这里插入图片描述
      在这里插入图片描述

    展开全文
  • 两个重要的排序算法的时间复杂度比较。所用的代码比较简陋,使用控制台。
  • 八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码...
  • 归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子数组,直到子数组里面只有一个元素,那么就自然排好序了,可以总结为先排序再递归;归并排序:先什么...
  • 归并排序的空间复杂度

    千次阅读 2021-05-29 09:32:03
    (待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n^2)。)但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。 这是因为归并...
  • 如何计算归并排序时间复杂度? 什么是归并排序归并排序的概念十分简单,就是“分而治之”的思想。这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法 。 计算时间复杂度 关键是怎么计算时间复杂度...
  • 排序算法之 快速排序时间复杂度分析 排序算法之 堆排序及时间复杂度分析 归并排序 归并排序是建立在归并操作上的一种有效排序算法,该算法是采用分治法的一个典型应用。 这里的分治如何理解? 比如我们要统计本...
  • 归并排序快速排序时间复杂度均为O(nlogn),适合大规模的数据排序且很常用,它们都用到了分治思想,将大的问题分解成小问题来解决。接下来我们分别对其进行分析。 归并排序(Merge Sort) 思路:归并排序的核心...
  • 文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
  • 各种排序算法的稳定性,时间复杂度和空间复杂度总结:我们比较时间复杂度函数的情况:时间复杂度函数O(n)的增长...2.线性对数阶O(nlog2n)排序快速排序、堆排序和归并排序;3.O(n1+§)排序,§是介于0和1之间的整数。...
  • 本文通过二分查找并归排序为例,主要介绍时间O(logn)O(nlogn)这两个时间复杂度是怎么得出来的。O(1)、O(n)、O(n2)在此不做介绍了,O(n)、O(n2)就是for循环一次、二次,O(1)的话…就好像单例模式或者map吧。 首先...
  • 希尔排序本质上是对插入排序的一种优化,它包括了插入排序的简单,同时解决了插入排序每次只交换相邻两个元素的缺点。插入排序过程如下: 1.将数组按照一定的间隔分为多个子数组(每跳跃一定间隔取一个值组成一组...
  • 排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
  • (1)冒泡排序时间复杂度: 1.比较相邻的元素,如果第一个比第二个大(升序),就交换他们两个 2.对每一对相邻的元素做同样的工作,从开始到结尾的最后一对 这步做完后,最后的元素会是最大的数 3.针对所有的...
  • 归并排序快速排序背后的秘密

    千次阅读 2021-11-03 22:30:23
    此外,可以找到很多递归式,递推式来解释为什么归并排序时间复杂度是O(nlog⁡2n)O(n\log_2n)O(nlog2​n),在数学上确实也是那个理,但为什么分治就能带来效率的提高呢?到底省了哪里的消耗呢? 只要记住,基于比较...
  • 【算法】快速排序归并排序对比

    千次阅读 2021-07-27 21:51:09
    算法 系列博客、 一、时间复杂度、 二、空间复杂度、 三、排序稳定性、 三、局部有序与整体有序、
  • 这里我们要总结的排序算法主要有4个,分别是插入排序Insertion Sort、归并排序Merge Sort、快速排序Quick Sort、堆排序Heap Sort。 下面是四种排序算法具体介绍的文章。 插入排序: 十分重要的O(n^2)级别排序算法...
  • 时间复杂度 平均情况 时间复杂度 最好情况 时间复杂度 最坏情况 空间复杂度 插入排序 是 O(n²) O O(n²) O 希尔排序 (Shell) 是...
  • 前言之前介绍的插入排序与冒泡排序...下面将介绍基于分治策略的两种排序算法,分别是快速排序算法和归并排序算法,并对其进行时间复杂度分析改进。一、分治策略首先,我们先了解一下什么是分治策略。分治策略:如...
  • 1、归并排序 归并排序算法的核心思想:把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。具体过程如下图所示: 归并排序使用的就是分治思想。分治,...
  • 归并排序和快速排序

    千次阅读 多人点赞 2019-04-16 15:25:51
    一,归并排序 归并排序算法实现 算法思路: 如果要排序一个数组,我们先从数组中间把数组分成左数组右数组两部分,分别对左右数组进行排序,然后将排序好的数组合并成结果数组,排序就完成了,最后只需将结果数组...
  • 堆排序过程、时间复杂度及空间复杂度? 写出你所知道的排序算法及时空复杂度,稳定性? 快速排序 算法在数组中选择一个称为主元(pivot)的元素,将数组分为两部分,使得 第一部分中的所有元素都小于或等于主元,而第...
  • 戳蓝字“CSDN云计算”关注我们哦!作者 |奎哥责编 | 阿秃之前的文章...排序算法有很多,如:「冒泡排序」、「插入排序」、「选择排序」、「希尔排序」、「堆排序」、「归并排序」、「快速排序」、「桶排序」、「计数...
  • 归并排序和快排的空间复杂度对比

    千次阅读 2019-04-15 10:17:33
    归并排序和快排都用到了递归调用,但是因为递归函数所处的位置不一样,所以,导致需要的空间复杂度不一样。 其实递归调用占用的空间就是因为一个函数还没有进行完,那么去执行下一个递归的函数,那么上一个还没有...
  • 归并排序时间复杂度为什么为nlogn

    千次阅读 2021-02-17 23:00:49
    归并排序的递归过程如下,该递归树的高度为log2n(计算过程:假设待排序的数组元素个数为n,设高度为x,x意味着n个元素需要连续二分x次才剩下1个元素,即n/2^x=1,x=log2n),每一层的总比较次数为n,所以时间复杂度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,704
精华内容 19,881
关键字:

归并排序和快速排序的时间复杂度