排序>>交换排序>>地精排序
List:
|
1 2 3 4 |
0.概念+伪代码+示例分析 1.地精排序实现 2.改进 3.Question |
- start
基本概念:
维基百科:http://en.wikipedia.org/wiki/Gnome_sort(目前只有英文版的)
地精排序又称侏儒排序，类似于插入排序，但是将一个数放入其正确位置的交换同冒泡排序（一系列交换）
简单，只有一层循环，
时间复杂度O(n^2)，最优复杂度O(n),平均时间复杂度O(n^2)
其实思想很简单,往前冒泡，一旦发生数据交换，就往回冒泡，直到把被交换数字放入正确位置，之后，继续前进
伪代码(来自于维基百科)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
procedure gnomeSort(a[]) pos := 1 while pos < length(a) if (a[pos] >= a[pos-1]) pos := pos + 1 else swap a[pos] and a[pos-1] if (pos > 1) pos := pos - 1 else pos := pos + 1 end if end if end while end procedure |
例子：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
[5, 3, 2, 4] #输入数组 i=0, i=i+1=1 #初始，i=0 ，直接i+=1 cmp l[0]= 5 l[1]= 3 change -> [3, 5, 2, 4] swap, i=i-1=0 #发生交换，i=i-1 i=0, i=i+1=1 #i=0,i+=1 cmp l[0]= 3 l[1]= 5 no swap, i=i+1=1 #无交换，i+=1 cmp l[1]= 5 l[2]= 2 change -> [3, 2, 5, 4] #交换 swap, i=i-1=1 #i=i-1，反向冒泡开始 cmp l[0]= 3 l[1]= 2 change -> [2, 3, 5, 4] swap, i=i-1=0 # 交换 i=0, i=i+1=1 cmp l[0]= 2 l[1]= 3 no swap, i=i+1=1 #无交换，i+=1 cmp l[1]= 3 l[2]= 5 no swap, i=i+1=2 #无交换，i+=1 cmp l[2]= 5 l[3]= 4 change -> [2, 3, 4, 5] swap, i=i-1=2 #交换,i-=1 cmp l[1]= 3 l[2]= 4 no swap>3 l[2]= 4 no swapt-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-always" style=" margin-top: 12px; margin-bottom: 12px; font-size: 13px !important; line-height: 15px !important;">
基本概念: 维基百科:http://en.wikipedia.org/wiki/Gnome_sort(目前只有英文版的)
地精排序又称侏儒排序，类似于插入排序，但是将一个数放入其正确位置的交换同冒泡排序（一系列交换） 简单，只有一层循环， 时间复杂度O(n^2)，最优复杂度O(n),平均时间复杂度O(n^2) 其实思想很简单,往前冒泡，一旦发生数据交换，就往回冒泡，直到把被交换数字放入正确位置，之后，继续前进 伪代码(来自于维基百科)
例子：
|
