首页 > 代码库 > Gnome排序算法
Gnome排序算法
Gnome排序（地精排序），起初由Hamid Sarbazi-Azad 于2000年提出，并被称为stupid排序，后来被Dick Grune描述并命名为“地精排序”，作为一个排序算法，和插入排序类似，除了移动一个元素到最终的位置，是通过交换一系列的元素实现，就像冒泡排序一样。概念上十分简单，不需要嵌套循环。时间复杂度为O(n2),但是如果初始数列基本有序，时间复杂度将降为O(n)。实际上Gnome算法可以和插入排序算法一样快。平均运行时间为O(n2).
Gnome排序算法总是查找最开始逆序的一对相邻数，并交换位置，基于交换两元素后将引入一个新的相邻逆序对，并没有假定当前位置之后的元素已经有序.
本文地址：http://www.cnblogs.com/archimedes/p/gnome-sort-algorithm.html，转载请注明源地址。
下面gnome排序算法的伪代码，使用0起始索引数组:
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 end if end if end whileend procedure
实例
给定一个无序数组, a = [5, 3, 2, 4], gnome排序将在while循环中执行如下的步骤. "current position"采用加粗黑体:
| 当前数组 | 操作 |
|---|---|
| [5, 3, 2, 4] | a[pos] < a[pos-1], 交换: |
| [3, 5, 2, 4] | a[pos] >= a[pos-1], pos自增: |
| [3, 5, 2, 4] | a[pos] < a[pos-1], 交换并且pos > 1, pos自减: |
| [3, 2, 5, 4] | a[pos] < a[pos-1], 交换并且pos <= 1, pos自增: |
| [2, 3, 5, 4] | a[pos] >= a[pos-1], pos自增: |
| [2, 3, 5, 4] | a[pos] < a[pos-1], 交换并且pos > 1, pos自减: |
| [2, 3, 4, 5] | a[pos] >= a[pos-1], pos自增: |
| [2, 3, 4, 5] | a[pos] >= a[pos-1], pos自增: |
| [2, 3, 4, 5] | pos == length(a), 完成. |
C代码如下：
// Completed on 2014.10.9 10:01// Language: C99//// 版权所有（C）codingwu (mail: oskernel@126.com) // 博客地址：http://www.cnblogs.com/archimedes/#include<stdio.h> #include<stdbool.h> void swap(int *a, int *b) //交换两元素的值{ int t; t = *a; *a = *b; *b = t;}void printArray(int a[], int count) //打印数组元素{ int i; for(i = 0; i < count; i++) printf("%d ",a[i]); printf("\n");}void gnome_sort(int *a, int len) //gnome排序算法{ int pos = 1; while(pos < len) { if(a[pos] >= a[pos - 1]) { pos++; } else { swap(&a[pos], &a[pos - 1]); if(pos > 1) pos--; } }}int main(void) { int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1}; int n = sizeof(a) / sizeof(*a); printArray(a, n); gnome_sort(a, n); printArray(a, n); return 0;}
优化：
gnome算法还可以通过引入一个变量，用于存储每次返回到数组前面的位置来进行优化。采用这样的优化，gnome排序将成为一个变种插入排序，下面优化后gnome排序算法的伪代码，使用0起始索引数组:
procedure optimizedGnomeSort(a[]) pos := 1 last := 0 while pos < length(a) if (a[pos] >= a[pos-1]) if (last != 0) pos := last last := 0 end if pos := pos + 1 else swap a[pos] and a[pos-1] if (pos > 1) if (last == 0) last := pos end if pos := pos - 1 else pos := pos + 1 end if end if end whileend procedure
C代码如下：
// Completed on 2014.10.9 10:31// Language: C99//// 版权所有（C）codingwu (mail: oskernel@126.com) // 博客地址：http://www.cnblogs.com/archimedes/#include<stdio.h> #include<stdbool.h> void swap(int *a, int *b) //交换两元素的值{ int t; t = *a; *a = *b; *b = t;}void printArray(int a[], int count) //打印数组元素{ int i; for(i = 0; i < count; i++) printf("%d ",a[i]); printf("\n");}void optimizedGnome_Sort(int *a, int len) //优化后的gnome排序{ int last, pos; last = 0; pos = 1; while(pos < len) { if(a[pos] >= a[pos - 1]) { if(last != 0) { pos = last; last = 0; } pos++; } else { swap(&a[pos], &a[pos - 1]); if(pos > 1) { if(last == 0) last = pos; pos--; } else { pos++; } } }}int main(void) { int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1}; int n = sizeof(a) / sizeof(*a); printArray(a, n); optimizedGnome_Sort(a, n); printArray(a, n); return 0;}
Gnome排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。