精华内容
下载资源
问答
  • 排序时间复杂度

    千次阅读 2013-08-07 00:49:54
    数组长度为N。 选择排序:将最小元素和第一个元素交换,第二小元素和第二个元素交换,依次类时间复杂度为O(N^2) ...归并排序:将两个有序数组合并为一个更大有序数组。时间复杂度为O(NlgN) 快速

    数组长度为N。

    选择排序:将最小的元素和第一个元素交换,第二小的元素和第二个元素交换,依次类推。时间复杂度为O(N^2)

    插入排序:将元素插入到其他已经有序的元素中的适当位置。时间复杂度为O(N^2)

    希尔排序:使数组中任意间隔为h的元素都是有序的。时间复杂度达不到O(N^2),最坏情况为O(N^1.5)

    归并排序:将两个有序数组合并为一个更大的有序数组。时间复杂度为O(NlgN)

    快速排序:将一个数组分成两个子数组进行独立排序。时间复杂度为O(NlgN)

    展开全文
  • 归并排序的时间复杂度是比较低的。 归并与快速排序法的平均时间复杂度一致,但是比快速排序法稳定。 示意图: 这里展示将4578和1236合并在一起进行排序的过程: public class MergeSorting { public static void...


    5、归并排序法

    归并排序是利用归并的思想实现的排序方法。如上图。思路比较简单,就是对数组进行不断的分割,分割到只剩一个元素,然后,再两两合并起来。

    归并排序的时间复杂度是比较低的。

    归并与快速排序法的平均时间复杂度一致,但是比快速排序法稳定。

    示意图:

    在这里插入图片描述

    这里展示将4578和1236合并在一起进行排序的过程:

    在这里插入图片描述

    在这里插入图片描述

    public class MergeSorting {
        public static void main(String[] args) {
            int arr[] = {3,9,-1,10,20,6};
            int temp[] = new int[arr.length];
            System.out.println("排序前:"+ Arrays.toString(arr));
            sort(arr,0,arr.length-1,temp);
            System.out.println("排序后:"+Arrays.toString(arr));
        }
    
        /**
         * 拆分后合并操作
         * @param arr 原数组
         * @param left 原数组的左索引
         * @param right 原数组的右索引
         * @param temp 临时数组
         */
        public static void sort(int[] arr, int left, int right, int[] temp){
            // 如果左索引小于右索引 就继续拆分,先左拆分,拆分到不能拆分为止,
            // 再右拆分到不能拆分为止,最后将最后拆分的结果合并
            if (left < right){
                int mid = (left+right)/2;
                // 往左拆分
                sort(arr, left, mid, temp);
                // 往右拆分
                sort(arr, mid+1, right, temp);
                // 合并
                merge(arr, left, mid, right, temp);
            }
        }
    
    
        /**
         * 合并操作
         * @param arr 分割的原数组
         * @param left 最左边的索引
         * @param mid 中间索引
         * @param right 最右边的索引
         * @param temp 临时存储的数组
         */
        public static void merge(int[] arr, int left, int mid, int right, int[] temp){
            int i = left; // 从最左边开始的索引
            int j = mid+1; // 从中间索引的下一个索引开始的索引
            int t = 0; // 临时数组的起始索引
    
            while ( i <= mid && j <= right){
                // 左右两部分进行比较,小的往临时数组里放
                if (arr[i] <= arr[j]){
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else {
                    temp[t] = arr[j];
                    j++;
                    t++;
                }
            }
    
            // 总有一边的数据先放完,另一边的数据就一次放到临时数组
            while (i <= mid){
                temp[t] = arr[i];
                t++;
                i++;
            }
            while (j <= right){
                temp[t] = arr[j];
                t++;
                j++;
            }
    
            // 组后将临时数组的数据全部拷贝到原数组对应位置
            t = 0;
            int tempLeft = left; // 原数组拆分后的起始索引位置
            while (tempLeft <= right){
                arr[tempLeft] = temp[t];
                tempLeft++;
                t++;
            }
        }
    }
    

    结果:

    排序前:[3, 9, -1, 10, 20, 6]
    排序后:[-1, 3, 6, 9, 10, 20]
    

    6、基数排序法

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    占用内存很大。

    基数排序法,只支持正数如果需要排序负数和正数混合的数组,就得将正数和负数分出来,到各自的数组然后对各自的数组进行装桶即可。负数判断与正数刚好相反

    public class RadixSorting {
        public static void main(String[] args) {
            int arr[] = {3,9,1,10,20,6};
            System.out.println("排序前:"+ Arrays.toString(arr));
            sort(arr);
            System.out.println("排序后:"+Arrays.toString(arr));
        }
    
        public static void sort(int[] arr){
            // 桶,第一个索引记录是第几个桶,第二个索引记录桶中存放的值
            // 每个桶的大小都是arr.length,而不是每个桶都有数据,所以消耗空间内存
            int bucket[][] = new int[10][arr.length];
            // 这个数组用于记录每个桶中的元素个数
            int bucketElementsCount[] = new int[10];
    
            // 获取数组中最大的数,计算有多少位
            int max = arr[0];
            for (int i : arr) {
                if (i>max){
                    max = i;
                }
            }
            int digit = (max+"").length();
    
            // 最大数的位数,决定了基数排序要轮回多少次,即digit-1次
            for (int i = 0; i < digit; i++) {
                // 每一轮的基数都有变化,第一轮为个位,第二轮位十位,第三轮为百位,以此类推
                for (int j = 0; j < arr.length; j++) {
                    int bucketNumber = arr[j] / (int)Math.pow(10,i) % 10;
                    // 将数装到bucketNumber的桶中索引为bucketElementsCount[bucketNumber]的位置
                    bucket[bucketNumber][bucketElementsCount[bucketNumber]] = arr[j];
                    // 自增,桶中的元素在增加
                    bucketElementsCount[bucketNumber]++;
                }
    
                // 每个数都到了自己对应的桶中之后,需要将桶中的数据都重新填到arr中
                int index = 0;
                for (int c = 0; c < bucketElementsCount.length; c++) {
                    // 如果不等于0,所以记录的该桶中是有数据的
                    if (bucketElementsCount[c] != 0){
                        for (int k = 0; k < bucketElementsCount[c]; k++) {
                            arr[index++] = bucket[c][k];
                        }
                    }
                }
    
                // 重置记录桶中元素的个数为0,为下一次记录做准备
                for (int j = 0; j < bucketElementsCount.length; j++) {
                    bucketElementsCount[j] = 0;
                }
            }
        }
    }
    

    结果:

    排序前:[3, 9, 1, 10, 20, 6]
    排序后:[1, 3, 6, 9, 10, 20]
    

    7、堆排序法 (不稳定)

    时间复杂度O(nlogn)

    大顶堆和小顶堆,顺序存储二叉树一定是完全二叉树

    • 大顶堆

    在这里插入图片描述

    顺序存储到数组(二叉树的顺序存储):

    arr[]={50,45,40,20,25,35,30,10,15}

    • 小顶堆

    在这里插入图片描述

    顺序存储到数组(二叉树的顺序存储):

    arr[]={10,20,15,25,50,30,40,35,45}

    n为父节点的索引:

    左子节点是:2*n+1

    右子节点是:2*n+2

    n为子节点的索引,父节点为:(n-1)/2

    一般升序采用大顶堆,降序采用小顶堆。

    思路分析:

    根据代码,画图理解

    • 将待排序的序列构建成大顶堆:从最后一个非叶子节点开始调整(arr.length/2-1)。从左至右,从下至上的顺序进行调整。
    • 此时,整个序列的最大值就是堆顶的根节点
    • 将其与末尾元素进行交换,此时末尾就为最大值
    • 然后将剩余n-1个元素重新构造成一个堆,这样在堆顶的就是次小值。如此反复执行,便能得到一个有序序列
    public class HeapSorting {
        public static void main(String[] args) {
            int arr[] = {4,6,8,5,9};
            System.out.println("通过堆排序得到升序:");
            heapSort(arr);
        }
    
        // 核心部分,这里是大顶堆的构造,升序
        // 需要小顶堆,只需要将16行和21行的比较符号更改以下即可,降序
        public static void adjustHeap(int[] arr, int i, int length){
            int temp = arr[i]; // 记录非叶子节点(父节点)
            // j为非叶子节点的左子节点
            for (int j = 2*i+1; j < length; j = j*2+1) {
                // 如果有右子节点并且左子节点小于右子节点,将j指向右子节点
                // 否子依旧指向左子节点
                if (j+1<length && arr[j]<arr[j+1]){
                   j++;
                }
                // 如果右子节点(左子节点)大于父节点,那么就将子节点赋值给父节点的位置
                // 并将父节点的i指向当前节点,目的为了下一次比较以及值得交换
                if (arr[j] > temp){
                    arr[i] = arr[j];
                    i=j;
                }else {
                    break;
                }
            }
            // 此时的i已经指向了当前节点,即将当前节点赋值为原先的父节点
            arr[i] = temp;
        }
    
        public static void heapSort(int[] arr){
            int temp;
    
            // 从最后一个非叶子节点开始依次往后遍历,创建一个大顶堆
            for (int i = arr.length/2-1; i >= 0 ; i--) {
                adjustHeap(arr, i, arr.length);
            }
    
            // 大顶堆创建完了,就开始排序了
            for (int j = arr.length-1; j >=0 ; j--) {
                // 交换,因为每次大顶堆调整完之后,最大的数都在根节点,
                // 因此需要将最大的数放在数组的后面,进行交换
                temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
                // 交换完之后,大顶堆被打乱,因此有需要调整成为大顶堆
                // 因为每次交换都是讲0索引的值与当前数组最后一个值进行交换,
                // 被打乱的是索引为0的根节点,所以就从根节点开始调整,长度变成了j
                adjustHeap(arr, 0, j);
            }
    
            System.out.println(Arrays.toString(arr));
        }
    }
    

    结果:

    通过堆排序得到升序:
    [4, 5, 6, 8, 9]
    
    展开全文
  • 排序算法--归并排序

    2018-03-25 21:54:07
    引言 归并排序的时间复杂度是O(N*logN),额外空间复杂度是O(N),可以实现做的稳定性。 归并排序的思想是把一个数组分成两半,把每一半都分成两个四分之一,把每个四分之一部分分成八分之一,依次类,反复的分割...

    引言

        归并排序的时间复杂度是O(N*logN),额外空间复杂度是O(N),可以实现做的稳定性。

        归并排序的思想是把一个数组分成两半,把每一半都分成两个四分之一,把每个四分之一部分分成八分之一,依次类推,反复的分割数组,直到得到的子数组是只有一个数据项。然后把两个只有一个数据进行比较。创建等于其数据项大小的数组,把数据按大小顺序拷贝到新创建的数组中,把新的数组中的数据按顺序再拷贝回到原数组。排序就排列好了。

    如下图


    把数组分成两半后

       

    先开始分左半部分 继续分两半 直到分到时单个数为止


        如图所示(图画的有点囧),先把数组的元素进行比较。元素1直接返回,右边元素8、7。先排序右侧部分,创建一个两个元素的数组,把元素8和7进行比较,然后按顺序进行排序,排序后就是7和8。再把7和8拷贝的原数组。然后再用元素1与7、8进行比较,左边1比7小 先拷贝1,然后再把7、8拷贝到新数组,在把这个次序按新数组的顺序拷贝到原来数组中去。依次类推,具体代码实现如下:

    /**
     * 归并排序
     * @author whmAdmin
     *
     */
    public class MergeSort {
    	
    	public static void mergeSort(int[] arr){
    		if(null == arr || arr.length < 2){
    			return;
    		}
    		
    		mergeSortTest(arr, 0, arr.length-1);
    	}
    
    	public static void mergeSortTest(int[] arr, int L, int R) {
    		// 如果左右下坐标相等,返回
    		if(L == R){
    			return;
    		}
    		
    		// 获取中间下坐标
    		int mid = L + (R - L) / 2;
    		// 先排序左部分,左部分是L到mid中间这部分元素
    		mergeSortTest(arr, L, mid);
    		// 再排序右部分,右部分是mid中间后一位到R这部分元素
    		mergeSortTest(arr, mid+1, R);
    		// 对要排序的数组进行排序操作
    		mergeSortArray(arr,L,mid,R);
    		
    	}
    
    	public static void mergeSortArray(int[] arr, int L, int mid, int R) {
    		//创建新数组
    		int[] arrs = new int[R-L+1];
    		//设置新数组开始坐标
    		int i = 0;
    		// 设置左部分开始指针
    		int p1 = L;
    		// 设置右部分开始指针
    		int p2 = mid + 1;
    		
    		// 如果左指针坐标小于等于中间左边并且右指针坐标小于等于R最右坐标,继续循环。否则越界停止循环
    		while(p1<=mid&& p2 <= R){
    			// 比较左右两个指针上的元素大小,谁小就拷贝到新数组,并且指针位置++
    			arrs[i++] = arr[p1] < arr[p2]?arr[p1++]:arr[p2++];
    		}
    		
    		// 如果左指针位置比右指针所有位置元素都大,需要把剩余左部分全部拷贝到新数组
    		while(p1<=mid){
    			arrs[i++] = arr[p1++];
    		}
    		
    		// 同理如果右指针位置比左指针所有位置的元素都大,需要把剩余右部分全部拷贝新数组
    		while(p2<=R){
    			arrs[i++] = arr[p2++];
    		}
    		// 以上左右指针拷贝只能出现一种
    		
    		// 把排序好的新数组元素拷贝到原数组中
    		for (int j = 0; j < arrs.length; j++) {
    			// L+1是要按原位置进行拷贝回去
    			arr[L+j] = arrs[j];
    		}
    	}
    
    }
        以上就是归并排序的实现,这种实现使用了递归的方式进行实现的,归并排序存在非递归实现版本。有兴趣的可以进行了解一下。
    展开全文
  • 快速排序和归并排序

    2018-05-06 17:07:25
    快速排序和归并排序是面试时候经常被问到的东西,对于其中任何一个知识点都要对答如流才可以,比如手推、时间复杂度、原理等等。下面我就对这两种排序中常问到的知识点进行以下总结。 快速排序 快速排序代码...

    快速排序和归并排序是面试的时候经常被问到的东西,对于其中的任何一个知识点都要对答如流才可以,比如手推、时间复杂度、原理等等。下面我就对这两种排序中常问到的知识点进行以下总结。

    快速排序

    快速排序代码如下(要做到熟记并理解):

    private static int Partition(int[] arr, int left, int right) {
            //arr[left]为挖的第一个坑
            int key = arr[left];
            while (left< right) {
                while (arr[right] >= key && right> left)
                    end--;
                arr[left] = arr[right];
                while (arr[left] <= key && right> start)
                    left++;
                arr[right] = arr[left];
            }
            arr[left] = key;
            return left;
    } 
    
    public static void quickSort(int[] arr, int left, int right) {
            if (left < right){
                int index = Partition(arr, left, right);
                quickSort(arr, left, index - 1);
                quickSort(arr, index + 1, right);
            }
     }

    算法原理参考:https://blog.csdn.net/kwang0131/article/details/51085734

    平均O(nlog2n)
    最坏O(n2)
    最好O(nlog2n)
    空间复杂度O(nlog2n)
    不稳定
    较复杂

    归并排序

    归并排序代码如下(要做到熟记并理解):

    public static void merge(int[] a, int left, int mid, int right) {
            int[] temp = new int[right- left + 1];
            int i = left;// 左指针
            int j = mid + 1;// 右指针
            int k = 0;
            // 把较小的数先移到新数组中
            while (i <= mid && j <= right) {
                if (a[i] < a[j]) {
                    temp[k++] = a[i++];
                } else {
                    temp[k++] = a[j++];
                }
            }
            // 把左边剩余的数移入数组
            while (i <= mid) 
                temp[k++] = a[i++];
            }
            // 把右边边剩余的数移入数组
            while (j <= right) {
                temp[k++] = a[j++];
            }
            // 把新数组中的数覆盖nums数组
            for (int k2 = 0; k2 < temp.length; k2++) {
                a[k2 + left] = temp[k2];
            }
        }
    
        public static void mergeSort(int[] a, int left, int right) {
            if (left < right) {
                int mid = (left + right) / 2;
                // 左边
                mergeSort(a, left, mid);
                // 右边
                mergeSort(a, mid + 1, right);
                // 左右归并
                merge(a, left, mid, right);
                System.out.println(Arrays.toString(a));
            }
        }
    
        public static void main(String[] args) {
            int a[] = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
            mergeSort(a, 0, a.length - 1);
            System.out.println("排序结果:" + Arrays.toString(a));
        }
    }

    算法原理参考:https://blog.csdn.net/lemon_tree12138/article/details/51517753

    平均O(nlog2n)
    最坏O(nlog2n)
    最好O(nlog2n)
    空间复杂度O(n)
    稳定
    较复杂

    展开全文
  • 归并排序【模板】

    2020-08-08 23:07:45
    归并排序 时间复杂度:O(log2n) 流程 1.分界点为中点:mid=(left + right)/2 2.分别递归排序两边 3.归并——合二为一 O(n) 这里我们就得到了两个排好序(从小大),然后: 再开出一个数组res,用i,j两个指针...
  • 目录 基本排序算法按时间复杂度分类 冒泡排序 插入排序 ...相邻两个元素对比,大数后,遍历整个列表一次后,将最大项以冒泡方式排列列表末尾。 简易版冒泡排序示例如下 def bu...
  • 基本排序算法按时间复杂度分类 O(n^2) 冒泡排序 插入排序 选择排序 Q(n log n) 分而治之 快速排序 归并排序 冒泡排序 相邻两个元素对比,大数后,遍历整个列表一次后,将最大项以冒泡方式排列i...
  • 几种常用的排序算法总结

    千次阅读 热门讨论 2015-05-25 10:02:52
    主要针对于插入排序,交换(冒泡和快速),选择,堆排序,归并这几种排序的基本原理和时间复杂度,及空间复杂度的一个总结。   一、插入排序 基本执行过程:3 5 2 7 9 8   1、从小大:从第二个数开始...
  • 你这样的时间复杂度基本是在O(n2),为什么空间控制这么严格呢? 九哥哥(提问者):因为这不是内存,而是个实际的柜子,只有这么大空间[捂脸],完全不考虑时间...
  • 最近参加内,四轮技术面里头有三轮都问了排序... 需要注意是:两路归并排序这个O(NlogN)时间复杂度的我没(Bu)写(Hui)。原因在快速排序里面已经展现了。其次,每次参与数组均由随机函数生成。  先说结论:
  • 排序的分类 1.内部排序 ...算法的时间复杂度 1.事后统计 执行程序,得到执行时间,对其进行分析。 2.事前估算 分析某个算法的时间复杂度 时间频度 一个算法执行的时间与算法中语句的执行次数成正比。 ...
  • 211通信本硕,自己搞了差不多一年的时间,学C++,通过面经学操作系统和计网,通过刷题学数据结构和算法 腾讯因为是提前批的,所以很多问题不记得了,见谅! 腾讯PCG一面(1h) 1.进程和线程的区别 2.死锁的原因 3....
  • 大话数据结构

    2019-01-10 16:35:22
    2.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    2.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大...
  • 2.9.1 算法时间复杂度定义 29 2.9.2 推导大O阶方法 30 2.9.3 常数阶 30 2.9.4 线性阶 31 2.9.5 对数阶 32 2.9.6 平方阶 32 2.10 常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。...
  • 2.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大...
  • 2.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    2.10 常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11 最坏情况与平均情况 35 2.12 算法空间复杂度 36 事先建立一个有...
  • 7.5.1.绝对时间: 是指从1970年01月01日00时00分00秒 此刻的时间,全世界都一样。 注意:1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒) 7.5.2.时区 是符合人们习惯的一种辅助计时方法,按照...
  • <div><h1>摘要 <ul><li>位运算</li><li>布隆过滤器</li><li>LRU Cache</li><li>排序算法</li><li>算法... Double LinkedList</li><li>时间复杂度</li><li>O(1) 查询 </li><li>O(1) 修改、更新</li><li>实现</li><li>...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

归并排序的时间复杂度推到