精华内容
下载资源
问答
  • 插入、冒泡、归并、快排时间复杂度和空间复杂度
    千次阅读
    2020-09-25 10:51:49
    排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性复杂性
    插入排序O(n2)O(n2)O(n)O(1)稳定简单
    冒泡排序O(n2)O(n2)O(n)O(1)不稳定较复杂
    归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定较复杂
    快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定较复杂

    1. 插入排序

    /**
         * 插入排序的
         * 1.时间复杂度为O(n^2)
         * 2. O(1)的额外空间的排序
         * 3. 平均情况为O(n*n)
         *
         * @param array
         * @return
         */
        public static int[] insertSort(int[] array) {
            for (int index = 0; index < array.length; index++) {
                int temp = array[index];  //将index位的数据拿出来,放到临时变量里,这时index位置就空出来了.
                int leftIndex = index - 1;
                while (leftIndex >= 0 && array[leftIndex] > temp) {  //开始将左面的数据与当前index位的数据(即temp)进行比较
                    array[leftIndex + 1] = array[leftIndex];
                    leftIndex--;
                }
                array[leftIndex + 1] = temp;
            }
            return array;
        }
    

    2.冒泡排序

    /**
         * 冒泡排序
         * 最优的时间复杂度为:O( n^2 )
         * 最差的时间复杂度为:O( n^2 );
         * 平均的时间复杂度为:O( n^2 );
         * 平均的空间复杂度为:O(1);
         *
         * @param array
         */
        public static void sort(int[] array) {
            for (int i = 0; i < array.length - 1; i++) {
                for (int j = 0; j < array.length - 1 - i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
    

    3.归并排序

    /**
         * 归并排序 归并排序是一种稳定的排序。
         * 可用顺序存储结构。也易于在链表上实现。o
         * 对长度为n的文件,需进行趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
         * 需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
         *
         * @param array
         * @param low
         * @param mid
         * @param high
         */
        public static void mergeArray(int[] array, int low, int mid, int high) {
            int[] temp = new int[array.length];
            int i = low;  //i右数组第一个元素索引
            int j = mid + 1;  //j左数组的第一个元素索引
            int k = 0;// k 记录临时数组的索引
            // 从两个数组中取出最小的放入临时数组
            while (i <= mid && j <= high) {
                if (array[i] > array[j]) temp[k++] = array[j++];
                else temp[k++] = array[i++];
            }
            // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
            while (i <= mid) temp[k++] = array[i++];
            while (j <= high) temp[k++] = array[j++];
            // 将临时数组中的内容拷贝回原数组中
            for (int x = 0; x < k; x++) array[x + low] = temp[x];
        }
    
        public static void mergeSort(int[] array, int low, int high) {
            if (low < high) {
                int mid = (low + high) / 2;            // 找出中间索引
                mergeSort(array, low, mid);            // 对左边数组进行递归
                mergeSort(array, mid + 1, high);  // 对右边数组进行递归
                mergeArray(array, low, mid, high);     // 合并
            }
        }
    

    4. 快速排序

    /**
         * 快排
         * 快排在最糟糕得情况下时间复杂度是O(n²),平均的复杂度是O(nlogn)
         * 主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,
         * 其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。
         * @param array
         * @param low
         * @param high
         * @return
         */
        public static int getIndex(int[] array, int low, int high) {
            int temp = array[low]; //记录一个标值的值
            while (low < high) {
                while (low < high && array[high] > temp) high--; //1. 队尾元素大于基准元素的时候 high--
                array[low] = array[high];                      // 如果队尾元素小于tmp了,需要将其赋值给low
                while (low < high && array[low] < temp) low++;  //2. 队首元素小于基准元素的时候 low++
                array[high] = array[low];                        // 当队首元素大于tmp时,需要将其赋值给high
            }
            array[low] = temp;
            return low;
        }
    
        public static void quickSort(int[] array, int low, int high) {
            if (low < high) {
                int index = getIndex(array, low, high);
                quickSort(array, low, index - 1);
                quickSort(array, index + 1, high);
            }
        }
    

    5.测试数据

    public static void main(String[] args) {
            int[] array = {38, 65, 97, 76, 13, 27, 49};
            insertSort(array);
            System.out.print("插入排序从小到大排序后的结果是:");
            for (Integer i : array) {
                System.out.print(i + " ");
            }
            System.out.println();
            int[] array1 = {38, 65, 97, 76, 13, 27, 49};
            sort(array1);
            System.out.print("冒泡排序从小到大排序后的结果是:");
            for (Integer i : array1) {
                System.out.print(i + " ");
            }
            System.out.println();
            int[] array2 = {38, 65, 97, 76, 13, 27, 49};
            mergeSort(array2, 0, array2.length - 1);
            System.out.print("归并排序从小到大排序后的结果是:");
            for (Integer i : array2) {
                System.out.print(i + " ");
            }
            System.out.println();
            int[] array3 = {38, 65, 97, 76, 13, 27, 49};
            quickSort(array3, 0, array3.length - 1);
            System.out.print("快速排序从小到大排序后的结果是:");
            for (Integer i : array3) {
                System.out.print(i + " ");
            }
        }
    
    更多相关内容
  • 归并排序的时间复杂度

    千次阅读 2021-05-24 21:53:41
    现在我们就借助归并排序来看看,如何用递归树,来分析递归代码的时间复杂度归并排序每次会将数据规模一分为二。我们把归并排序画成递归树,就是下面这个样子: 因为每次分解都是一分为二,所以代价很低,我们把...

    归并排序算法你还记得吧?它的递归实现代码非常简洁。现在我们就借助归并排序来看看,如何用递归树,来分析递归代码的时间复杂度。

    归并排序每次会将数据规模一分为二。我们把归并排序画成递归树,就是下面这个样子:
    在这里插入图片描述
    因为每次分解都是一分为二,所以代价很低,我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作,也就是把两个子数组合并为大数组。从图中我们可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。

    现在,我们只需要知道这棵树的高度 h,用高度 h 乘以每一层的时间消耗 n,就可以得到总的时间复杂度 O(n∗h)。

    从归并排序的原理和递归树,可以看出来,归并排序递归树是一棵满二叉树。我们前两节中讲到,满二叉树的高度大约是 log2​n,所以,归并排序递归实现的时间复杂度就是 O(nlogn)。我这里的时间复杂度都是估算的,对树的高度的计算也没有那么精确,但是这并不影响复杂度的计算结果。

    总结

    • 归并排序的时间复杂读为nlogn,每一行时间复杂度O(n) 然后二叉树高度log(n)

    参考

    归并排序图解_鸭梨的博客-CSDN博客

    展开全文
  • 归并排序时间复杂度过程分析

    千次阅读 2020-07-02 14:31:51
    归并排序总时间=分解时间+子序列排好序时间+合并时间 无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。 则:归并排序总时间=子序列排好序时间+合并时间 如果假设一个序列有n个数的排序...

    归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。

    归并排序总时间=分解时间+子序列排好序时间+合并时间

    无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。

    则:归并排序总时间=子序列排好序时间+合并时间


    如果假设一个序列有n个数的排序时间为T(n),T(n)是一个关于n的函数,随着n的变化而变化。

    那么我们将n个数的序列,分为两个(n/2)的序列。

    那么T(n)=2*T(n/2)+合并时间

    由于合并时,两个子序列已经组内排好序了,那我们将两个排好序的序列组合成一个大的有序序列,只需要一个if循环即可。if循环中有n个数需要比较,所以时间复杂度为n。

    那么T(n)=2*T(n/2)+n

     

    我们再将两个n/2个序列再分成4个(n/4)的序列。

    一个(n/2)序列排序时间=两个(n/4)的序列排序时间+两个(n/4)的序列的合并为一个(n/2)的序列时间

    T(n/2)=2*T(n/4)+n/2

    将T(n/2)带入到T(n)中,T(n)=2*(2*T(n/4)+n/2)+n,

    通过化简T(n)=4*T(n/4)+2n

     

    我们再将4个n/4个序列再分成8个(n/8)的序列。

    T(n/4)=2*T(n/8)+n/4

    将T(n/4)带入到黄色公式中,T(n)=4*(2*T(n/8)+n/4)+2n

    通过化简T(n)=8*T(n/8)+3n

    ······


    这样分下去,前面我们已经说过了,分为n个序列,每个序列里只有一个数为止。

    前面我们假设的一个序列有n个数的排序时间为T(n),现在每个序列只有一个数,所以不需要进行组内排序,时间复杂度为0。T(1)=0

    大家有没有找到规律,右边式子中n前面的系数随着层数的增加而增加,第一层公式中没有n,则系数为0,第二层n的系数为1,第三层为2,第四层为3。那么规律就出来了,n前面的系数为层数减1。

    那这个图有没有很熟悉,就像一个二叉树一样,通过二叉树的知识点我们可以知道,一个n个结点的二叉树层数为(log2n)+1。

    那么n前面的系数为层数减1。

    (log2n)+1-1=log2n

    那log2n就是最底层n的系数。

     

    那么我们最后一层是不是可以这样表示

    T(n)=n*T(1)+(log2n)*n

    T(1)=0,那么T(n)=(log2n)*n

    所以归并排序的时间复杂度为nlog2n

    展开全文
  • 一、归并排序 基本思想:将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序,然后将一排序的两个子数组归并成一个含有n个元素的有序数组。 归并排序包含不相邻...

    归并排序

    基本思想:将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序,然后将一排序的两个子数组归并成一个含有n个元素的有序数组。

    归并排序包含不相邻元素的比较,但并不会直接交换。在合并两个已排序的数组时,如果遇到了相同的元素,只要保证前半部分数组优先于后半部分数组,相同元素的顺序就不会颠倒,所以归并排序属于稳定的非线性的排序算法

    归并排序算法虽然高效且稳定,但在处理过程中除了用于保存输入数据的数组外,还要临时占用一部分的内存空间。

    归并排序是个原地的排序,空间可以为O(1)

    1、时间复杂度

    算法的递推关系
    在这里插入图片描述
    若n=2k,则有
    在这里插入图片描述若2k<n<2k+1,
    在这里插入图片描述则时间复杂度为:T(n)=O(nlogn)


    2、代码实现

    const int maxn=100;
    int temp[maxn];
    void MergeSort(int *a,int low,int high)
    {
    	if(low>=high)//代码段①
    		return;
    	int mid=(low+high)/2;
    	MergeSort(a,low,mid);
    	MergeSort(a,mid+1,high);
    	Merge(a,low,mid,high);
    }
    
    void Merge(int *a,int low,int mid,int high)
    {
    	int i=low;
    	int j=mid+1;
    	int size=0;
    	for(;(i<=mid)&&(j<=high);size++)
    	{
    		if(a[i]<a[j])
    			temp[size]=a[i++];//代码段②
    		else
    			temp[size]=a[j++];
    	}
    	while(i<=mid)
    		temp[size++]=a[i++];
    	while(j<=high)
    		temp[size++]=a[j++];
    	for(i=0;i<size;i++)
    	{
    		a[low+i]=temp[i];
    	}
    }
    

    3、改进

    代码段①

    if(low>=high)//代码段①
    		return;
    

    可以进行改进,当长度<5或者<7,可以换成冒泡排序、选择排序,避免递归深度过大,效率能够提高。

    代码段②

    for(;(i<=mid)&&(j<=high);size++)
    	{
    		if(a[i]<a[j])
    			temp[size]=a[i++];//代码段②
    		else
    			temp[size]=a[j++];
    	}
    

    temp可以存储数据的索引,而非数据的值,避免数据的值过大的时候拷贝所耗费的时间与空间。

    4、应用场景

    外排序是指处理超过内存限度的数据的排序算法。通常将中间结果放在读写较慢的外存储器(通常是硬盘)上。

    外排序通常采用“排序-归并”策略

    • 排序阶段:读入能放在内存中的数据量,将其排序输出到临时文件,一次进行,将待排序数据组织为多个有序的临时文件。
    • 归并阶段:将这些临时文件组合为大的有序文件。

    【举例】
    使用100M内存对于900MB的数据进行排序:

    • 读入100M数据内存,用常规方式(如堆排序)排序。
    • 将排序后的数据写入磁盘。
    • 重复前两个步骤,得到9个100MB的块(临时文件)中。
    • 将100M内存划分为10份,前9份中为输入缓冲区,第10份输出缓冲区。
      (如前9份各8M,第10份18M;或10份大小同时为10M)
    • 执行九路归并算法,将结果输出到缓冲区
      (若输出缓冲区满,将数据写至目标文件,清空缓冲区。若输入缓冲区空,读入相应文件的下一份数据)
    展开全文
  • 归并排序的定义 归并排序算法采用的是分治算法,即把两个(或两个以上)有序表合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-...
  • public class MergeSort { public void mergeSort(int[]data, int left, int right) { if(left >= right) return; int mid = (left + right)/2; mergeSort(data, le...
  • 内排序有可以分为以下几类:(1)插入排序:直接插入排序、二分法插入排序、希尔排序(2)选择排序:直接选择排序、堆排序(3)交换排序:冒泡排序、快速排序(4)归并排序(5)基数排序排序方法时间复杂度(平均)...
  • 在用快排求解逆序数前,我先考虑了这个问题,1:归并和快排的时间复杂度都是nlog(n),为什么不用归并? 我认为应该是由于快排在每次合并时都有用到临时数组,然后每次还需要把临时数组重新copy到原数组中 ,增加了...
  • 文章目录一、排序算法的介绍二、排序的分类三、算法的时间复杂度3.1 度量一个程序(算法)执行时间的两种方法3.2 时间频度3.3 时间复杂度3.4 常见时间复杂度3.5 平均时间复杂度和最坏时间复杂度四、算法的空间复杂度 ...
  • 归并排序、快速排序都使用了分治的思想,时间复杂度都是O(N*logN)。由于其时间复杂度低,所以被广泛的应用,比如Java Collection.sort; Mysql数据库中的排序;Tim排序等。
  • 转载请注明出处:排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常见的排序...
  • 归并排序的基本思想 归并排序法是将两个或以上的有序表合并成一个新的有序表,即把待排序序列分成若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。注意:一定要是有序序列!  归并排序...
  • 输入n个整数,用快速排序、堆排序与2路归并排序算法实现由小到大排序并输出排序结果。要求排序数据及排序结果用字符文件实现输入与输出。
  • 7.1 排序算法的介绍 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的...7.3 算法的时间复杂度 7.3.1度量一个程序(算法)执行时间的两种方法 1) 事后统计的方法 这种方法可行, 但是有两个问题:一是要.
  • 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) 选择排序 O(n2) O(n2) 不稳定 O(1) 二叉树排序O(n2) O(n*...
  • 合并有序数组的时间复杂度

    千次阅读 2019-04-14 20:44:36
    对于以第一个元素建立起来的小根堆,重建过程需要logm,一共有m个这样的元素所以第一个小根堆完全输出需要的时间复杂度是m*logm(堆排序的时间复杂度logmm包括了初始化的o(m),因为这个只有刚开始的初始化过程需要...
  • 排序算法-桶排序的时间复杂度分析

    千次阅读 2019-08-26 14:05:36
    桶排序,是一种基于非比较的排序方式,时间复杂度O(n),因此它是是属于一种“线性排序”。 思想:桶排序的思想是将一组数据分到几个有序的桶里,每个桶里的数据再单独进行快速排序。每个桶内都排序完成后,再加上...
  • 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常见的排序算法进行归纳。 ...
  • 一般递归时间复杂度分析

    千次阅读 2019-03-14 16:48:50
    其中T(n)为样本量的时间复杂度,a为子过程发生多少次,T(n/b)子过程的样本量的时间复杂度,O(n ^b)为除了子过程以外,其他操作所需的时间复杂度。 1.log(b,a) &lt; d 时,时间复杂度为O(n^d) 。 2.log(b,a) = d ...
  • 时间复杂度为O(nlogn)的排序算法(归并排序、快速排序),比时间复杂度O(n²)的排序算法更适合大规模数据排序。归并排序归并排序的核心思想采用“分治思想”,将要排序的数组从中间分成前后两个部分,然后对前后两个...
  • 声明:本帖子专为个人面试所写,本身只是... 时间复杂度:计算规则常见时间复杂度常见时间复杂度比较List常见内置操作的时间复杂度Dict常见内置操作时间复杂度:二. 顺序表:定义存储方式三. python中的顺序表(列...
  • 常见排序算法及其对应的时间复杂度、空间复杂度: 排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序,本文...
  • 常见排序算法及其时间复杂度

    万次阅读 多人点赞 2019-06-20 18:00:18
    常见排序算法及其时间复杂度 一、内部排序:1.稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序的实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序的实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并...
  • 1利用随机函数产生10000个随机整数对这些数进行多种方法 排序 2至少采用4种方法实现上述问题求解可采用的方法有插入排 序希尔排序起泡排序快速排序选择排序堆排序归并排序 并把排序后的结功能果保存在不同的文件里 ...
  • 应用于二分查找 归并排序等 public void getMaxByBinary(int[] arr){ 1 return process(arr,0,arr.length-1); } public int process(int[] arr,int L,int R){//f(0,3) 2 if(L==R){ 3 return arr[L]; } 4 int mid =...
  • 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n) 选择排序 O(n2) O(n2) 不稳定 O(1) 二叉树排序 O(n2) O(n*log2n) 不一顶 ...
  • ①、什么是稳定性? 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些...计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的...
  • 1)利用随机函数产生10000个随机整数对这些数进行多种方法排序 2至少采用4种方法实现上述问题求解可采用的方法有插入排序希尔排序起泡排序快速排序选择排序堆排序归并排序并把排序后的结功能果保存在不同的文件里 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,847
精华内容 7,538
关键字:

文件归并的时间复杂度

友情链接: BipolarSPWM_2015b.rar