臭皮匠排序

十大经典排序算法

臭皮匠排序（Stooge Sort）是一种低效的递归排序算法，实现步骤如下：

• 在排序区间内如果最后一个值小于第一个值，则交换这两个数。
• 如果当前区间元素数量大于等于 3 ：
  • 使用臭皮匠排序法递归排序前 2/3 的元素。
  • 使用臭皮匠排序法递归排序后 2/3 的元素。
  • 再次使用臭皮匠排序法递归排序前 2/3 的元素。

private void stoogeSort(int[] nums) {
    stoogeSort(nums, 0, nums.length - 1);
}

private void stoogeSort(int[] nums, int left, int right) {
    if (nums[left] > nums[right])// 如果最后一个值小于第一个值，则交换这两个数
        swap(nums, left, right);
    if (right - left + 1 >= 3) {// 如果当前集合元素数量大于等于3，执行下面操作
        int third = (right - left + 1) / 3;
        stoogeSort(nums, left, right - third);// 使用臭皮匠排序法排序前2/3的元素
        stoogeSort(nums, left + third, right);// 使用臭皮匠排序法排序后2/3的元素
        stoogeSort(nums, left, right - third);// 再次使用臭皮匠排序法排序前2/3的元素
    }
}

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

相关链接