-1

知道如何为本地插入排序生成和打印最坏的情况吗？这是我的本地插入排序的实现：

public class InsertionSort{
    public static void main(String a[]){
        int i;
        int array[] = {12,9,4,99,120,1,3,10}; 
        System.out.println("Values Before the sort:\n");  

        for(i = 0; i < array.length; i++)
            System.out.print( array[i]+"  ");
        System.out.println();

        insertion_srt(array, array.length);  
        System.out.print("Values after the sort:\n");  

        for(i = 0; i <array.length; i++)
            System.out.print(array[i]+"  ");

        System.out.println(); 
        System.out.println("PAUSE"); 
    }

    public static void insertion_srt(int array[], int n){
        for (int i = 1; i < n; i++){
            int j = i;
            int B = array[i];
            while ((j > 0) && (array[j-1] > B)){
                array[j] = array[j-1];
                j--;
            }
            array[j] = B;
        }
    }
}

我怎样才能修改它以产生最坏的情况？

4

1 回答 1

1

以降序排序的数组将是最坏的情况（或者，对于通用实现，排序将其放入的顺序相反）。

要了解这一点，请考虑插入排序的工作原理：

在任何时候，输入都会被分成两部分——左边排序，右边未排序：

sorted | unsorted

最初排序的部分开始是空的，然后我们重复地将未排序部分的最左边的元素插入其中，将值向右移动以腾出空间。

现在，每个插入的最坏情况将是我们必须将它一直插入到左侧 - 我们必须将所有其他值向上移动以将其放置在需要的位置。这什么时候会发生？当要插入的元素小于左边的所有元素时。

因此，最坏的情况是每个元素都小于其左侧的所有元素，而这只是降序排列的数组。

于 2013-10-20T22:21:42.313 回答