选择排序没有按降序排序

Question

这是我的作业：我想知道在选择排序中发生了多少次比较和交换。当我像这样以反向或降序声明我的数组时：

int arr[] = { 5, 4, 3, 2, 1 };

…运行很好，计数也比较和交换但是当我尝试给出 'n' 并以相反的顺序填充数组时，它按降序填充它但它没有正常工作按降序排序以计算我的交换，尽管它计算比较。

代码如下：

public class SelectionSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        Scanner in = new Scanner(System.in);
        int compares = 0, exchanges = 0, x;
        x = in.nextInt();
        int[] arr = new int [x];
        int n = arr.length;
        int s = 0;
        int min;
        int temp, i, j;
        System.out.print("Filling Array");
        for(i = n - 1; i > 0; i--)
        {
            arr[i] = i;
            System.out.print(" " + arr[i]);
        }
        System.out.println("");
        for(i = 0; i < n ; i++)
        {
            min = i ;

            for(j = i + 1; j < n; j++)
            {
                compares++;
                if(arr[min] > arr[j])
                    min = j;
            }

            if(min != i)
            {
                exchanges++;
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }

            System.out.println("Iteration " + (++s));
            for(int a = 0; a < arr.length; a++)
                System.out.print(" " + arr[a]);

            System.out.println("");
        }
        System.out.println("");
        System.out.println("Compares -- >> " + compares);
        System.out.println("Exchanges -->> " + exchanges);
    }
}

Answer 1

显示错误的 EXCHANGES 次数的原因很简单。如果您遵循此处的代码：

System.out.print("Filling Array");
for(i = n - 1; i > 0; i--)
{
    arr[i] = i;
    System.out.print(" " + arr[i]);
}

明白了吗？该数组从不按降序填充或排序，您只是按相反的顺序打印它。

让我们假设 n = 3 并且当数组初始化时它是 { 0, 0, ... } 并遵循循环：

迭代 1：

// i = n - 1 = 2
// i > 0 = true
// arr[i] = i;
// arr[2] = 2;
// print statement

迭代 2：

// i - 1 = 1
// i > 0 = true
// arr[i] = i;
// arr[1] = 1;
// print statement

迭代 3：

// i - 1 = 0
// i > 0 = false
// arr = { 0, 1, 2 }

试试这个来填充反向排序的数组：

for (i = n - 1, z = 0; i > 0; i--, z++)
{
    arr[z] = i;
}

选择排序没有按降序排序

Selection sort didn't sort in descending order

java

arrays

sorting

selection-sort