热门问题
时间线
聊天
视角

侏儒排序

来自维基百科,自由的百科全书

侏儒排序
Remove ads

侏儒排序(英语:Gnome Sort)或愚人排序(英语:Stupid Sort)是一种排序算法,最初在2000年由伊朗计算机工程师哈米德·萨尔巴齐-阿扎德(Hamid Sarbazi-Azad,谢里夫理工大学计算机工程教授)提出,他称之为“愚人排序”[1]。此后迪克·格鲁纳英语Dick Grune也描述了这一算法,称其为“侏儒排序”[2]。此算法类似于插入排序,但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单,甚至不需要嵌套循环。它的平均运行时间 ,如果列表已经排序好则只需 的运行时间。[3]

事实速览 侏儒排序, 概况 ...
Remove ads
Remove ads

解释 

下面是侏儒排序的伪代码,其中使用的数组是下标从零开始的

procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

样例 

给定一个未排序的数组a = [5, 3, 2, 4],侏儒排序在while循环中执行以下步骤。粗体表示pos变量当前所指的元素。

更多信息 当前数组, 下一步操作 ...
Remove ads

实现示例

# Julia Sample : GnomeSort

function GnomeSort(A)
	pos = 1
	while pos<length(A)+1
		if (pos==1) || (A[pos]>=A[pos-1])
			pos+=1
		else
			A[pos],A[pos-1] = A[pos-1],A[pos] 
			pos-=1
		end
	end
	return A
end

# Main Code
A = [16,586,1,31,354,43,3]
println(A)              # Original Array
println(GnomeSort(A))   # Gnome Sort Array

参考文献

Loading content...

外部链接&nbsp;

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads