0

我编写了这个程序来比较使用选择和冒泡排序对随机数进行排序所需的操作数。但是，这些数字一直保持不变，我无法弄清楚我的代码哪里出错了。

static int num_comps;   

public static void main(String[] args) 
{
    Random rnd = new Random();

    // max size of array
    // number of N inputs
    int array_size = 32768;
    int num_datasets = 12;

    // allocate array once to the max size
    int[] vals = new int[array_size];

    // temp array with allocated array to max size
    int[] tvals = new int[array_size];

    // array to hold operation counts
    int[] op_counts = new int[num_datasets];
    int[] op_counts2 = new int[num_datasets];

    // array to hold the size of each array
    //
    int[] arraySizes = new int[num_datasets];

    int i;
    int j;
    int sz;

    for (i = 0, sz = 16; i < num_datasets; i++, sz *= 2)
        arraySizes[i] = sz;

    for (int iter = 0; iter < num_datasets; iter++)
    {
        int curr_size = arraySizes[iter];

        // load array with random values
        //
        for (i = 0; i < curr_size; i++)
            vals[i] = rnd.nextInt(4999);

        for (i = 0; i < curr_size; i++)
            tvals[i] = vals[i];

        // run the bubble sort algorithm
        //
        num_comps = 0;
        bubbleSort(tvals, curr_size);
        op_counts[iter] = num_comps;
        //System.out.println("Num comps at " + iter + " is " + num_comps);

        // run the selection-sort algorithm
        num_comps = 0;
        selectionSort(tvals, curr_size);
        op_counts2[iter] = num_comps;
        //System.out.println("Num comps at " + iter + " is " + num_comps);
    }

    System.out.println("Operation Counts (N vs. op Count): ");
    for (int k = 0; k < num_datasets; k++)
        System.out.println(arraySizes[k] + "\t\t" + op_counts[k] + "\t\t" + op_counts2[k]);
}

static void bubbleSort(int vals[], int curr_size)
{
    int temp;
    for (int i = 0; i < curr_size - 1; i++)
    {
        for (int j = 0; j < curr_size - i - 1; j++)
        {
            // swap
            num_comps = num_comps + 1;
            if (vals[j+1] < vals[j])
            {
                temp = vals[j];
                vals[j] = vals[j+1];
                vals[j+1] = temp;
            }
        }
    }
}

static void selectionSort(int vals[], int curr_size)
{
    int temp;
    for(int i=0; i<curr_size - 1; i++)
     {
        for(int j=i+1; j<curr_size; j++)
        {
            num_comps = num_comps + 1;
            if(vals[i] > vals[j] )
            {
                temp = vals[j];
                vals[j] = vals[i];
                vals[i] = temp;
            }
        }
     }
}
4

1 回答 1

2

您的选择排序算法不会搜索列表中的最小值。然后用外循环的索引交换它。

你应该这样做：

static void selectionSort(int vals[], int curr_size)
{
    int temp;
    for(int i=0; i<curr_size - 1; i++)
    {
        int lowest = i;
        for(int j=i+1; j<curr_size; j++)
        {
            num_comps = num_comps + 1;
            if(vals[lowest] > vals[j] )
            {
                lowest = j;
            }
        }

        // swap lowest with current index
        temp = vals[lowest];
        vals[lowest] = vals[i];
        vals[i] = temp;
     }
}

（当然这可以进一步优化）这个算法的优势不是比较的数量，而是交换的数量（我想这是最少的）。

你的冒泡排序算法对我来说似乎没问题。

Both have the same two loops, so comparing the counts of the current implementations indeed result in the same values. But, I think you can optimize the bubble sort, to stop earlier (when no swaps were found). Again, the strength of sorting algorithms depends on the used ones, and are not necessarily the least amount of comparisons. So Using the correct algorithm for your specific task, and thereby circumventing the task-specific high cost operations, is important!

于 2013-02-18T22:14:02.053 回答