-
排序时间复杂度
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)
-
Java排序算法03:归并排序法、基数排序法、推排序法、思路分析、代码实现
2020-06-14 15:57:47归并排序的时间复杂度是比较低的。 归并与快速排序法的平均时间复杂度一致,但是比快速排序法稳定。 示意图: 这里展示将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两个指针... -
Python3 基本排序算法 之 冒泡排序,插入排序,选择排序
2019-06-14 14:50:04目录 基本排序算法按时间复杂度分类 冒泡排序 插入排序 ...相邻的两个元素对比,大的数后推,遍历整个列表一次后,将最大项以冒泡的方式排列到列表末尾。 简易版冒泡排序示例如下 def bu... -
Python3 基本排序算法之冒泡排序,插入排序,选择排序
2019-09-18 05:43:54基本排序算法按时间复杂度分类 O(n^2) 冒泡排序 插入排序 选择排序 Q(n log n) 分而治之 快速排序 归并排序 冒泡排序 相邻的两个元素对比,大的数后推,遍历整个列表一次后,将最大项以冒泡的方式排列i到... -
几种常用的排序算法总结
2015-05-25 10:02:52主要针对于插入排序,交换(冒泡和快速),选择,堆排序,归并这几种排序的基本原理和时间复杂度,及空间复杂度的一个总结。 一、插入排序 基本执行过程:3 5 2 7 9 8 1、从小到大:从第二个数开始... -
一道「空间」很贵的排序算法
2020-12-26 19:05:54你这样的时间复杂度基本是在O(n2),为什么空间控制这么严格呢? 九哥哥(提问者):因为这不是内存,而是个实际的柜子,只有这么大空间[捂脸],完全不考虑时间... -
【一个小实验】排序效率比较
2015-08-01 16:07:58最近参加内推,四轮技术面里头有三轮都问到了排序... 需要注意的是:两路归并排序这个O(NlogN)时间复杂度的我没(Bu)写(Hui)。原因在快速排序里面已经展现了。其次,每次参与的数组均由随机函数生成。 先说结论: -
Introduction for sort algorithm
2020-12-28 22:48:22排序的分类 1.内部排序 ...算法的时间复杂度 1.事后统计 执行程序,得到执行时间,对其进行分析。 2.事前估算 分析某个算法的时间复杂度 时间频度 一个算法执行的时间与算法中语句的执行次数成正比。 ... -
腾讯网易字节面经(C++,腾讯和字节是iOS岗)
2021-01-23 13:47:34211通信本硕,自己搞了差不多一年的时间,学C++,通过面经学操作系统和计网,通过刷题学数据结构和算法 腾讯因为是提前批的,所以很多问题不记得了,见谅! 腾讯PCG一面(1h) 1.进程和线程的区别 2.死锁的原因 3.... -
大话数据结构
2019-01-10 16:35:222.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大... -
大话数据结构 程杰
2018-09-01 10:06:432.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大... -
大话数据结构(中文高清版)
2017-04-19 11:57:092.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 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。... -
大话数据结构三个版本
2018-09-10 09:39:382.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大... -
《大话数据结构》( 程杰 编著)
2018-02-15 10:00:212.10常见的时间复杂度 35 有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。 2.11最坏情况与平均情况 35 2.12算法空间复杂度 36 事先建立一个有2050大... -
大话数据结构-程杰
2014-07-13 23:45:522.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.时区 是符合人们习惯的一种辅助计时方法,按照...
-
【336-week 07】课后总结
2020-11-25 07:54:21<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>...
-
U盘修复量化工具.rar
-
PPTP_NNN 服务生产环境实战教程
-
react-native-document-picker一个适合react native打开本地文件,上传文件的组件
-
Visio培训教材.ppt
-
虚幻4引擎基础
-
Git主要命令
-
2021 PHP租车系统 毕业设计 毕设源码 源代码使用教程
-
基于电商业务的全链路数据中台落地方案(全渠道、全环节、全流程)
-
靶形与离子发射
-
高匿代理帮你解决爬虫问题
-
MySQL和JDBC.pdf
-
JAVA面向对象
-
SaleageLogic_V1.2.18.zip
-
TaggedAR:基于RFID的增强现实系统中多个标记对象的识别方法
-
龙芯实训平台应用实战(希云)
-
vue-cli打包优化之分析工具webpack-bundle-analyzer
-
几款串口助手.zip
-
性能测试设计(二)
-
判断素数
-
gif分解工具.zip