侏儒排序

十大经典排序算法

侏儒排序（Gnome Sort）或愚人排序（Stupid Sort），有的也叫地精排序，最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad（谢里夫理工大学计算机工程教授）提出，他称之为“愚人排序”。它的实现原理是使用一个指针 index ，每次都和前面的元素比较，如果大于或等于他前面的元素，index 指针就往后移一步，否则就和他前面的元素进行交换，交换完之后 index 要往前移一步，继续和他前面的比较……，如下图所示。

private void gnomeSort(int[] nums) {
    int index = 0;
    int length = nums.length;
    while (index < length) {
        if (index == 0 || nums[index] >= nums[index - 1])
            index++;// 如果当前元素不比前面的小，index指针就往后移。
        else {// 如果当前元素比前面的小，就和前面的交换，交换完之后，index指针往前移一步。
            swap(nums, index, index - 1);
            index--;
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

相关链接