冒泡排序并行数组

Question

我需要读取数据文件并将其加载到 2 个数组（1 个并行）中。数据由 100 个整数 (ID#) 的列表组成，这些整数对应于如下所示的双精度 (Price)：

[ID] - [价格]

837 - 14.88

253 - 65.12

931 - 11.96

196 - 20.47

我需要用bubbleSort()的方法把ID（和对应的价格）降序排列。最后，我需要使用二进制和顺序搜索方法来定位我将显示的特定目标。

我的问题 - 当我运行这个程序时，我的顺序搜索成功了，但我的二分搜索失败了。我已经在下面粘贴了我的代码，希望有人能来救我。

public class StoreInventory
{
    public int[] storeItem = new int[200];
    public double[] itemPrice = new double[200];
    public int itemCount = 0;

    StoreInventory() {}

    public void loadItems() 
    {       
        try {
            String filename = "MasterStoreInv.dat";
            Scanner infile = new Scanner(new FileInputStream(filename));

            while (infile.hasNext()) {                  
                storeItem[itemCount] = infile.nextInt();
                itemPrice[itemCount] = infile.nextDouble();
                itemCount += 1;             
            }

            infile.close();

        } catch (IOException ex) {
            itemCount = -1;
            ex.printStackTrace();
        }
    }

    public double getItemPrice(int item)
    {
        return itemPrice[item];
    }

    public void bubbleSort() 
    {   
        for (int i = 0; i < itemCount; i++) {
            for (int x = 1; x < itemCount - i; x++) {
                if (storeItem[x - 1] > storeItem[x] && itemPrice[x - 1] > itemPrice[x]) {
                    int temp = storeItem[x - 1];
                    double tempi = itemPrice[x - 1];
                    storeItem[x - 1] = storeItem[x];
                    itemPrice[x - 1] = itemPrice[x];
                    storeItem[x] = temp;
                    itemPrice[x] = tempi;
                } 
            }
        }
    }

    public int binSearch (int target)
    {
     int low = 0;
     int high = itemCount - 1;

     while(high >= low) {
      int mid = (low + high) / 2;
        if(storeItem[mid] == target) {
        return mid;
        }
        if(storeItem[mid] < target) {
          low = mid + 1;
          }
        if(storeItem[mid] > target) {
          high = mid - 1;
          }
       }
         return -1;
    }

    public int seqSearch (int target)
    {
        int ind = 0;
        int found = -1;

        while (ind < itemCount) {
          if(target==storeItem[ind]) {
              found = ind;
              ind = itemCount;
            }else {
              ++ind;
            }
        }
        return found;
    }   

    public static void main(String[] args) 
    {
        StoreInventory inventory = new StoreInventory();
        Scanner myScanner = new Scanner(System.in);
        int target, item;
        double itemPrice;


        inventory.loadItems();      
        inventory.bubbleSort();

        do {
            System.out.println("Which item number do you want to see -->");     
            target = myScanner.nextInt();
        /* Sequential Search */
        item = inventory.seqSearch(target);     
            if (item >= 0) {
                itemPrice = inventory.getItemPrice(item);
                System.out.print("\nSequential search - Successful!\nID number: " + target + "  Price: $" + itemPrice+ "\n");   
            }else {
                System.out.print("\nSequential search - Failed\nID number not found\n\n");
            }
        /* Binary Search */
        item = inventory.binSearch(target);     
            if (item >= 0) {
                itemPrice = inventory.getItemPrice(item);
                System.out.print("\nBinary search - Successful!\nID number: " + target + "  Price: $" + itemPrice+ "\n\n"); 
            }else {         
                System.out.print("\nBinary search - Failed\nID number not found\n\n");
            }

        System.out.print("Enter '1' to make another search\nEnter '0' to quit -->");

        }while (myScanner.nextInt() >= 1);
        myScanner.close();  


    }//END main

}

Answer 1

您的问题在这里：

if (storeItem[x - 1] > storeItem[x] && itemPrice[x - 1] > itemPrice[x])

只有当商品和价格都更高时，您才移动商品 - 这不是正确的排序。想象一下这样的数据：

5,10
1,20

这些不会被交换 - 而且这些也不会：

1,20
5,10

您需要选择一个合适的顺序，例如：

storeItem[x - 1] > storeItem[x] || (storeItem[x - 1] == storeItem[x] && itemPrice[x - 1] > itemPrice[x])

这将确保所有条目都有严格的顺序。

顺便说一句 - 您可能希望考虑构建一个 class 来存储对并使其实现 Comparable.

冒泡排序并行数组

Bubble Sort Parallel Array

java

arrays

sorting

bubble-sort

parallel-arrays