数据结构&算法实践—地精排序及改进_程序人生

数据结构&算法实践—地精排序及改进

admin

2023-07-31 00:37:06

0次

排序>>交换排序>>地精排序

List:

1234	0.概念+伪代码+示例分析1.地精排序实现2.改进3.Question

start

基本概念:

维基百科:http://en.wikipedia.org/wiki/Gnome_sort(目前只有英文版的)

地精排序又称侏儒排序，类似于插入排序，但是将一个数放入其正确位置的交换同冒泡排序（一系列交换）

简单，只有一层循环，

时间复杂度O(n^2)，最优复杂度O(n),平均时间复杂度O(n^2)

其实思想很简单,往前冒泡，一旦发生数据交换，就往回冒泡，直到把被交换数字放入正确位置，之后，继续前进

伪代码(来自于维基百科)

123456789101112131415

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 whileend procedure

例子：

12345678910111213141516171819202122232425262728293031323334353637

[5, 3, 2, 4] #输入数组 i=0, i=i+1=1 #初始，i=0 ，直接i+=1 cmp l[0]= 5 l[1]= 3change -> [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]= 5no swap, i=i+1=1 #无交换，i+=1 cmp l[1]= 5 l[2]= 2change -> [3, 2, 5, 4] #交换swap, i=i–1=1 #i=i-1，反向冒泡开始 cmp l[0]= 3 l[1]= 2change -> [2, 3, 5, 4]swap, i=i–1=0 # 交换 i=0, i=i+1=1cmp l[0]= 2 l[1]= 3no swap, i=i+1=1 #无交换，i+=1 cmp l[1]= 3 l[2]= 5no swap, i=i+1=2 #无交换，i+=1 cmp l[2]= 5 l[3]= 4change -> [2, 3, 4, 5]swap, i=i–1=2 #交换,i-=1 cmp l[1]= 3 l[2]= 4no swap>3 l[2]= 4no 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;\”>

1234	0.概念+伪代码+示例分析1.地精排序实现2.改进3.Question

start