lancelei

一个很少见的算法--------地精排序(Gnome Sort)
博主复习准备考研专业课,网上瞎看算法资料的时候,发现一个叫做“地精排序”的算法引起了我的兴趣(为了部落!)。查了查...
扫描右侧二维码阅读全文
11
2018/10

一个很少见的算法--------地精排序(Gnome Sort)

博主复习准备考研专业课,网上瞎看算法资料的时候,发现一个叫做“地精排序”的算法引起了我的兴趣(为了部落!)。查了查资料,现在给大家简单介绍一下这个算法。

经典排序算法 - 地精排序Gnome Sort

先上wiki的官方介绍 https://en.wikipedia.org/wiki/Gnome_sort (目前只有英文版),没有条件FQ的宝宝不要着急,我可以慢慢介绍。

Gnome sort (or Stupid sort) is a sorting algorithm originally proposed
by an Iranian computer scientist Hamid Sarbazi-Azad (Professor of
Computer Engineering at Sharif University of Technology) in 2000 and
called "stupid sort"(not to be confused with bogosort), and then
later on described by Dick Grune and named "gnome sort"

It is a sorting algorithm which is similar to insertion sort, except
that moving an element to its proper place is accomplished by a series
of swaps, as in bubble sort. It is conceptually simple, requiring no
nested loops. The average, or expected, running time is O(n2), but
tends towards O(n) if the list is initially almost sorted.

The algorithm always finds the first place where two adjacent elements
are in the wrong order and swaps them. It takes advantage of the fact
that performing a swap can introduce a new out-of-order adjacent pair
only next to the two swapped elements. It does not assume that
elements forward of the current position are sorted, so it only needs
to check the position directly previous to the swapped elements.

是不是有点懵了,简单解释下,这是一种类似于插入排序的算法,但是又有冒泡排序在里面。地精排序被称为最简单的排序,不需要循环嵌套,只需要一个循环就可以解决。预期时间复杂度O(N^2),如果原始列表较为规律,或者几乎排序,则时间复杂度趋向于O(n)。算法默认情况下前进冒泡,一旦遇到冒泡的情况发生就往回冒,直到把这个数字放到正确的位置为止。

Sorting_gnomesort_anim.gif

语言的描述是空洞的,我们来用代码解释一下。

JAVA语言版本:

static void gnome_sort(int[] unsorted)
{
    int i = 0;
    while (i < unsorted.Length)
    {
        if (i == 0 || unsorted[i - 1] <= unsorted[i])
        {
            i++;
        }
        else
        {
            int tmp = unsorted[i];
            unsorted[i] = unsorted[i - 1];
            unsorted[i - 1] = tmp;
            i--;
        }
    }
}

C++版本:

template<class T>

void gnome_sort_1(T data[], int n, bool comparator(T, T))

{
   int i = 1;
   while (i < n)
    {
       if (i > 0 && comparator(data[i], data[i-1]))
       {
           swap(data[i], data[i-1]);
           i--;
       }else
       {
           i++;
       }
    }
}

是不是超级简单,只需要一个循环就可以解决所有问题。现在我们用文字介绍下它排序的过程

先设一个i=0,然后从头开始判断,当(i < a)不成立,排序结束。a为待排数组元素个数

所以,如何控制i的值是这个算法的关键

例如待排数组:

[7 1 4 0 5 8]

看一下具体的排序过程


[ i = 0 ]时啥也不干,先让i自增1,达到值为1才开始真正的比较

交换前7 1 4 0 5 8

交换后7 1 4 0 5 8


[ i = 1 ]比较7和1,此时发生交换,只要发生交换i就减1

交换前7 1 4 0 5 8

交换后1 7 4 0 5 8


[ i = 0 ]又成0了,啥也不干,自增变成1再说

交换前1 7 4 0 5 8

交换后1 7 4 0 5 8


[ i = 1 ]比较1和7,不交换,i自增1

交换前1 7 4 0 5 8

交换后1 7 4 0 5 8


[ i = 2 ]比较7和4,交换,i减1

交换前1 7 4 0 5 8

交换后1 4 7 0 5 8


[ i = 1 ]比较1和4,不交换i自增1

交换前1 4 7 0 5 8

交换后1 4 7 0 5 8


[ i = 2 ]比较4和7,不交换i自增1

交换前1 4 7 0 5 8

交换后1 4 7 0 5 8


[ i = 3 ]比较7和0,交换,i减1

交换前1 4 7 0 5 8

交换后1 4 0 7 5 8


[ i = 2 ]比较4和0,交换,i减1

交换前1 4 0 7 5 8

交换后1 0 4 7 5 8


[ i = 1 ]比较1和0,交换,i减1

交换前1 0 4 7 5 8

交换后0 1 4 7 5 8


[ i = 0 ]先自增到1再运算

交换前0 1 4 7 5 8

交换后0 1 4 7 5 8


[ i = 1 ]比较0和1,不交换i自增1
[ i = 2 ]比较1和4,不交换i自增1
[ i = 3 ]比较4和7,不交换i自增1


[ i = 4 ]比较7和5,交换,i减1

交换前0 1 4 7 5 8

交换后0 1 4 5 7 8


[ i = 3 ]比较4和5,不交换i自增1

交换前0 1 4 5 7 8

交换后0 1 4 5 7 8


[ i = 4 ]比较5和7,不交换i自增1

交换前0 1 4 5 7 8

交换后0 1 4 5 7 8


[ i = 5 ]比较7和8,不交换i自增1

交换前0 1 4 5 7 8

交换后0 1 4 5 7 8


重点来了

[ i = 6]表达式(i < n)不成立,排序结束

然后顺序输出排序结果[0 1 4 5 7 8]即可

完结撒花,技术有限,有问题希望各位大佬轻拍

Last modification:October 24th, 2018 at 05:02 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment