Gnome Sort 的 C++ 程序?
server side programmingprogrammingc++
在这里我们将看到 gnome sort 的工作原理。这是另一种排序算法。如果列表已经排序,则在这种方法中需要 O(n) 时间。因此最佳情况的时间复杂度为 O(n)。但平均情况和最坏情况的复杂度为 O(n^2)。现在让我们看一下算法,以了解这种排序技术。
算法
gnomeSort(arr, n)
begin index := 0 while index < n, do if index is 0, then index := index + 1 end if 如果 arr[index] >= arr[index -1], then index := index + 1 else 交换 arr[index] 和 arr[index - 1] index := index - 1 end if 完成 结束
示例
#include<iostream> using namespace std; void gnomeSort(int arr[], int n){ int index = 0; while(index < n){ if(index == 0) index++; if(arr[index] >= arr[index - 1]){ //如果元素大于前一个元素 index++; } else { swap(arr[index], arr[index - 1]); index--; } } } main() { int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40}; int n = sizeof(data)/sizeof(data[0]); cout << "排序序列"; gnomeSort(data, n); for(int i = 0; i <n;i++){ cout << data[i] << &" &";; } }
输出
排序序列 13 20 32 35 40 54 74 98 98 154