0

因此，此代码确实计算了比较，但不计算交换（每个循环中的 countswap）。

有谁知道为什么，它太“嵌入式”还是什么？感谢一百万的帮助。

 */
package sorts;

import java.util.*;

public class Sorts {

    Random rand = new Random();

    private int countcomp;
    private int countswap;

    public Sorts() {
        countcomp = 0;
        countswap = 0;
    }

    public int getcomparisions() {
        return countcomp;
    }

    public int getswaps() {
        return countswap;
    }

    public static void main(String args[]) {

        Sorts sorts = new Sorts();

        //int[] unsorted = {2, 4, 1, 9, 5, 10, 3, 6, 8, 7};
        //int[] unsorted = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        //int[] unsorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] unsorted = new int[100];
        for(int i = 0; i < 100; i++){
            unsorted[i] = i;
    }
        //GENERATOR OF INT ARRAYS

        System.out.println("\n\tSelection sort");
        Sorts sortsselect = new Sorts();
        sortsselect.selection(unsorted);
        System.out.println("\nSwap Count : " + sortsselect.getswaps() + "\nComparision Count : " + sortsselect.getcomparisions());

        System.out.println("\n\tBubble sort");
        Sorts sortsbubble = new Sorts();
        sortsbubble.bubble(unsorted);
        System.out.println("\nSwap Count : " + sortsbubble.getswaps() + "\nComparision Count : " + sortsbubble.getcomparisions());

        System.out.println("\n\n\tInsertion sort");
        Sorts sortsinsertion = new Sorts();
        sortsinsertion.insertion(unsorted);
        System.out.println("\nSwap Count : " + sortsinsertion.getswaps() + "\nComparision Count : " + sortsinsertion.getcomparisions());

        System.out.println("\n\n\tExchange sort");
        Sorts sortsexchange = new Sorts();
        sortsexchange.exchange(unsorted);
        System.out.println("\nSwap Count : " + sortsexchange.getswaps() + "\nComparision Count : " + sortsexchange.getcomparisions());

    }

    //selection takes in a unsorted array and returns a sorted one
    public void selection(int[] selunsorted) {

        int i, j, max;
        countcomp = 0;
        countswap = 0;
        max = selunsorted.length;

        //iterate through the array and move the smallest number into an incrementing position
        for (i = 0; i < max - 1; i++) {
            int smallpos = i;
            int smallest = selunsorted[i];

            for (j = i + 1; j < max; j++) {
                countcomp++;
                if (selunsorted[j] < smallest) {
                    countswap++;
                    smallest = selunsorted[j];
                    smallpos = j;
                }
            }
            int temp = selunsorted[i];
            selunsorted[i] = selunsorted[smallpos];
            selunsorted[smallpos] = temp;
        }
        for (i = 0; i < max; i++) {
            j = selunsorted[i];
            System.out.print(j + ",");
        }
    }

    public void bubble(int[] bubunsorted) {

        int max = bubunsorted.length;
        int i, imax, j;
        countcomp = 0;
        countswap = 0;

        for (imax = max; imax > 0; imax--) {
            for (j = 0; j + 1 < imax; j++) {
                countcomp++;
                if (bubunsorted[j] > bubunsorted[j + 1]) {
                    int temp = bubunsorted[j + 1];
                    bubunsorted[j + 1] = bubunsorted[j];
                    bubunsorted[j] = temp;
                    countswap++;
                }
            }
        }
        for (i = 0; i < max; i++) {
            j = bubunsorted[i];
            System.out.print(j + ",");
        }
    }

    public void insertion(int[] insertunsorted) {

        int i, j, a;
        int max = insertunsorted.length;
        countcomp = 0;
        countswap = 0;

        for (i = 0; i < max; i++) {
            for (j = 0; j < i; j++) {
                countcomp++;
            }
            if (insertunsorted[j] > insertunsorted[i]) {
                int temp = insertunsorted[j + 1];
                insertunsorted[j + 1] = insertunsorted[i];
                countswap++;
                for (a = (j + 2); a < (i + 1); a++) {
                    int temp1 = insertunsorted[a];
                    insertunsorted[a] = temp;
                    temp = temp1;
                    countswap++;
                }
            }
        }

        for (i = 0; i < max; i++) {
            j = insertunsorted[i];
            System.out.print(j + ",");
        }
    }

    public void exchange(int[] exchangeunsorted) {

        int max = exchangeunsorted.length;
        int i, j;
        countcomp = 0;
        countswap = 0;

        for (i = 0; i < max; i++) {
            for (j = i; j < max; j++) {
                countcomp++;
                if (exchangeunsorted[j] < exchangeunsorted[i]) {
                    countswap++;
                    int temp = exchangeunsorted[j];
                    exchangeunsorted[i] = exchangeunsorted[j];
                    exchangeunsorted[j] = temp;
                }
            }
        }
        for (i = 0; i < max; i++) {
            j = exchangeunsorted[i];
            System.out.print(j + ",");
        }
    }
}
4

2 回答 2

0

在您的 main()方法开始时查看您的数组初始化：-

int[] unsorted = new int[100];
for(int i = 0; i < 100; i++){
        unsorted[i] = i;
}

您的数组已经排序..所以，不会发生交换..所以，swapCount 为 0..但仍然会进行比较..因此它们被计算在内..

尝试使用较小的数组..并向其中添加随机值..未排序的..它将起作用..

于 2012-10-05T18:25:10.117 回答
0

是的，你正在创建一个排序数组，所以没有交换发生。你应该这样做：

Random r = new Random();
for(int i = 0; i < 100; i++)  {
unsorted[i] = r.nextInt(500);
}

您还需要为每个不同的排序算法创建一个新的未排序数组（或仅使用 Arrays.copyOf(array) 复制数组），因为数组将按第一个排序算法排序。如果你这样做，交换会正确显示。

此外，我复制并测试了您的代码，并且在交换排序或插入排序中某处有问题，因为交换排序的输出很多为 1。

于 2012-10-05T18:59:29.883 回答