Menu

冒泡排序,选择排序,插入排序,希尔排序的区别以及空间复杂度

2018年2月9日 - 算法,数据结构

冒泡排序

比较数组中的元素,相邻两个数依次作比较,每次循环,比较一次,两层循环,所以时间复杂度为n*2;

 

选择排序:

选择排序是冒泡排序的升级,分为有序和无序两个区别,第一个数默认为有序,无序的数,遍历找出最小值与有序数做比较,因为每次只有一层循环,所以时间复杂度为o(n)

1、算法思想:

将待排序序列分为两部分,一部分为有序序列,另一部分为无序序列。第一趟:从a[0]到a[n-1]中找到最小的数a[i],然后将a[i]与a[0]交换,第二趟:从a[1]到a[n-1]中找到最小的数a[j],然后将a[j]与a[1]交换,第三趟:从a[2]到a[n-1]中找到最小的数a[k],然后将a[k]与a[2]交换 ……

2、实例分析:

{13,15,37,89,60,39,12,109,56,72}

第一趟 :12  {15,37,89,60,39,13,109,56,72}

第二趟:12 ,13 {37,89,60,39,15,109,56,72}

第三趟:12 ,13 ,15 {89,60,39,37,109,56,72}

 

插入排序:

从第一个元素开始,默认为排序的,然后从无序的元素的第一个元素与第一个元素相比较,插入到有序元素中去,所以排序稳定,时间复杂度为o(n)

插入排序

1、算法思想:

1〉从第一个元素开始,该元素可以认为已经被排序

2〉取出第一个未排序元素存放在临时变量temp中,在已经排序的元素序列中从后往前扫描,逐一比较

3〉如果temp小于已排序元素,将该元素移到下个位置

4〉重复步骤3〉,直到找到已排序的元素小于或者等于

2、实例分析:

{13,15,37,89,60,39,12,109,56,72}

第一趟:   13 {15,37,89,60,39,12,109,56,72}     temp = 15

temp>13

第二趟:   13 ,15 { 37,89,60,39,12,109,56,72}      temp = 37

temp>15         temp>13
第三趟: 13,15 ,37  {89,60,39,12,109,56,72}     temp = 89

temp>37       temp>15       temp>13

第三趟: 13,15 ,37 ,89 {60,39,12,109,56,72}     temp =60

temp< 89:60<->89          13,15 ,37 , 60,89 {39,12,109,56,72}

temp>37        temp>15        temp>13

第四趟: 13,15 ,37 , 60,89  {39,12,109,56,72}        temp = 39

temp<89:  39<->89           13,15 ,37 , 60,39,89 {12,109,56,72}

temp<60  :   39<->60           13,15 ,37 , 39,60,89 {12,109,56,72}

temp>37      temp>15         temp >13

第五趟:    13,15 ,37 , 39,60,89 {12,109,56,72}       temp = 12

temp<89 :12<->89                   13,15 ,37 ,39,60, 12,89 {109,56,72}

temp<60:12<->60                    13,15 ,37 ,39,12,60,89 {109,56,72}

temp<39 :12<->39                   13,15 ,37 ,12,39,60,89 {109,56,72}

temp<37 :12<->37                    13,15 ,12 ,37 ,39,60,89 {109,56,72}

temp<15: 12<->15                   13,12,15 ,37 ,39,60,89 {109,56,72}

temp<13 :12<->13                     12,13,15 ,37 ,39,60,89 {109,56,72}

第六趟:  12,13,15 ,37 ,39,60,89 {109,56,72}           temp = 109

……

 

希尔排序:加强版直接插入排序,也是不稳定的,将整个无序序列分成若干个子序列,然后进行插入排序,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: