• 关于 数组循环下标 的搜索结果

回答

假设用户输入了如下数组: 下标 0 1 2 3 4 5 数据 6 2 7 3 8 9 创建变量i=0(指向第一个数据), j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。我们要把所有比k小的数移动到k的左面,所以我们可以开始寻找比6小的数,从j开始,从右往左找,不断递减变量j的值,我们找到第一个下标3的数据比6小,于是把数据3移到下标0的位置,把下标0的数据6移到下标3,完成第一次比较: 下标 0 1 2 34 5 数据 3 2 7 6 8 9 i=0 j=3 k=6接着,开始第二次比较,这次要变成找比k大的了,而且要从前往后找了。递加变量i,发现下标2的数据是第一个比k大的,于是用下标2的数据7和j指向的下标3的数据的6做交换,数据状态变成下表: 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 i=2 j=3 k=6称上面两次比较为一个循环。接着,再递减变量j,不断重复进行上面的循环比较。在本例中,我们进行一次循环,就发现i和j“碰头”了:他们都指向了下标2。于是,第一遍比较结束。得到结果如下,凡是k(=6)左边的数都比它小,凡是k右边的数都比它大: 下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 如果i和j没有碰头的话,就递加i找大的,还没有,就再递减j找小的,如此反复,不断循环。注意判断和寻找是同时进行的。然后,对k两边的数据,再分组分别进行上述的过程,直到不能再分组为止。注意:第一遍快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。 在c++中可以用函数qsort()可以直接为数组进行排序。 用 法:void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));参数:  1 待排序数组首地址  2 数组中待排序元素数量  3 各元素的占用空间大小  4 指向函数的指针,用于确定排序的顺序

小哇 2019-12-02 01:17:33 0 浏览量 回答数 0

回答

不同点: 冒泡排序法:一趟一趟的将两个相邻的数进行交换如果有10个数则需要排9躺,如果是从大到小输出则需要每次将后一个数和前一个数进行比较将较大的数赋值给钱一个数,将较小的数赋值给后一个数,其实就是两个数交换,那么第一趟交换完毕后,最小的数便出现在了数组的最后面,然后进行第二趟的比较时则要对余下的前9个数进行比较,9趟比较完成后则数组也已经排好序。 选择排序法:10个数则是需要排9次,若按降序排列,第一次比较:则是将数组的第一个元素与数组中从第二个元素开始到最后的元素进行比较找到最大的数记录下来然后将值赋值给数组的第一个元素,然后进行第二次比较:则是将数组的第二个元素与数组中从第三个元素开始到最后的元素进行比较,找最大的数记录下来将值赋值给数组的第二个元素,依次循环找完。 程序分析: 选择排序: 1>.对于选择排序,首先理解排序的思想。给定一个数组,这种思想首先假定数组的首元素为最大(最小)的。此时就要利用3个变量i,j,k表示元素的下标。i表示当前,j表示找到的最大(最小)的下标,k用于存放每次循环中最大值的下标。 2>.在掌握了程序的基本思想之后,再进行排序。找到最大的下标后赋给k。找到之后判断所假设的当前值是否为此次循环的最大值,如果不是,就交换a[k] 与当前a[i]的值,从而将数组以一定的顺序排放,最后写一个循环将结果输出。 冒泡排序: 1>.对于冒泡排序,主要采用的是相邻数两两进行比较的思想。如果后一个比前一个大(小),则将其调换位置,直至所有的数都比较完。 2>.如果给定一个大小为n的数组,那么需要比较n-1趟,每一趟比较n-1-i次 ,i 表示上次循环中已经比较完的下标。写两个循环 判断,如需交换则进行交换,如果不需要交换则进行下两个数的比较,直到所有的数比较完。最后,用一个循环将排序完成后的数全部输出。-------------------------数组排序前 7 23 12 4 33 21 2 17 13 9 第一轮排序 7 12 4 23 21 2 17 13 9 33 第二轮排序 7 4 12 21 2 17 13 9 23 第三轮排序 4 7 12 2 17 13 9 21 第四轮排序 4 7 2 12 13 9 17 第五轮排序 4 2 7 12 9 13 第六轮排序 2 4 7 9 12 第七轮排序 2 4 7 9 第八轮排序 2 4 7 第九轮排序 2 4 可以看到,每一轮的排序,在这一轮中参与比较的元素中最大的数将会浮到最后。而冒泡排序的名字也是从这里来的 。 数组排序前 7 23 12 4 33 21 2 17 13 9 第一轮循环 2 23 12 4 33 21 7 17 13 9 第二轮循环 4 12 23 33 21 7 17 13 9 第三轮循环 7 23 33 21 12 17 13 9 第四轮循环 9 33 21 12 17 13 23 第五轮循环 12 21 33 17 13 23 第六轮循环 13 33 17 21 23 第七轮循环 17 33 21 23 第八轮循环 21 33 22 第九轮循环 22 33 通过这个过程,我们可以看到,每轮循环过程中,都会找出这个最值元素,下一轮排序时就不用再考虑这个元素

马铭芳 2019-12-02 01:17:36 0 浏览量 回答数 0

回答

static void Main(string[] args) { int[] arr = new int[] { 3, 9, 27, 6, 12, 21, 16 };//定义一个一维数组,并赋值 foreach (int m in arr) { Console.Write(m + " ");//循环遍历定义的一维数组,并输出其中的元素 } Console.WriteLine(); //定义两个int类型的变量,分别表示数组下标和存储新的数组元素 int j, temp; for (int i = 0; i < arr.Length - 1; i++)//根据数组下标的值遍历数组元素 { j = i + 1; id://定义一个标识,以便从这里开始执行语句 if (arr[i] < arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; goto id; } else if (j < arr.Length - 1)//判断是否执行到最后一个元素 { j++; //如果没有则再往后判断 goto id; //返回标识,继续后面的元素 } } foreach (int n in arr)//循环遍历排序后的数组元素并输出 Console.Write(n + " "); Console.WriteLine(); Console.ReadKey(); }

马铭芳 2019-12-02 01:18:07 0 浏览量 回答数 0

海外云虚拟主机包年25元/月起

海外独享虚拟主机全面上线,助力构建海外网站,提升公司国际形象;全球有效覆盖,超高性价比;建站入门首选,助力出口,适合跨境贸易企业。

回答

/* ================================================ 功能:选择排序 输入:数组名称(也就是数组首地址)、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环 到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)--[n的平方] ===================================================== */ int select_sort(int *x, int n) { int i, j, min, t;int count=0; for (i=0; i<n-1; i++) /*要选择的次数:0~n-2共n-1次*/ { min = i; /*假设当前下标为i的数最小,比较后再调整*/ for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/ { if (*(x+j) < *(x+min)) { min = j; /*如果后面的数比前面的小,则记下它的下标*/ } } if (min != i) /*如果min在循环中改变了,就需要交换数据*/ { t = *(x+i); *(x+i) = *(x+min); *(x+min) = t; count++; } }return count; } 其中count为交换的次数,排序完后将count返回;具体想了解各种排序算法的性能比较可以到这下载 http://download.csdn.net/source/1400524

游客886 2019-12-02 01:18:27 0 浏览量 回答数 0

回答

我给你说一下冒泡的原理吧: 冒泡冒泡,顾名思义,就是往上走的意思。 冒泡排序是要依靠两层循环,外层控制次数,内层逐个比较。 第一次外层循环将最大(最小)的值放到最上面(数组最后面); 第二次外层循环把第二大(小)的值放到从上往下第2个位置:(数组最后一个) 那么,每一次外层循环,内层的循环只需要循环从1到总长度减外层次数的长度,这就是: for(int j=0;j<arr.length-i-1;j++) 这一行的意义; 然后实现把最大(最小)的值放到最后面的方法是挨着的两个数依次做判断。这就是: if(arr[j]<arr[j+1]) 这一行的意义;如果当前值比后面的一个值小,则两个值交换位置。 你的这个排序是要把最小的放到最后面,也就是从大到小的排序。 我估计你对边界:j<arr.length-i-1;会不解,为什么-i之后还要-1呢。 这是因为在下面的判断里面你是把当前值和后面一个值做比较的。如果不减1,则当循环到最后一个值的时候,再取下一个值就取不到,就需要额外的操作,或者抛出数组下标越界的异常。

琴瑟 2019-12-02 01:18:16 0 浏览量 回答数 0

回答

简单说吧。上面foreach就是遍历数组$a的每个元素,并把每个元素的键、值分别赋给 $key、$b,便于在循环主体中使用。下面1、php中array当纯粹的数组用,$key就是数组元素的下标,array('a1','a2'); 等价于 array(0 =>'a1', 1 => 'a2'); 如果不特别指定下标,每增加一数组项,下标自增12、array当作映射表来用,实际上这也是array最重要的用法。这时作为key可以数字也可以是字符串下面定义了电话区号和城市的映射表,如下 $map = array( '010' => '北京', '0755' => '深圳', ...... ); 如果要查0755对应的是哪个城市就可以用map['0755']查出另外再举个例子,页面上经常会有下拉列表,那么如果要生成区号-城市下拉列表的话就要 echo '<select>'; foreach($map as $code = > $city){ //双引号总的变量可以用{}括起来 echo "<option value = '{$code}'>{$city}</option>" } echo '</select>'; `` 输入就是 ` <select><option value='010'> 北京</option><option value='0755'> 深圳</option></select>`

小旋风柴进 2019-12-02 02:01:41 0 浏览量 回答数 0

回答

本期答案 1、现在假设参与人数为:n=8;指定出列数:m=4; 那么第一个出列的数为:4 . . . 2、数组结构示意图: 3、设出列元素的下标为t,初始值为:t=0,可以得到一个规律: t=(t+m-1)%n=(0+4-1)%8=3; 那么数组下标为3的人出列。出列一个元素之后,数组的规模:n-1;然后出列位置后面的元素向前移动。 import java.util.Scanner; public class Tree1 { int[] a=new int[20]; //定义成员编号数组 int n; //定义参与人数的属性 public static void main(String[] args) { Scanner input=new Scanner(System.in); Tree1 l=new Tree1(); System.out.println("请输入参与人数的整数值:"); l.n=input.nextInt(); int m=0; System.out.println("请输入出列的整数值:"); m=input.nextInt(); for(int i=0;i<l.n;i++) { l.a[i]=i+1; } System.out.println("*************"); int t=0; while(l.n>0) { //利用循环将所有人员出列 t=(t+m-1)%l.n; //得到出列人员的下标 System.out.print("\t"+l.a[t]); for(int j=t+1;j<l.n;j++) { //利用循环将出列人员位置后面的数组元素前移 l.a[j-1]=l.a[j]; } l.n--; //出列一个人员之后参与人员数目n-1 } }

答题小助手 2020-03-19 17:42:46 0 浏览量 回答数 0

回答

需要组织一组数量不确定的数据,通过循环迭代处理的时候我们使用集合类。map适合通过一个索引寻找一个记录的情况,比如说记录单词和单词出现的次数;记录用户名和密码。list适合,list适合需要顺序的集合,可以通过下标像数组那样访问list。set不关心顺序,表示一个集合。

蛮大人123 2019-12-02 02:39:51 0 浏览量 回答数 0

回答

因为getline()数组s的下标是从0开始的,这个函数的for循环,如果改成i=1开始,将从s[1]开始赋值,会导致s[0]的值是乱码,可能造成一些无法预测的执行结果

a123456678 2019-12-02 02:17:49 0 浏览量 回答数 0

回答

this的指向有问题,在方法的最开始定义constself=this;循环的时候使用self代替thisfor(variteminself.listDate) 因为forin中的item是当前的索引(下标),可以使用forof替换 for(letiofarr) forin不建议遍历数组,遍历顺序有可能不是按照实际数组的内部顺序,使用forin会遍历数组所有的可枚举属性,包括原型。

爱吃鱼的程序员 2020-06-23 00:36:32 0 浏览量 回答数 0

回答

最明显的区别是 ArrrayList底层的数据结构是数组,支持随机访问,而 LinkedList 的底层数据结构是双向循环链表,不支持随机访问。使用下标访问一个元素,ArrayList 的时间复杂度是 O(1),而 LinkedList 是 O(n)。

游客pklijor6gytpx 2019-12-02 03:06:59 0 浏览量 回答数 0

回答

首先树的儿子会有很多的,为了解决儿子很多且不定的情况: 也采用二叉树的存储结构类型,但做了一点改进: 左节点vp表示大儿子,右节点hp表示兄弟,这样“树”就变成“二叉树” 的结构了。 右节点串在一起,表示同一层。 另要搞懂队列,是数组做的循环队列qu[ ], 头front ,尾rear; 又增加一个数组 level [ ]是队列qu[ ]的辅助单元, 存放 队列节点的层号,两数组 下标是一一对应的; 这两个概念是基础,一定要懂。不懂是看不下去的。 算法的核心: 1. 用队列的方法遍历所有节点,从队列中取出一个节点指针进行访问,同时 取出层号,并把这个节点的所有子节点及它的层号放入队列,以便以后取出访问; 为了启动遍历,初始队列须压入根节点; 2. 遍历时知道这个节点层号(m),就可比较,最大值(max)就是树的深度。 3. 遍历访问一个节点时,左节点vp就是大儿子,属下一层,层号是m+!, 右节点开始就是同层兄弟(第二个while就是),须压入队列,层号仍是m+1; 4. 反复循环取出队列中节点进行访问(直到为空),并把它的把有儿子压入队列 以便再次访问; 这个经典算法,不复杂, 有不明白的再追问

一键天涯 2019-12-02 01:25:57 0 浏览量 回答数 0

问题

二分法 7月11日 【今日算法】

游客ih62co2qqq5ww 2020-07-11 07:37:20 178 浏览量 回答数 1

问题

二分查找及对应经典题目

问问小秘 2020-07-03 16:20:06 3 浏览量 回答数 1

回答

提交的某字段,一定是_POST、_GET甚至_REQUEST,而不是单纯讨论$var。要防三个情况:1.提交中根本没有这个字段(如果不处理,下标不存在将直接引发运行时错误)2.提交的字段为空3.提交的字段trim()之后为空如果是原生的PHP,我推荐的步骤如下:1.原则是先预处理$_POST。2.把$_POST中所有元素的首尾空格剥了。3.把$_POST中的所有空元素扔了。4.这样,数组中幸存的元素,就都不是空的。判断元素是否存在即可。注意第二和第三步,千万不要傻傻的用foreach自己循环,最好是使用数组函数里的几个遍历函数。代码:$_POST = array_map('trim', $_POST); $_POST = array_filter($_POST); $result = array_key_exists('fieldname', $_POST); if ($result) { // do whatever you wish }这样足够简便了,不过带来的问题是可移植性差(因为需要依赖前边做过的预处理)。如果想要可移植性又好,看着又简单,判断又全面的,自己写函数去吧。

落地花开啦 2019-12-02 02:49:14 0 浏览量 回答数 0

问题

这几道经典例题帮你轻松搞透贪心算法 6月17日 【今日算法】

游客ih62co2qqq5ww 2020-06-18 15:46:11 1 浏览量 回答数 1

回答

冒泡法大家都较熟悉。其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a[i],则交换它们,一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理,即完成排序。下面列出其代码: void bubble(int *a,int n) /*定义两个参数:数组首地址与数组大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循环的上下限*/ if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } 冒泡法原理简单,但其缺点是交换次数多,效率低。 下面介绍一种源自冒泡法但更有效率的方法“选择法”。 (2)“选择法” 选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换,提高了效率。 void choise(int *a,int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; /*给记号赋值*/ for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/ if(i!=k) { /*当k!=i是才交换,否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } } } 选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。 (3)“快速法” 快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素(一般为a[(i+j)/2],即中间元素)作为参照,把比它小的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析其代码: void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/ while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/ if(m<=n) { /*若找到且满足条件,则交换*/ temp=a[m]; a[m]=a[n]; a[n]=temp; m++; n--; } }while(m<=n); if(m<j) quick(a,m,j); /*运用递归*/ if(n>i) quick(a,i,n); } (4)“插入法” 插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序,再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。 void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; /*temp为要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数,同时把数组元素向后移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } } (5)“shell法” shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序,再缩小k值(一般取其一半),再排序,直到k=1时完成排序。下面让我们来分析其代码: void shell(int *a,int n) { int i,j,k,x; k=n/2; /*间距值*/ while(k>=1) { for(i=k;i<n;i++) { x=a[i]; j=i-k; while(j>=0&&x<a[j]) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=2; /*缩小间距值*/ } } 上面我们已经对几种排序法作了介绍,现在让我们写个主函数检验一下。 #include<stdio.h> /*别偷懒,下面的"..."代表函数体,自己加上去哦。*/ void bubble(int *a,int n) { ... } void choise(int *a,int n) { ... } void quick(int *a,int i,int j) { ... } void insert(int *a,int n) { ... } void shell(int *a,int n) { ... } /*为了打印方便,我们写一个print吧。*/[code] void print(int *a,int n) { int i; for(i=0;i<n;i++) printf("%5d",a[i]); printf("\n"); } main() { /*为了公平,我们给每个函数定义一个相同数组*/ int a1[]={13,0,5,8,1,7,21,50,9,2}; int a2[]={13,0,5,8,1,7,21,50,9,2}; int a3[]={13,0,5,8,1,7,21,50,9,2}; int a4[]={13,0,5,8,1,7,21,50,9,2}; int a5[]={13,0,5,8,1,7,21,50,9,2}; printf("the original list:"); print(a1,10); printf("according to bubble:"); bubble(a1,10); print(a1,10); printf("according to choise:"); choise(a2,10); print(a2,10); printf("according to quick:"); quick(a3,0,9); print(a3,10); printf("according to insert:"); insert(a4,10); print(a4,10); printf("according to shell:"); shell(a5,10); print(a5,10); }

云篆 2019-12-02 01:19:07 0 浏览量 回答数 0

回答

HashMap HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk1.7 和 1.8 中具体实现稍有 不同 其实1.7一个很明显需要优化的地方就是: 当 Hash 冲突严重时,在桶上形成的链表会变的越来越长,这样在查询时的效 率就会越来越低;时间复杂度为 O(N)。 因此 1.8 中重点优化了这个查询效率。 1.8 HashMap 结构图 JDK 1.8 对 HashMap 进行了修改: 最大的不同就是利用了红黑树,其由数组+链表+红黑树组成。 JDK 1.7 中,查找元素时,根据 hash 值能够快速定位到数组的具体下标, 但之后需要顺着链表依次比较才能查找到需要的元素,时间复杂度取决于链 表的长度,为 O(N)。 为了降低这部分的开销,在 JDK 1.8 中,当链表中的元素超过 8 个以后,会 将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。 JDK 1.8 使用 Node(1.7 为 Entry) 作为链表的数据结点,仍然包含 key, value,hash 和 next 四个属性。 红黑树的情况使用的是 TreeNode。 根据数组元素中,第一个结点数据类型是 Node 还是 TreeNode 可以判断该位 置下是链表还是红黑树。 核心成员变量于 1.7 类似,增加了核心变量,如下表。 属性说明TREEIFY_THRESHOLD用于判断是否需要将链表转换为红黑树的阈值,默认 为 8。 put步骤: 判断当前桶是否为空,空的就需要初始化(resize 中会判断是否进行初始 化)。 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空,为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。 如果当前桶有值( Hash 冲突),那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等,相等就赋值给 e,在第 8 步的时候会统一进 行赋值及返回。 如果当前桶为红黑树,那就要按照红黑树的方式写入数据。 如果是个链表,就需要将当前的 key、value 封装成一个新节点写入到当前桶的 后面(形成链表)。 接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。 如果在遍历过程中找到 key 相同时直接退出遍历。 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。 后判断是否需要进行扩容. get 方法看起来就要简单许多了。 首先将 key hash 之后取得所定位的桶。 如果桶为空则直接返回 null 。 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是 就直接返回 value。 如果第一个不匹配,则判断它的下一个是红黑树还是链表。 红黑树就按照树的查找方式返回值。 不然就按照链表的方式遍历匹配返回值。 从这两个核心方法(get/put)可以看出 1.8 中对大链表做了优化,修改为红黑树之 后查询效率直接提高到了 O(logn)。 但是 HashMap 原有的问题也都存在,比如在并发场景下使用时容易出现死循环。 但是为什么呢?简单分析下。 看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法,就是这里的并 发操作容易在一个桶上形成环形链表;这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环。 如下图: HashTable HashTable 容器使用 synchronized来保证线程安全,但在线程竞争激烈的情况下 HashTable 的效 率非常低下。 当一个线程访问 HashTable 的同步方法时,其他线程访问 HashTable 的同步方 法可能会进入阻塞或轮询状态。 HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有 访问它的线程都必须竞争同一把锁,假如容器里有多把锁,每一把锁用于锁容 器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就 不会存在锁竞争,从而可以有效的提高并发访问效率,这就是 ConcurrentHashMap(JDK 1.7) 使用的 锁分段技术。 ConcurrentHashMap 将数据分成一段一段的存储,然后给每一段数据配一把 锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他 线程访问。 有些方法需要跨段,比如 size() 和 containsValue(),它们可能需要锁定整个表 而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所 有段的锁。 按顺序 很重要,否则极有可能出现死锁,在 ConcurrentHashMap 内部,段数 组是 final 的,并且其成员变量实际也是 final 的,但是,仅仅是将数组声明为 final 的并不保证数组成员也是 final 的,需要实现上的保证。这可以确保不会 出现死锁,因为获得锁的顺序是固定的。 HashTable 的迭代器是强一致性的,而 ConcurrentHashMap 是弱一致的。 ConcurrentHashMap 的 get,clear,iterator 方法都是弱一致性的。 初识ConcurrentHashMap Concurrent翻译过来是并发的意思,字面理解它的作用是处理并发情况的 HashMap。 通过前面的学习,我们知道多线程并发下 HashMap 是不安全的(如死循环),更普遍 的是多线程并发下,由于堆内存对于各个线程是共享的,而 HashMap 的 put 方法 不是原子操作,假设Thread1先 put 值,然后 sleep 2秒(也可以是系统时间片切换失 去执行权),在这2秒内值被Thread2改了,Thread1“醒来”再 get 的时候发现已经不 是原来的值了,这就容易出问题。 那么如何避免这种多线程出错的情况呢? 常规思路就是给 HashMap 的 put 方法加锁(synchronized),保证同一个时刻只允 许一个线程拥有对 hashmap 有写的操作权限即可。然而假如线程1中操作耗时,其 他需要操作该 hashmap 的线程就需要在门口排队半天,严重影响用户体验, HashTable 就是这样子做的。 举个生活中的例子,很多银行除了存取钱,还支持存取贵重物品,贵重物品都放在 保险箱里,把 HashMap 和 HashTable 比作银行,结构: 把线程比作人,对应的情况如下: 多线程下用 HashMap 不确定性太高,有破产的风险,不能选;用 HashTable 不会 破产,但是用户体验不太好,那么怎样才能做到多人存取既不影响他人存值,又不 用排队呢? 有人提议搞个「银行者联盟」,多开几个像HashTable 这种「带锁」的银行就好 了,有多少人办理业务,就开多少个银行,一对一服务,这个区都是大老板,开银 行的成本都是小钱,于是「银行者联盟」成立了。 接下来的情况是这样的:比如用户A和用户B一起去银行存各自的项链,这个「银行 者联盟」操作后,然后对用户A说,1号银行现在没人你可以去那存,不用排队,然 后用户A就去1号银行存项链,1号银行把用户A接进门,马上拉闸,然后把用户A的 项链放在第x行第x个保险箱,等用户A办妥离开后,再开闸;对于用户B同理。此时 不管用户A和用户B在各自银行里面待多久都不会影响到彼此,不用担心自己的项链 被人偷换了。这就是ConcurrentHashMap的设计思路,用一个图来理解 从上图可以看出,此时锁的是对应的单个银行,而不是整个「银行者联盟」。分析 下这种设计的特点: 多个银行组成的「银行者联盟」 当有人来办理业务时,「银行者联盟」需要确定这个人去哪个银行 当此人去到指定银行办理业务后,该银行上锁,其他人不能同时执行修改操作,直 到此人离开后解锁. ConcurrentHashMap源码解析 ConcurrentHashMap 同样也分为 1.7 、1.8 版,两者在实现上略有不同。 先来看看 1.7 的实现,下面是结构图: 如图所示,是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组 加链表。主要是通过分段锁实现的。 关于分段锁 段Segment继承了重入锁ReentrantLock,有了锁的功能,每个锁控制的是一段, 当每个Segment越来越大时,锁的粒度就变得有些大了。 分段锁的优势在于保证在操作不同段 map 的时候可以并发执行,操作同段 map 的时候,进行锁的竞争和等待。这相对于直接对整个map同步 synchronized是有优势的。 缺点在于分成很多段时会比较浪费内存空间(不连续,碎片化); 操作map时竞争 同一个分段锁的概率非常小时,分段锁反而会造成更新等操作的长时间等待; 当 某个段很大时,分段锁的性能会下降。 1.7 已经解决了并发问题,并且能支持 N 个 Segment 这么多次数的并发,但依然存 在 HashMap 在 1.7 版本中的问题。 那就是查询遍历链表效率太低。 因此 1.8 做了一些数据结构上的调整。 首先来看下底层的组成结构: 其实和 1.8 HashMap 结构类似,当链表节点数超过指定阈值的话,也是会转换成红 黑树的,大体结构也是一样的。 那么 JDK 1.8 ConcurrentHashMap 到底是如何实现线程安全的? 答案:其中抛弃了原有的Segment 分段锁,而采用了 CAS + synchronized 来保证 并发安全性。(cas:比较并替换) **① 基本组成 ** 抛弃了 JDK 1.7 中原有的 Segment 分段锁,而采用了 CAS + synchronized 来 保证并发安全性。 将JDK 1.7 中存放数据的 HashEntry 改为 Node,但作用是相同的。、 我们来看看 ConcurrentHashMap 的几个重要属性. 重要组成元素 Node:链表中的元素为 Node 对象。他是链表上的一个节点,内部存储了 key、 value 值,以及他的下一 个节点的引用。这样一系列的 Node 就串成一串,组成一 个链表。 ForwardingNode:当进行扩容时,要把链表迁移到新的哈希表,在做这个操作 时,会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不 保存 key 和 value,只保存了扩容后哈希表 (nextTable)的引用。此时查找相应 node 时,需要去 nextTable 中查找。 TreeBin:当链表转为红黑树后,数组中保存的引用为 TreeBin,TreeBin 内部不保 存 key/value,他保存了 TreeNode 的 list 以及红黑树 root。 TreeNode:红黑树的节点。 **② put 方法过程 ** 存储结构定义了容器的 “形状”,那容器内的东西按照什么规则来放呢?换句话讲, 某个 key 是按 照什么逻辑放入容器的对应位置呢? 我们假设要存入的 key 为对象 x,这个过程如下 : 1、通过对象 x 的 hashCode () 方法获取其 hashCode; 2、将 hashCode 映射到数组的某个位置上; 3、把该元素存储到该位置的链表中。 put 方法用来把一个键值对存储到 map 中。代码如下: 实际调用的是 putVal 方 法,第三个参数传入 false,控制 key 存在时覆盖原来的值。 请先看完代码注释,有个大致的了解,然后我们更加详细的学习一下: 判断存储的 key、value 是否为空,若为空,则抛出异常,否则,进入步骤 2。 计算 key 的 hash 值,随后进入自旋,该自旋可以确保成功插入数据,若 table 表为空或者长度为 0,则初始化 table 表,否则,进入步骤 3。 根据 key 的 hash 值取出 table 表中的结点元素,若取出的结点为空(该桶为 空),则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则,进入 步骤 4。 若该结点的的 hash 值为 MOVED(-1),则对该桶中的结点进行转移,否则, 进入步骤 5。 5 . 对桶中的第一个结点(即 table 表中的结点)进行加锁,对该桶进行遍历,桶中 的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等,则根据标识选择是 否进行更新操作(用给定的 value 值替换该结点的 value 值),若遍历完桶仍 没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点,则直接新生 一个结点并赋值为之前后一个结点的下一个结点。进入步骤 6。 若 binCount 值达到红黑树转化的阈值,则将桶中的结构转化为红黑树存储, 后,增加 binCount 的值。 如果桶中的第一个元素的 hash 值大于 0,说明是链表结构,则对链表插入或者 更新。 如果桶中的第一个元素是 TreeBin,说明是红黑树结构,则按照红黑树的方式进 行插入或者更新。 在锁的保护下,插入或者更新完毕后,如果是链表结构,需要判断链表中元素 的数量是否超过 8(默认),一旦超过,就需要考虑进行数组扩容,或者是链表 转红黑树。 扩容 什么时候会扩容? 使用put()添加元素时会调用addCount(),内部检查sizeCtl看是否需要扩容。 tryPresize()被调用,此方法被调用有两个调用点: 链表转红黑树(put()时检查)时如果table容量小于64(MIN_TREEIFY_CAPACITY),则会 触发扩容。 调用putAll()之类一次性加入大量元素,会触发扩容。 addCount() addCount()与tryPresize()实现很相似,我们先以addCount()分析下扩容逻辑: **1.链表转红黑树 ** 首先我们要理解为什么 Map 需要扩容,这是因为我们采用哈希表存储数据,当固定 大小的哈希表存 储数据越来越多时,链表长度会越来越长,这会造成 put 和 get 的 性能下降。此时我们希望哈希表中多一些桶位,预防链表继续堆积的更长。 ConcurrentHashMap 有链表转红黑树的操作,以提高查找的速度,红黑树时间复 杂度为 O (logn),而链表是 O (n/2),因此只在 O (logn)<O (n/2) 时才会进行转换, 也就是以 8 作为分界点。 接下来我们分析 treeifyBin 方法代码,这个代码中会选择是把此时保存数据所在的 链表转为红黑树,还是对整个哈希表扩容。 treeifyBin 不一定就会进行红黑树转换,也可能是仅仅做数组扩容。 构造完TreeBin这个空节点之后,就开始构造红黑树,首先是第一个节点,左右 子节点设置为空,作为红黑树的root节点,设置为黑色,父节点为空。 然后在每次添加完一个节点之后,都会调用balanceInsertion方法来维持这是一 个红黑树的属性和平衡性。红黑树所有操作的复杂度都是O(logn),所以当元素量比 较大的时候,效率也很高。 **数组扩容 ** 我们大致了解了 ConcurrentHashMap 的存储结构,那么我们思考一个问题,当数 组中保存的链表越来越多,那么再存储进来的元素大概率会插入到现有的链表中, 而不是使用数组中剩下的空位。 这样会造成数组中保存的链表越来越长,由此导致 哈希表查找速度下降,从 O (1) 慢慢趋近于链表 的时间复杂度 O (n/2),这显然违背 了哈希表的初衷。 所以 ConcurrentHashMap 会做一个操作, 称为扩容。也就是把数组长度变大,增 加更多的空位出来,终目的就是预防链表过长,这样查找的时间复杂度才会趋向于 O (1)。扩容的操作并不会在数组没有空位时才进行,因为在桶位快满时, 新保存元 素更大的概率会命中已经使用的位置,那么可能后几个桶位很难被使用,而链表却 越来 越长了。ConcurrentHashMap 会在更合适的时机进行扩容,通常是在数组中 75% 的位置被使用 时。 其实以上内容和 HashMap 类似,ConcurrentHashMap 此外提供了线程安全的保 证,它主要是通 过 CAS 和 Synchronized 关键字来实现,我们在源码分析中再详细 来看。 我们做一下总结: 1、ConcurrentHashMap 采用数组 + 链表 + 红黑树的存储结构; 2、存入的 Key 值通过自己的 hashCode 映射到数组的相应位置; 3、ConcurrentHashMap 为保障查询效率,在特定的时候会对数据增加长度,这个 操作叫做扩容; 4、当链表长度增加到 8 时,可能会触发链表转为红黑树(数组长度如果小于 64, 优先扩容,具体 看后面源码分析)。 接下来,我们的源码分析就从 ConcurrentHashMap 的构成、保存元素、哈希算 法、扩容、查找数 据这几个方面来进行 扩容后数组容量为原来的 2 倍。 **数据迁移( 扩容时的线程安全) ** ConcurrentHashMap 的扩容时机和 HashMap 相同,都是在 put 方法的后一步 检查是否需要扩容,如果需要则进行扩容,但两者扩容的过程完全不同, ConcurrentHashMap 扩容的方法叫做 transfer,从 put 方法的 addCount 方法进 去,就能找到 transfer 方法,transfer 方法的主要思路是: 首先需要把老数组的值全部拷贝到扩容之后的新数组上,先从数组的队尾开始 拷贝; 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷 贝到新数组时,把 原数组槽点赋值为转移节点; 这时如果有新数据正好需要 put 到此槽点时,发现槽点为转移节点,就会一直 等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化的; 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置成转移 节点; 直到所有数组数据都拷贝到新数组时,直接把新数组整个赋值给数组容器,拷 贝完成 putTreeVal()与此方法遍历方式类似不再介绍。  ④ get 方法过程 ConcurrentHashMap 读的话,就比较简单,先获取数组的下标,然后通过判断数 组下标的 key 是 否和我们的 key 相等,相等的话直接返回,如果下标的槽点是链表 或红黑树的话,分别调用相应的 查找数据的方法,整体思路和 HashMap 很像,源 码如下: 计算 hash 值。 根据 hash 值找到数组对应位置: (n – 1) & h。 根据该位置处结点性质进行相应查找。 如果该位置为 null,那么直接返回 null。 如果该位置处的结点刚好就是需要的,返回该结点的值即可。 如果该位置结点的 hash 值小于 0,说明正在扩容,或者是红黑树。 如果以上 3 条都不满足,那就是链表,进行遍历比对即可。 ** 初始化数组 ** 数组初始化时,首先通过自旋来保证一定可以初始化成功,然后通过 CAS 设置 SIZECTL 变量的值,来保证同一时刻只能有一个线程对数组进行初始化,CAS 成功 之后,还会再次判断当前数组是否已经初始化完成,如果已经初始化完成,就不会 再次初始化,通过自旋 + CAS + 双重 check 等 手段保证了数组初始化时的线程安 全,源码如下: 里面有个关键的值 sizeCtl,这个值有多个含义。 1、-1 代表有线程正在创建 table; 2、-N 代表有 N-1 个线程正在复制 table; 3、在 table 被初始化前,代表 根据构造函数传入的值计算出的应被初始化的大小; 4、在 table 被初始化后,则被 设置为 table 大小 的 75%,代表 table 的容量(数组容量)。 initTable 中使用到 1 和 4,2 和 3 在其它方法中会有使用。下面我们可以先看下 ConcurrentHashMap 的构造方法,里面会使用上面的 3 最后来回顾总结下HashMap和ConcurrentHashMap对比 ConcurrentHashMap 和 HashMap 两者的相同之处: 1.数组、链表结构几乎相同,所以底层对数据结构的操作思路是相同的(只是思路 相同,底层实现 不同); 2.都实现了 Map 接口,继承了 AbstractMap 抽象类,所以大多数的方法也都是相 同的, HashMap 有的方法,ConcurrentHashMap 几乎都有,所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时,无需关心两者之间的兼容问题 不同点: 1.红黑树结构略有不同,HashMap 的红黑树中的节点叫做 TreeNode,TreeNode 不仅仅有属 性,还维护着红黑树的结构,比如说查找,新增等等; ConcurrentHashMap 中红黑树被拆分成 两块,TreeNode 仅仅维护的属性和查找 功能,新增了 TreeBin,来维护红黑树结构,并负责根 节点的加锁和解锁; 2.新增 ForwardingNode (转移)节点,扩容的时候会使用到,通过使用该节点, 来保证扩容时的线程安全。

剑曼红尘 2020-03-25 11:21:44 0 浏览量 回答数 0

回答

一、简单排序算法   由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境   下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么   问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法:   这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:   #include <iostream>   using namespace std;   void BubbleSort(int * pData, int Count)   {   int iTemp;   for (int i=0; i<Count; i++)   {   for (int j=Count-1; j>i; j--)   {   if (pData[j]<pData[j-1])   {   iTemp = pData[j-1];   pData[j-1] = pData[j];   pData[j] = iTemp;   }   }   }   }   void main()   {   int data[7] = {10,9,8,7,6,5,4};   BubbleSort(data,7);   for (int i=0; i<7; i++)   {   cout<<data[i]<<" ";   }   cout<<endl;   system("PAUSE");   }   倒序(最糟情况)   第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)   第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:6次   其他:   第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)   第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换,   显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。   写成公式就是1/2*(n-1)*n。   现在注意,我们给出O方法的定义:   若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没学好数学呀,对于编程数学是非常重要的。。。)   现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)   =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。   再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的   有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),   复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的   原因,我们通常都是通过循环次数来对比算法。 2.交换法:   交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。   #include <iostream.h>   void ExchangeSort(int* pData,int Count)   {   int iTemp;   for(int i=0;i<Count-1;i++)   { //共(count-1)轮,每轮得到一个最小值   for(int j=i+1;j<Count;j++)   { //每次从剩下的数字中寻找最小值,于当前最小值相比,如果小则交换   if(pData[j]9,10,8,7->8,10,9,7->7,10,9,8(交换3次)   第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:6次   其他:   第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)   第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样   也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以   只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法:   现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)   这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中   选择最小的与第二个交换,这样往复下去。   #include <iostream.h>   void SelectSort(int* pData,int Count)   {   int iTemp;   int iPos;   for(int i=0;i<Count-1;i++)   {   iTemp = pData;   iPos = i;   for(int j=i+1;j<Count;j++)   {   if(pData[j]<iTemp)   {   iTemp = pData[j];   iPos = j;   }   }   pData[iPos] = pData;   pData = iTemp;   }   }   void main()   {   int data[] = {10,9,8,7,6,5,4};   SelectSort(data,7);   for (int i=0;i<7;i++)   cout<<data<<" ";   cout<<"\n";   }   倒序(最糟情况)   第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)   第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)   第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次)   循环次数:6次   交换次数:2次   其他:   第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)   第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)   第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。   我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n   所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法:   插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张   #include <iostream.h>   void InsertSort(int* pData,int Count)   {   int iTemp;   int iPos;   for(int i=1;i<Count;i++)   {   iTemp = pData[i]; //保存要插入的数   iPos = i-1; //被插入的数组数字个数   while((iPos>=0) && (iTemp9,10,8,7(交换1次)(循环1次)   第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)   第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)   循环次数:6次   交换次数:3次   其他:   第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)   第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)   循环次数:4次   交换次数:2次   上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,   因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<=   1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单   排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似   选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’   而这里显然多了一些,所以我们浪费了时间。   最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法   高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。   它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后   把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使   用这个过程(最容易的方法——递归)。   1.快速排序:   #include <iostream.h>   void run(int* pData,int left,int right)   {   int i,j;   int middle,iTemp;   i = left;   j = right;   middle = pData[left];   do{   while((pData[i]<middle) && (i<right))//从左扫描大于中值的数   i++;    while((pData[j]>middle) && (j>left))//从右扫描大于中值的数   j--;   if(i<=j)//找到了一对值   {   //交换   iTemp = pData[i];   pData[i] = pData[j];   pData[j] = iTemp;   i++;   j--;   }   }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)   //当左边部分有值(left<j),递归左半边   if(left<j)   run(pData,left,j);   //当右边部分有值(right>i),递归右半边   if(right>i)   run(pData,i,right);   }   void QuickSort(int* pData,int Count)   {   run(pData,0,Count-1);   }   void main()   {   int data[] = {10,9,8,7,6,5,4};   QuickSort(data,7);   for (int i=0;i<7;i++)   cout<<data<<" ";   cout<<"\n";   }   这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况   1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。   2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。   第一层递归,循环n次,第二层循环2*(n/2)......   所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n   所以算法复杂度为O(log2(n)*n)   其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变   成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全   不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。   如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢

知与谁同 2019-12-02 01:18:20 0 浏览量 回答数 0

回答

遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么? 遍历方式有以下几种: for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。 最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。如果没有实现该接口,表示不支持 Random Access,如LinkedList。 推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下: ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下: 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。插入元素的时候,也需要做一次元素复制操作,缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换? 数组转 List:使用 Arrays. asList(array) 进行转换。List 转数组:使用 List 自带的 toArray() 方法。 代码示例: ArrayList 和 LinkedList 的区别是什么? 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全; 综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。 补充:数据结构基础之双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么? 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。性能:ArrayList 在性能方面要优于 Vector。扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性? ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差。 LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList? ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样: 为什么 ArrayList 的 elementData 加上 transient 修饰? ArrayList 中的数组定义如下: private transient Object[] elementData; 再看一下 ArrayList 的定义: public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现: 每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。 Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理? HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。 HashSet如何检查重复?HashSet是如何保证数据不可重复的? 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。 以下是HashSet 部分源码: hashCode()与equals()的相关规定: 如果两个对象相等,则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值,它们也不一定是相等的 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么? Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别? 相同点:都是返回第一个元素,并在队列中删除返回的对象。 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。 代码示例: Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理? HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题: resize 扩容优化引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程? 当我们put的时候,首先计算 key的hash值,这里调用了 hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。 HashMap的扩容操作是怎么实现的? ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容; ②.每次扩展的时候,都是扩展2倍; ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。 在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的? 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突: 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) } 这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); JDK1.8新增红黑树 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn); 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的: 使用链地址法(使用散列表)来链接拥有相同hash值的数据;使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; **能否使用任何类作为 Map 的 key? **可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点: 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K? 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况; 如果使用Object作为HashMap的Key,应该怎么办呢? 答:重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞; 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置; 那怎么解决呢? HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均; 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题; HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢? 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢? 答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的; HashMap 与 HashTable 有什么区别? 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它; 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap? 对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。) HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的; 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。 两者的对比图: HashTable: JDK1.7的ConcurrentHashMap: JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗?实现原理是什么? JDK1.7 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下: 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。 结构如下: 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 辅助工具类 Array 和 ArrayList 有何区别? Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。 如何实现 Array 和 List 之间的转换? Array 转 List: Arrays. asList(array) ;List 转 Array:List 的 toArray() 方法。 comparable 和 comparator的区别? comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素? TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式, 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较; 第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。

剑曼红尘 2020-03-24 14:41:57 0 浏览量 回答数 0

回答

选择法的算法: 假设需要对10个数进行排序,那么首先找出10个数里面的最小数,并和这个10个数的第一个(下标0)交换位置,剩下9个数(这9个数都比刚才选出来那个数大),再选出这9个数中的最小的数,和第二个位置的数(下标1)交换,于是还剩8个数(这8个数都比刚才选出来的大).. 依次类推,当还剩两个数时,选出两个数的最小者放在第9个位置(下标8),于是就只剩下一个数了。这个数已经在最后一位(下标9),不用再选择了。所以10个数排序,一共需要选择9次(n个数排序就需要选择n-1次)。#include "Stdio.h"void main(){ void sa(int array[],int n); int array[10],i; printf("enter the array:\n"); for(i=0;i<10;i++) scanf("%d",&array[i]); sa(array,10); printf("the sorted array:\n"); for(i=0;i<10;i++) printf("%d\t",array[i]); getch();}void sa(int array[],int n){ int i,j,k,temp; for(i=0;i<10;i++) { k=i; for(j=i+1;j<n;j++) if(array[j]<array[k]) k=j; temp=array[k]; array[k]=array[i]; array[i]=temp; }} main() { int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf ("%d,",&a[i]); for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} } for(i=1;i<11;i++) printf("%5d,",a[i] ); printf("\n"); }--------------冒泡算法冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (1)初始 R[1..n]为无序区。 (2)第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key<R[j].key,则交换R[j+1]和R[j]的内容。 第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。 (3)第二趟扫描 扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上…… 最后,经过n-1 趟扫描可得到有序区R[1..n] 注意: 第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R上,结果是R[1..i]变为新的有序区。 2、冒泡排序过程示例 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程 3、排序算法 (1)分析 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。 (2)具体算法 void BubbleSort(SeqList R) { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j; Boolean exchange; //交换标志 for(i=1;i<n;i++){ //最多做n-1趟排序 exchange=FALSE; //本趟排序开始前,交换标志应为假 for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key<R[j].key){//交换记录 R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange) //本趟排序未发生交换,提前终止算法 return; } //endfor(外循环) } //BubbleSort 4、算法分析 (1)算法的最好时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值: Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。 (2)算法的最坏时间复杂度 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。 (3)算法的平均时间复杂度为O(n2) 虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。 (4)算法稳定性 冒泡排序是就地排序,且它是稳定的。 5、算法改进 上述的冒泡排序还可做如下的改进: (1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R[1..lastExchange-1]是有序区,R[lastExchange..n]是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况: 只有最轻的气泡位于R[n]的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。 需要n-1趟扫描完成排序情况: 当只有最重的气泡位于R[1]的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。 【例】对初始关键字序列:94,10,12,18,42,44,45,67就需七趟扫描。 ②造成不对称性的原因 每趟扫描仅能使最重气泡"下沉"一个位置,因此使位于顶端的最重气泡下沉到底部时,需做n-1趟扫描。 ③改进不对称性的方法 在排序过程中交替改变扫描方向,可改进不对称性。 勤奋一点网上都可找到,这是帮你拷的。祝你进步。

祁同伟 2019-12-02 01:17:20 0 浏览量 回答数 0

问题

阅读《C陷阱与缺陷》的知识增量 第一章 词法陷阱 第二章 语法陷阱 第三章 语义?400报错

爱吃鱼的程序员 2020-06-04 15:05:01 2 浏览量 回答数 1

问题

阅读《C陷阱与缺陷》的知识增量 第一章 词法陷阱 第二章 语法陷阱 第三章 语义?400报错

爱吃鱼的程序员 2020-06-04 12:00:05 3 浏览量 回答数 1

回答

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将给出详细的说明。 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。 现在,让我们开始吧: 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include <iostream.h> void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义: 若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的。。。) 现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因,我们通常都是通过循环次数来对比算法。 2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[j]<pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法: 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中选择最小的与第二个交换,这样往复下去。 #include <iostream.h> void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(int j=i+1;j<Count;j++) { if(pData[j]<iTemp) { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次 其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法: 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include <iostream.h> void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0) && (iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次 其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些,所以我们浪费了时间。 最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。 1.快速排序: #include <iostream.h> void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } void QuickSort(int* pData,int Count) { run(pData,0,Count-1); } void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。 2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。 第一层递归,循环n次,第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变 成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全 不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。 如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢于快速排序(因为要重组堆)。 三、其他排序 1.双向冒泡: 通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。 代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。 反正我认为这是一段有趣的代码,值得一看。 #include <iostream.h> void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1; //反向的部分 for(i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } right = t-1; }while(left<=right); } void main() { int data[] = {10,9,8,7,6,5,4}; Bubble2Sort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 2.SHELL排序 这个排序非常复杂,看了程序就知道了。 首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。 工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序 以次类推。 #include <iostream.h> void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1; int iTemp; int k,s,w; for(int i=0;i<4;i++) { k = step[i]; s = -k; for(int j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp<pData[w]) && (w>=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } } void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++) cout<<data[i]<<" "; cout<<"\n"; } 呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因 避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。 四、基于模板的通用排序: 这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。 MyData.h文件 /////////////////////////////////////////////////////// class CMyData { public: CMyData(int Index,char* strData); CMyData(); virtual ~CMyData(); int m_iIndex; int GetDataSize(){ return m_iDataSize; }; const char* GetData(){ return m_strDatamember; }; //这里重载了操作符: CMyData& operator =(CMyData &SrcData); bool operator <(CMyData& data ); bool operator >(CMyData& data ); private: char* m_strDatamember; int m_iDataSize; }; //////////////////////////////////////////////////////// MyData.cpp文件 //////////////////////////////////////////////////////// CMyData::CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) { } CMyData::~CMyData() { if(m_strDatamember != NULL) delete[] m_strDatamember; m_strDatamember = NULL; } CMyData::CMyData(int Index,char* strData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) { m_iDataSize = strlen(strData); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,strData); } CMyData& CMyData::operator =(CMyData &SrcData) { m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,SrcData.GetData()); return *this; } bool CMyData::operator <(CMyData& data ) { return m_iIndex<data.m_iIndex; } bool CMyData::operator >(CMyData& data ) { return m_iIndex>data.m_iIndex; } /////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// //主程序部分 #include <iostream.h> #include "MyData.h" template <class T> void run(T* pData,int left,int right) { int i,j; T middle,iTemp; i = left; j = right; //下面的比较都调用我们重载的操作符函数 middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } template <class T> void QuickSort(T* pData,int Count) { run(pData,0,Count-1); } void main() { CMyData data[] = { CMyData(8,"xulion"), CMyData(7,"sanzoo"), CMyData(6,"wangjun"), CMyData(5,"VCKBASE"), CMyData(4,"jacky2000"), CMyData(3,"cwally"), CMyData(2,"VCUSER"), CMyData(1,"isdong") }; QuickSort(data,8); for (int i=0;i<8;i++) cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; cout<<"\n"; }

沉默术士 2019-12-02 01:19:06 0 浏览量 回答数 0

问题

【javascript学习全家桶】934道javascript热门问题,阿里百位技术专家答疑解惑

管理贝贝 2019-12-01 20:07:22 6202 浏览量 回答数 1

回答

所谓交换,就是根据序列中两个记录值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。常见的交换排序有冒泡排序(Bubble Sort),鸡尾酒排序(Cocktail Sort),奇偶排序(OddEven Sort),地精排序(Gnome Sort),快速排序(Quick Sort),臭皮匠排序(Stooge Sort),梳排序(Comb Sort),Bogo排序(Bogo sort)。下面介绍前六种: (一)冒泡排序 最差时间复杂度:O(n^2) 最优时间复杂度:O(n) 平均时间复杂度:O(n^2) 最差空间复杂度:总共O(n),需要辅助空间O(1) 稳定性:稳定 冒泡排序(Bubble Sort),它重复地走访过要排序的数列,一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序算法的运作如下: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤,除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 实现代码: [cpp] view plaincopy void BubbleSort(int *a, int len) { for (int i=0; i<len; i++) { for (int j=len-1; j>i; j--) { if (a[j]<a[j-1]) swap(a[j], a[j-1]); } } } (二)鸡尾酒排序 最差时间复杂度:O(n^2) 最优时间复杂度:O(n) 平均时间复杂度:O(n^2) 稳定性:稳定 鸡尾酒排序(Cocktail sort),是冒泡排序的一种变形。它与冒泡排序的不同之处在于排序时是以双向在序列中进行排序。数组中的数字本是无规律的排放,先对数组从左到右进行冒泡排序(升序),把最大值放到最右端,然后对数组从右到左进行冒泡排序(降序),把最小的数字放到最左端。然后再以此类推,以此改变冒泡的方向,并不断缩小未排序元素的范围。直到在一趟双向冒泡后没有发生交换,排序结束。 实现代码: [cpp] view plaincopy void CocktailSort(int* a, int len) { int bottom = 0; int top = len-1; bool swapped = true; while (swapped) { swapped = false; for (int i=bottom; i<top; i++) { if (a[i]>a[i+1]) { swap(a[i], a[i+1]); swapped = true; } } top = top-1; for (int i=top; i>bottom; i--) { if (a[i]<a[i-1]) { swap(a[i], a[i-1]); swapped = true; } } bottom = bottom+1; } } (三)奇偶排序 最差时间复杂度:O(n^2) 稳定性:稳定 奇偶排序(OddEven Sort),是一种相对简单的排序算法,最初发明用于有本地互联的并行计算。此算法通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换。下一步重复该操作,但针对所有的(偶-奇)位置数字对。如此交替下去,直到不发生交换,则排序结束。 在并行计算排序中,使用该算法,每个处理器对应处理一个值,并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作,交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。但在单处理器串行运行此算法,类似冒泡排序,较为简单但效率并不特别高。 实现代码: [cpp] view plaincopy void OddEvenSort(int *a, int len) { bool swapped = true; while (swapped) { swapped = false; for (int i=0; i<len-1; i=i+2) { if (a[i]>a[i+1]) { swap(a[i], a[i+1]); swapped = true; } } for (int i=1; i<len-1; i=i+2) { if (a[i]>a[i+1]) { swap(a[i], a[i+1]); swapped = true; } } } } (四)地精排序 最差时间复杂度:O(n^2) 最优时间复杂度:O(n) 平均时间复杂度:O(n^2) 稳定性:稳定 地精排序(Gnome Sort),被Dick Grune称为最简单的排序算法。整个算法只有一层循环,默认情况下前进冒泡,一旦遇到冒泡的情况发生就往回冒,直到把这个数字放好,然后继续前进,前进到数组最后一个数结束。此排序算法虽然代码极短,但效率不高。 实现代码: [cpp] view plaincopy void GnomeSort(int *a, int len) { int i=0; while (i<len) { if (i==0 || a[i-1]<=a[i]){ i++; } else { swap(a[i], a[i-1]); i--; } } } (五)快速排序 最差时间复杂度:O(n^2) 最优时间复杂度:O(nlogn) 平均时间复杂度:O(nlogn) 稳定性:不稳定 快速排序(Quick Sort),使用分治法策略来把一个串行分为两个子串行,左边子串的值总小于右边的子串。此算法的三个步骤: 1.分解:将数组A[l...r]划分成两个(可能空)子数组A[l...p-1]和A[p+1...r],使得A[l...p-1]中的每个元素都小于等于A(p),而且,小于等于A[p+1...r]中的元素。下标p也在这个划分过程中计算。 2.解决:通过递归调用快速排序,对数组A[l...p-1]和A[p+1...r]排序。 3.合并:因为两个子数组时就地排序,将它们的合并并不需要操作,整个数组A[l..r]已经排序。 实现代码(其他实现方法见“三种快速排序算法的实现”): [cpp] view plaincopy int partition(int* a, int left, int right) { int x = a[right]; int i = left-1, j = right; for (;;) { while(a[++i] < x) { } while(a[--j] > x) { if(j==left) break;} if(i < j) swap(a[i], a[j]); else break; } swap(a[i],a[right]); return i; } void quickSort(int* a, int left, int right) { if (left<right) { int p = partition(a, left, right); quickSort(a, left, p-1); quickSort(a, p+1, right); } } (六)臭皮匠排序 最差时间复杂度:O(n^2.7) 臭皮匠排序(Stooge Sort),是一种低效的排序算法,在《算法导论》第二版第7章的思考题中被提到,是由Howard Fine等教授提出的所谓“漂亮的”排序算法。将数列平分为三个子串,依次递归排序前两个子串、后两个子串、前两个子串,最后确保整个数列有序。此算法在最坏情况下的递归式为T(n) = 3T(2n/3) + 1。由主定理很容易知道它的算法复杂性为:T(n) = O(n^log(3/2, 3))。很显然log(3/2, 3))>2,也就是说这个算法比插入排序的O(n^2)性能还差。 实现代码: [cpp] view plaincopy void StoogeSort(int *a, int i, int j) { if(a[i]>a[j]) swap(a[i], a[j]); if((i+1)>=j) return; int k = (j-i+1)/3; StoogeSort(a, i, j-k); StoogeSort(a, i+k, j); StoogeSort(a, i, j-k); }

琴瑟 2019-12-02 01:18:10 0 浏览量 回答数 0

回答

1. <form name="f1"> <select name="s1" onchange="chg(document.f1.s1,document.f1.s2)"> <option value="江西">江西</option> <option value="福建">福建</option> </select> <select name="s2"> <option value="1">1</option> </select> </form> <script> //创建对象,数据,值,文本 function obj(aData,aValue,aText){ this.Data=aData; this.Value=aValue; this.Text=aText; } //设置选项数据数组,可以添加多个参数为"源地址,选择值,选择文本" var Set_data=new Array( new obj('江西','南昌','南昌'), new obj('江西','九江','九江'), new obj('福建','福州','福州'), new obj('福建','厦门','厦门') ); //该函数接受两个参数——两个下拉菜单 function chg(parent,child){ //以父菜单的选中选项的值,子菜单,和选项数数据组为参数调用chg函数 chgComitem(parent.options[parent.selectedIndex].value,child,Set_data); } function chgComitem(parentValue,child,objs){ //改变子菜单 //1.以子菜单为参数调用函数 DelAllComitem(child); //2.遍历所有的选项数据 for(i=0;i<objs.length;i++){ //如果选项数据的Data与父菜单选中值一样的话 if (objs[i].Data==parentValue) //3.以子菜单,选项数据的值,选项数据的文本作为参数调用AddComitem AddComitem(child,objs[i].Value,objs[i].Text); } } //1.删除子菜单的所有元素 function DelAllComitem(aList){ //传入的是select元素,让options全为null for(i=aList.options.length-1;i>=0;i--) aList.options[i]=null; } //3.添加子菜单的元素 function AddComitem(aList,aValue,aText){ //用传入的文本和值来创建option var aOption=new Option(aText,aValue); //插入option(注:length属性比最大下标大1) aList.options[aList.options.length]=aOption; } </script> 2. <%@ page language="Java" import="java.util.*" pageEncoding="UTF-8"%> <% String path = request.getContextPath(); String basePath = request.getScheme()+"://"+request.getServerName()+":"+request.getServerPort()+path+"/"; %> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <HTML> <HEAD> <TITLE> New Document </TITLE> <META NAME="Generator" CONTENT="EditPlus"> <META NAME="Author" CONTENT=""> <META NAME="Keywords" CONTENT=""> <META NAME="Description" CONTENT=""> <script language="JavaScript" type="text/javascript"> //定义了城市的二维数组,里面的顺序跟省份的顺序是相同的。通过selectedIndex获得省份的下标值来得到相应的城市数组 var city=[ ["北京","天津","上海","重庆"], ["南京","苏州","南通","常州"], ["福州","福安","龙岩","南平"], ["广州","潮阳","潮州","澄海"], ["兰州","白银","定西","敦煌"] ]; function getCity(){ //获得省份下拉框的对象 var sltProvince=document.form1.province; //获得城市下拉框的对象 var sltCity=document.form1.city; //得到对应省份的城市数组 var provinceCity=city[sltProvince.selectedIndex - 1]; //清空城市下拉框,仅留提示选项 sltCity.length=1; //将城市数组中的值填充到城市下拉框中 for(var i=0;i<provinceCity.length;i++){ sltCity[i+1]=new Option(provinceCity[i],provinceCity[i]); } } </script> </HEAD> <BODY> <FORM METHOD=POST ACTION="" name="form1"> <SELECT NAME="province" onChange="getCity()"> <OPTION VALUE="0">请选择所在省份 </OPTION> <OPTION VALUE="直辖市">直辖市 </OPTION> <OPTION VALUE="江苏省">江苏省 </OPTION> <OPTION VALUE="福建省">福建省 </OPTION> <OPTION VALUE="广东省">广东省 </OPTION> <OPTION VALUE="甘肃省">甘肃省 </OPTION> </SELECT> <SELECT NAME="city"> <OPTION VALUE="0">请选择所在城市 </OPTION> </SELECT> </FORM> </BODY> </HTML> 3. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Untitled Document</title> <script> function setSecond(obj){ var val = obj.value; if(val == 'en'){ var sec = document.getElementById('second'); sec.options[0] = new Option("one","one"); sec.options[1] = new Option("two","two"); }else{ var sec = document.getElementById('second'); sec.options[0] = new Option("一","one"); sec.options[1] = new Option("二","two");//可设置循环配置,也可一个一个配置 } } </script> </head> <body> <div> <select id="first" onchange="setSecond(this)"> <option value="en">en</option> <option value="zh">zh</option> </select> </div> <div> <select id="second"> </select> </div> </body> </html>

云栖技术 2019-12-02 02:31:30 0 浏览量 回答数 0

问题

洗牌算法和它的应用场景 7月20日 【今日算法】

游客ih62co2qqq5ww 2020-07-27 13:19:28 3 浏览量 回答数 0

问题

图解!24张图彻底弄懂九大常见数据结构! 7月22日 【今日算法】

游客ih62co2qqq5ww 2020-07-27 13:19:32 6 浏览量 回答数 1

回答

本人学习数据结构时看到的不错的总结,共享一下了 文件有一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字; 排序是将文件按关键字的递增(减)顺序排列; 排序文件中有相同的关键字时,若排序后相对次序保持不变的称稳定排序,否则称不稳定排序; 在排序过程中,文件放在内存中处理不涉及数据的内、外存交换的称内部排序,反之称外部排序; 排序算法的基本操作:1)比较关键字的大小;2)改变指向记录的指针或移动记录本身。 评价排序方法的标准:1)执行时间;2)所需辅助空间,辅助空间为O(1)称就地排序;另要注意算法的复杂程度。 若关键字类型没有比较运算符,可事先定义宏或函数表示比较运算。 8.2插入排序 8.2.1直接插入排序 实现过程: void insertsort(seqlist R) { int i, j; for(i=2;i<=n;i++) if(R[i].key< R[i-1].key{ R[0]=R[i];j=i-1; do{R[j+1]=R[j];j--;} while(R[0].key R[j+1]=R[0]; } } 复制代码 算法中引入监视哨R[0]的作用是:1)保存 R[i] 复制代码 的副本;2)简化边界条件,防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.2.2希尔排序 实现过程:是将直接插入排序的间隔变为d。d的取值要注意:1)最后一次必为1;2)避免d值互为倍数; 关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25; 算法的平均时间是O(n^1.25);是一种就地的不稳定的排序; 8.3交换排序 8.3.1冒泡排序 实现过程:从下到上相邻两个比较,按小在上原则扫描一次,确定最小值,重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2;记录移动次数最小为0,最大为3n(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.3.2快速排序 实现过程:将第一个值作为基准,设置i,j指针交替从两头与基准比较,有交换后,交换j,i。i=j时确定基准,并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2; 算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是O(nlog2n);辅助空间为O(log2n);是一种不稳定排序; 8.4选择排序 8.4.1直接选择排序 实现过程:选择序列中最小的插入第一位,在剩余的序列中重复上一步,共重复n-1次。 关键字比较次数为n(n-1)/2;记录移动次数最小为0,最大为3(n-1); 算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序; 8.4.2堆排序 实现过程:把序列按层次填入完全二叉树,调整位置使双亲大于或小于孩子,建立初始大根或小根堆,调整树根与最后一个叶子的位置,排除该叶子重新调整位置。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序; 8.5归并排序 实现过程:将初始序列分为2个一组,最后单数轮空,对每一组排序后作为一个单元,对2个单元排序,直到结束。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序; 8.6分配排序 8.6.1箱排序 实现过程:按关键字的取值范围确定箱子的个数,将序列按关键字放入箱中,输出非空箱的关键字。 在桶内分配和收集,及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。 8.6.2基数排序 实现过程:按基数设置箱子,对关键字从低位到高位依次进行箱排序。 算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序; 8.7各种内部排序方法的比较和选择 按平均时间复杂度分为: 1) 平方阶排序:直接插入、直接选择、冒泡排序; 2) 线性对数阶:快速排序、堆排序、归并排序; 3) 指数阶:希尔排序; 4) 线性阶:箱排序、基数排序。 选择合适排序方法的因素:1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。 结论: 1) 若规模较小可采用直接插入或直接选择排序; 2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序; 3) 若规模较大可采用快速排序、堆排序或归并排序; 4) 任何借助于比较的排序,至少需要O(nlog2n)的时间,箱排序和基数排序只适用于有明显结构特征的关键字; 5) 有的语言没有提供指针及递归,使归并、快速、基数排序算法复杂; 6) 记录规模较大时为避免大量移动记录可用链表作为存储结构,如插入、归并、基数排序,但快速、堆排序在链表上难以实现,可提取关键字建立索引表,然后对索引表排序。 附二: 第八章排序 ************************************************************************************* 记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。 排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作:比较关键字大小;改变指向记录的指针或移动记录。 ·存储结构:顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的,否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序),反之,若存在数据的内外存交换,则称之为外排序。 内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。 ************************************************************************************* 插入排序:·直接插入排序: ·逐个向前插入到合适位置。 ·哨兵(监视哨)有两个作用: ·作为临变量存放 R[i] 复制代码 ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2; ·希尔排序: ·等间隔的数据比较并按要求顺序排列,最后间隔为1。 ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25),比较次数为(n^1.25);移动次数为(1.6n^1.25); 交换排序:·冒泡排序:·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个,后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为n(n-1)/2;移动次数为3n(n-1)/2; ·快速排序:·以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n),比较次数为n(n-1)/2; 选择排序:·直接选择排序: ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2; ·堆排序 ·建堆:按层次将数据填入完全二叉树,从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。 ·堆排序是就地不稳定的排序,时间复杂度为O(nlog2n),不适宜于记录数较少的文件。。 归并排序: ·先两个一组排序,形成(n+1)/2组,再将两组并一组,直到剩下一组为止。 ·归并排序是非就地稳定排序,时间复杂度是O(nlog2n), 分配排序:·箱排序: ·按关键字的取值范围确定箱子数,按关键字投入箱子,链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n). ·基数排序:·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序,时间复杂度是O(d*n+d*rd)。 各种排序方法的比较和选择: ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现; ·关键字的结构及其初始状态; ·对稳定性的要求; ·语言工具的条件; ·存储结构; ·时间和辅助空间复杂度。 排序(sort)或分类 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 1.被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。 注意: 在不易产生混淆时,将关键字项简称为关键字。 2.排序运算的依据--关键字 用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。 排序的稳定性 当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。 在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。 排序方法的分类 1.按是否涉及数据的内、外存交换分 在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。 注意: ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。 2.按策略划分内部排序方法 可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2.待排文件的常用存储方式 (1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。 3.排序算法性能评价 (1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。

马铭芳 2019-12-02 01:19:07 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 云栖号物联网 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站 云栖号弹性计算 阿里云云栖号 云栖号案例 云栖号直播