一起学习交流~

排序-08-侏儒排序,最简单的排序

算法 laomuji 12个月前 (10-11) 336次浏览 已收录 0个评论

一、什么是侏儒排序

侏儒排序(Gnome sort或Stupid sort)是一种排序算法,最初由伊朗计算机工程师Hamid Sarbazi-Azad博士(谢里夫理工大学计算机工程教授)于2000年提出并被称为“愚蠢排序”(不是 与bogosort混淆),然后由Dick Grune描述并命名为“gnome sort”。 它是一种类似于插入排序的排序算法,除了将元素移动到适当的位置是通过一系列交换完成的,如冒泡排序。 它在概念上很简单,不需要嵌套循环。 平均或预期的运行时间是O(n2),但如果列表最初几乎排序,则倾向于O(n)。

侏儒排序只有一层循环,非常简单,但是使用场景有限,基本上只用于快排序好的数据

下面是排序步骤

原始数组:3 1 6 6 9 4 7
swap:1 3
1 3 6 6 9 4 7
swap:4 9
1 3 6 6 4 9 7
swap:4 6
1 3 6 4 6 9 7
swap:4 6
1 3 4 6 6 9 7
swap:7 9
1 3 4 6 6 7 9
排序后:1 3 4 6 6 7 9

二、具体代码

#include<iostream>
using namespace std;
//侏儒排序,只有一层循环,最简单的排序
//平均或预期的运行时间是O(n2),但如果列表最初几乎排序,则倾向于O(n)。
//使用场景在几乎已经排完的情况下

void gnomeSort(int nums[],int length)
{
	for (int i = 1; i < length;)
	{
		if (nums[i] < nums[i - 1])
		{
			swap(nums[i], nums[i - 1]);
			if (i > 1)i--;
		}
		else 
		{
			i++;
		}
	}
}

int main()
{
	int nums[] = { 3,1,6,6,9,4,7 };
	gnomeSort(nums, 7);
	for (int i = 0; i < 7; i++)
	{
		cout << nums[i] << " ";
	}
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论