递归插入排序

Question

我遇到了以下问题，特别是在某些代码提供给我的部分。

问题描述：给定一个整数数组，return一个包含相同整数的数组，使用插入排序从大到小排序。我们将使用仅考虑从给定索引开始到另一个索引结束的数组部分的约定。这样，递归调用可以遍历数组的任何部分。初始调用将传入索引 0 和最后一个元素的索引。

插入排序([2, 1, 3, -2, 8], 0, 4) → [8, 3, 2, 1, -2]
insertionSort([2, 6, -4], 0, 2) → [6, 2, -4]
插入排序([2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22], 0, 10) → [22, 20, 18, 16, 14, 12, 10, 8, 6, 4、2]

给出的代码：

public int[] insertionSort(int[] nums, int begin, int end) {

}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

我遇到的问题是理解 "element" 变量在 "insert" 方法中的含义。

这是我为它编写的代码。

public int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums.length;
   insert(nums, begin, end, element);
   insertionSort(nums, begin, end);

  }
  return nums;
}

void insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

这是我从我的代码中得到的错误：

Answer 1

所以你做错的是将元素作为 nums.length 传递，元素是要插入的数字，也就是说在每次递归调用之后它将是第 (begin+1) 个元素，你将继续增加 1，因为数组的那部分（从 0 开始）已经排序。因此，下一次将在 begin+1 上调用 insertionsort 以结束。这是下面的工作示例。

public class Main
{

    public static int[] insertionSort(int[] nums, int begin, int end) {
 if(begin >= end) return nums;
 else if (begin < end){

   int element = nums[begin+1];
   insert(nums, 0, begin, element);
   insertionSort(nums, begin+1, end);

  }
  return nums;
}

static void  insert(int[] nums, int begin, int end, int element) {
  int index=end;
  while(index>=begin && nums[index]<element) {
    index--;
  }
  for(int i=end; i>index; i--) {
    nums[i+1] = nums[i];
  }
  nums[index+1] = element;
}

    public static void main(String[] args) {
        int[] a = {3,41,0,10};
        int[] t = insertionSort(a, 0, 3);
        for (int i =0; i<4; i++){
            System.out.println(t[i]);
        }
    }
}

Answer 2

我想这或多或少就是你想要做的。

class RecursiveInsertionSort {

    public static void main(String[ ] args) {
        int[] input1 = {2, 1, 3, -2, 8};
        int[] input2 = {2, 6, -4};
        int[] input3 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22};

        int[] res1 = insertionSort(input1, 0, 4);
        // res1 = [8, 3, 2, 1, -2]

        int[] res2 = insertionSort(input2, 0, 2);
        // res2 = [6, 2, -4]

        int[] res3 = insertionSort(input3, 0, 10);
        // res3 = [22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
    }

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return nums; // We are done
        }

        // Sort the first n-1 elements
        insertionSort(nums, begin, end - 1);

        // Insert the nth element in the first n-1 elements array
        insert(nums, begin, end - 1, nums[end]);

        return nums;
    }

    static void insert(int[] nums, int begin, int end, int element) {
        int index = end;
        while(index >= begin && nums[index] < element) {
            index--;
        }
        for(int i = end; i > index; i--) {
            nums[i + 1] = nums[i];
        }
        nums[index + 1] = element;
    }
}

Answer 3

非递归版本：

    public static int[] insertionSort(int[] nums, int begin, int end) {

        for (int i = begin + 1; i <= end; i++) {
            insert(nums, begin, i - 1, nums[i]);
        }

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }

递归版本：

    public static int[] insertionSort(int[] nums, int begin, int end) {
        if (begin>=end) {
            return nums;
        }

        insertionSort(nums, begin, end-1);
        insert(nums, begin, end-1, nums[end]);

        return nums;
    }

    public static void insert(int[] nums, int begin, int end, int element) {
        int index=end;
        while(index>=begin && nums[index]<element) {
            index--;
        }
        for(int i=end; i>index; i--) {
            nums[i+1] = nums[i];
        }
        nums[index+1] = element;
    }

    public static void main(String[] args) {
        int[] is = new int[]{5,6,7,2};
        System.out.println();
        insertionSort(is, 0, is.length - 1);
        System.out.println(Arrays.toString(is));
    }

Answer 4

以下解决方案正在通过您的所有测试用例。你的插入方法应该是这样的

public static int[] insertionSort(int[] nums, int begin, int end) {
if (begin >= end) {
    return nums;
}

for (int i = 0; i < end; i++) {
    insert(nums, i, end - 1, nums[end]);
}
return nums;

}

以下是供您快速参考的完整解决方案。

public class Solution {

public static void main(String[] args) {
    int[] input1 = { 2, 1, 3, -2, 8 };
    int[] result1 = insertionSort(input1, 0, 4);
    printArray(result1);
    int[] input2 = { 2, 6, -4 };
    int[] result2 = insertionSort(input2, 0, 2);
    printArray(result2);
    int[] input3 = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 };
    int[] result3 = insertionSort(input3, 0, 10);
    printArray(result3);
    int[] input4 = { 6, 6, 6, };
    int[] result4 = insertionSort(input4, 0, 2);
    printArray(result4);
    int[] input5 = { 8 };
    int[] result5 = insertionSort(input5, 0, 0);
    printArray(result5);
}

public static void printArray(int[] input) {
    System.out.print("[ ");
    for (int i = 0; i < input.length; i++) {
        System.out.print(input[i] + " ");
    }
    System.out.println("]");
}

public static int[] insertionSort(int[] nums, int begin, int end) {
    if (begin >= end) {
        return nums;
    }

    for (int i = 0; i < end; i++) {
        insert(nums, i, end - 1, nums[end]);
    }
    return nums;
}

static void insert(int[] nums, int begin, int end, int element) {
    int index = end;
    while (index >= begin && nums[index] < element) {
        index--;
    }
    for (int i = end; i > index; i--) {
        nums[i + 1] = nums[i];
    }
    nums[index + 1] = element;
}

}

递归插入排序

Recursive Insertion Sort

java

insertion-sort