什么是地精排序？

📝地精排序(Gnome)，也称侏儒排序

和冒泡排序相类似，比较相邻元素，在决定是否交换，类似于插入算法，但是地精排序的特点是，只需要一层循环即可完成排序，能有效的减少交换的回合数

为什么叫地精排序？

地精排序在2000年由Dr. Hamid Sarbazi-Azad 提出的时候被称作 Stupid Sort，可见其思想的简单性。后来，这个算法被Dick Grune 描述成地精排序Gnome Sort

​ Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
—Dick Grune

💕这就是萌萌哒的Gnome(Tuinkabouter)

算法思想

可以看作冒泡排序的简化版，冒泡排序是将元素不断的上浮，而地精排序是出现需要交换的元素时往回推，直到到达数组头部，或者无任何交换

先定义一个用于测试的数组📌

int[] Arr = {12,26,58,20,14,10,23,45,48,10,95,13};

这里需要判断是要前进还是后退，所以先定义一个移动指针 index 初始化为1

int index = 1;

然后使用 While 做循环体，当 index 超过数组大小的时候代表已经移动到末尾，证明数组已经排序完毕

while(index < Arr.length){
    //判断/交换
}

判断这里就很简单，只需要判断当前元素是否小于上一个元素即可，但是要注意如果 index 等于0时，在减1下标就变成了-1，所以提前判断 index 是否大于0😮

if(index > 0 && Arr[index] < Arr[index - 1]){
	//交换 Arr[index] & Arr[index - 1]
	index--;
}
else{
	index++;
}

这里的交换数据格式不固定，可以按照使用习惯来写😊

可以看到算法很简练，当出现交换数据时 移动指针就 - 1 否则 + 1

最后验证一下交换后的数组😋

for(int i = 0;i < Arr.length ;i++){
	System.out.print(Arr[i] + " ");
}
//10 10 12 13 14 20 23 26 45 48 58 95 

完整代码：

int[] Arr = {12,26,58,20,14,10,23,45,48,10,95,13};

int index = 1;
while(index < Arr.length){
	if(index > 0 && Arr[index] < Arr[index - 1]){
		Arr[index - 1] = Arr[index - 1] + Arr[index];
		Arr[index] = Arr[index - 1] - Arr[index];
		Arr[index - 1] = Arr[index - 1] - Arr[index];
		index--;
	}
	else{
		index++;
	}
}
for(int i = 0;i < Arr.length ;i++){
	System.out.print(Arr[i] + " ");
}

完美散花~🎉

算法扩展

算法复杂度：

$最差情况 ：T(n) = O(n^2)$

$最好情况：T(n) =O(n)$

最后：

虽然地精排序被归为奇葩排序之一，但也有一定的应用场景，如在元素大部分有序的情况下，地精排序可以有效的减少排序的循环回合数🎉🎉🎉