java - 冒泡排序中的交换和比较

Question

我有一个java程序，用户可以选择1000、10000或100000个元素，我希望能够计算上面元素的3个选项中每一个的交换和比较，这是我的冒泡排序数组的代码

public static void bubbleSort(int[] arrayToSort)
{
  int comps=0;
  int swaps=0;


  for(int i = 0; i < arrayToSort.length-1; i++) 
  {
     for(int j = 0; j < arrayToSort.length-1; j++)
     {
        comps++;
        if(arrayToSort[j] > arrayToSort[j+1])
        {
           swaps++;
           int temp = arrayToSort[j];
           arrayToSort[j] = arrayToSort[j+1];
           arrayToSort[j+1] = temp;  
        }   
     }   

  }

     System.out.println("\nComparisions: " + comps + "swaps: " + swaps); 
}

当我运行此代码时，每个数组大小的输出为

比较:99980001 交换:0

比较:99980001 交换:0

编辑:我有一个测试器类，其中包含一个值从 1-100 的随机数组

这是我的测试人员类(class):

import java.util.*;
import java.util.Scanner;
import java.util.Random;

public class Tester extends algorithmTest
{
 public static void main(String [] args)
 {
  int option;
  int sortType=0;
  int numElements=0;
  int algorithm; 
  String algName="";  

  Scanner keyIn = new Scanner(System.in);

  System.out.print("****************MENU****************");
  System.out.print("\nPlease Select The Number Of Elements In The Array:");
  System.out.print("\n1. 1000");
  System.out.print("\n2. 10000");
  System.out.print("\n3. 100000");
  System.out.print("\n4. Quit\n");
  numElements = keyIn.nextInt();

  switch(numElements){
     case 1 : 
        numElements =1000;
        System.out.print("You have selected " + numElements + " elements");         
        break;
     case 2 :
        numElements=10000;
        System.out.print("You have selected " + numElements + " elements");      
        break;
     case 3 :
        numElements=100000;
        System.out.print("You have selected " + numElements + " elements");  
        break;
     default :
        System.out.println("Error");
  }      

  System.out.print("\n**********MENU**********");
  System.out.print("\nPlease Select A Sorting Algorithm");
  System.out.print("\n1. Bubble Sort");
  System.out.print("\n2. Enhanced Bubble Sort");
  System.out.print("\n3. Selection Sort");
  System.out.print("\n4. Insertion Sort");
  System.out.print("\n5. Quit\n");
  algorithm = keyIn.nextInt();


  int [] array = new int[numElements];
  Assignment.bubbleSort(array);



  if(algorithm ==1)
  {
     algName = "Bubble Sort: ";
     Assignment.bubbleSort(array);


  } 

  else if(algorithm ==2)
  {
     algName = "Enhanced Bubble Sort: ";
     Assignment.bubbleSortEnhanced(array);


  }  

  else if(algorithm ==3)
  {
     algName = "Selection Sort: ";
     Assignment.selectionSort(array);


  } 

  else if(algorithm ==4)
  {
     algName = "Insertion Sort: ";
     Assignment.insertionSort(array);


  } 



  System.out.print("\n*************MENU*************");
  System.out.print("\nPlease Select A Sorting Option");
  System.out.print("\n1. Random Sorted Array");
  System.out.print("\n2. Sorted Array");
  System.out.print("\n3. Inversely Sorted Array\n");
  sortType=keyIn.nextInt();

     System.out.print("\nRandom Array: ");
     for(int i=0; i<array.length; i++)
     {
     array[i] = (int)(Math.random() * 101);
     System.out.print(array[i] +" "); 
     } 

     System.out.print("\nSorted Array: ");
     Assignment.bubbleSort(array);
     for(int i=0; i<array.length; i++)
     { 
        System.out.print(array[i] +" "); 
     }

  if(sortType ==1)
  {
     Assignment.bubbleSort(array);
     System.out.print("\nRandomly Sorted Array: ");
     for(int i=0; i<array.length; i++)
     {
        array[i] = (int)(Math.random() * 101);
        System.out.print(array[i] +" "); 

     }

  } 

  else if(sortType ==2)
  {
     Assignment.bubbleSort(array);
     System.out.print("\n" +algName);
     for(int i=0; i<array.length; i++)
     {

        System.out.print(array[i] +" "); 
     }

  } 


  else if(sortType ==3)
  {
     long start = System.nanoTime();
     Assignment.inverseSort(array);
     System.out.print("\n" +algName);
     for(int i=0; i<array.length; i++)
     {

        System.out.print(array[i] +" "); 
     }
  long end = System.nanoTime();
     System.out.print("\nThe algorithm was completed in " + (end-start) + " nanoseconds");  

  }  

}}

Answer 1

抛开算法问题 - 关于原始代码的交换和比较:

我已通过 online java compiler 运行您的代码，包括用于生成随机数值的代码片段。交换和比较更有意义。我认为这与我生成随机值的方式有关。

代码示例:

import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.*;
import java.util.Arrays;

public class MyClass {
    public static void main(String[] args) {
        int[] arrayToSort = new int[800];
        IntStream.range(0,arrayToSort.length).forEach(i -> arrayToSort[i] = ThreadLocalRandom.current().nextInt(-10000, 10000 + 1) );
        bubbleSort(arrayToSort);
    }
    public static void bubbleSort(int[] arrayToSort)
    {
      int comps=0;
      int swaps=0;


      for(int i = 0; i < arrayToSort.length-1; i++) 
      {
         for(int j = 0; j < arrayToSort.length-1; j++)
         {
            comps++;
            if(arrayToSort[j] > arrayToSort[j+1])
            {
               swaps++;
               int temp = arrayToSort[j];
               arrayToSort[j] = arrayToSort[j+1];
               arrayToSort[j+1] = temp;  
            }   
         }   

      }

        System.out.println("\nComparisions: " + comps + " swaps: " + swaps);
        IntStream.range(0,arrayToSort.length).forEach(i -> {
            String outStr = arrayToSort[i] + " , ";
            if(i % 100 == 0)
                System.out.println(outStr);
            else
                System.out.print(outStr);
        });
    }
}

输出:

Comparisions: 638401 swaps: 155054
-9939 , 
-9889 , -9880 , -9870 , -9853 , -9824 , -9785 , -9710 , -9689 , -9686 , -9673 , -9631 , -9617 , -9589 , -9582 , -9512 , -9452 , -9444 , -9403 , -9394 , -9373 , -9322 , -9315 , -9274 , -9247 , -9200 , -9196 , -9118 , -9113 , -9105 , -9067 , -9066 , -9040 , -8999 , -8960 , -8921 , -8916 , -8873 , -8860 , -8854 , -8836 , -8767 , -8762 , -8720 , -8703 , -8665 , -8655 , -8645 , -8623 , -8614 , -8606 , -8602 , -8585 , -8584 , -8563 , -8527 , -8515 , -8504 , -8477 , -8455 , -8427 , -8409 , -8369 , -8369 , -8366 , -8345 , -8323 , -8306 , -8302 , -8295 , -8228 , -8196 , -8110 , -8081 , -8067 , -8031 , -8008 , -7973 , -7966 , -7861 , -7842 , -7826 , -7823 , -7821 , -7755 , -7735 , -7696 , -7667 , -7663 , -7645 , -7573 , -7548 , -7515 , -7506 , -7492 , -7474 , -7465 , -7454 , -7439 , -7380 , -7312 , 
-7256 , -7251 , -7151 , -7144 , -7135 , -7133 , -7110 , -7101 , -7101 , -7084 , -7050 , -7045 , -7044 , -7036 , -7030 , -6945 , -6944 , -6935 , -6931 , -6920 , -6881 , -6821 , -6757 , -6725 , -6618 , -6583 , -6581 , -6545 , -6527 , -6512 , -6279 , -6251 , -6221 , -6207 , -6193 , -6183 , -6173 , -6171 , -6141 , -6133 , -6119 , -6032 , -6028 , -6024 , -6014 , -5983 , -5982 , -5923 , -5866 , -5823 , -5812 , -5773 , -5680 , -5654 , -5627 , -5619 , -5608 , -5578 , -5569 , -5560 , -5514 , -5494 , -5487 , -5469 , -5456 , -5439 , -5434 , -5427 , -5385 , -5371 , -5371 , -5350 , -5323 , -5321 , -5316 , -5235 , -5199 , -5185 , -5183 , -5173 , -5166 , -5127 , -5111 , -5067 , -5065 , -5050 , -5029 , -5014 , -4990 , -4875 , -4846 , -4817 , -4780 , -4771 , -4732 , -4702 , -4694 , -4685 , -4673 , -4652 , 
-4641 , -4624 , -4600 , -4584 , -4565 , -4564 , -4563 , -4545 , -4519 , -4505 , -4473 , -4440 , -4416 , -4338 , -4296 , -4276 , -4224 , -4205 , -4202 , -4193 , -4153 , -4147 , -4130 , -4128 , -4081 , -4079 , -4073 , -4014 , -3948 , -3943 , -3885 , -3835 , -3751 , -3750 , -3721 , -3665 , -3651 , -3641 , -3638 , -3619 , -3618 , -3611 , -3602 , -3588 , -3583 , -3581 , -3513 , -3485 , -3462 , -3457 , -3434 , -3428 , -3359 , -3359 , -3328 , -3291 , -3238 , -3231 , -3209 , -3205 , -3164 , -3164 , -3057 , -3024 , -3014 , -2938 , -2935 , -2928 , -2917 , -2870 , -2804 , -2751 , -2723 , -2709 , -2657 , -2646 , -2614 , -2576 , -2567 , -2560 , -2518 , -2487 , -2417 , -2351 , -2341 , -2332 , -2332 , -2323 , -2280 , -2278 , -2265 , -2233 , -2210 , -2209 , -2174 , -2158 , -2139 , -2087 , -2015 , -1968 , 
-1917 , -1898 , -1857 , -1767 , -1747 , -1741 , -1730 , -1728 , -1621 , -1616 , -1615 , -1610 , -1601 , -1600 , -1586 , -1554 , -1492 , -1476 , -1470 , -1468 , -1432 , -1423 , -1419 , -1416 , -1415 , -1386 , -1372 , -1334 , -1327 , -1327 , -1295 , -1288 , -1259 , -1223 , -1185 , -1144 , -1132 , -1120 , -1101 , -1060 , -1039 , -1029 , -1018 , -950 , -932 , -895 , -848 , -838 , -807 , -799 , -766 , -728 , -707 , -697 , -630 , -623 , -601 , -594 , -558 , -536 , -529 , -511 , -496 , -451 , -440 , -436 , -433 , -420 , -409 , -407 , -396 , -300 , -287 , -280 , -222 , -217 , -195 , -194 , -193 , -190 , -185 , -185 , -164 , -163 , -116 , -105 , -53 , -21 , -10 , 13 , 13 , 29 , 44 , 80 , 114 , 120 , 124 , 126 , 161 , 199 , 
218 , 266 , 289 , 295 , 303 , 378 , 385 , 426 , 430 , 482 , 483 , 500 , 522 , 545 , 600 , 650 , 674 , 688 , 707 , 716 , 765 , 899 , 944 , 946 , 983 , 983 , 1011 , 1017 , 1028 , 1029 , 1031 , 1035 , 1043 , 1059 , 1075 , 1076 , 1112 , 1114 , 1119 , 1123 , 1157 , 1171 , 1177 , 1193 , 1210 , 1211 , 1222 , 1277 , 1284 , 1301 , 1328 , 1343 , 1345 , 1417 , 1420 , 1439 , 1446 , 1491 , 1501 , 1594 , 1656 , 1665 , 1787 , 1788 , 1826 , 1895 , 1896 , 1899 , 1921 , 1924 , 1925 , 1975 , 1988 , 1995 , 2022 , 2029 , 2047 , 2065 , 2074 , 2163 , 2170 , 2206 , 2215 , 2238 , 2274 , 2309 , 2327 , 2337 , 2350 , 2357 , 2364 , 2385 , 2387 , 2415 , 2420 , 2489 , 2500 , 2503 , 2509 , 2536 , 
2568 , 2598 , 2652 , 2654 , 2687 , 2707 , 2739 , 2743 , 2753 , 2868 , 2885 , 2898 , 2906 , 3015 , 3024 , 3024 , 3031 , 3059 , 3060 , 3112 , 3166 , 3167 , 3191 , 3201 , 3236 , 3247 , 3345 , 3351 , 3405 , 3411 , 3446 , 3451 , 3648 , 3655 , 3707 , 3714 , 3727 , 3754 , 3759 , 3770 , 3779 , 3793 , 3908 , 3918 , 3948 , 3963 , 3968 , 4016 , 4026 , 4050 , 4056 , 4056 , 4073 , 4087 , 4128 , 4159 , 4177 , 4178 , 4219 , 4267 , 4281 , 4295 , 4333 , 4351 , 4361 , 4378 , 4405 , 4415 , 4432 , 4466 , 4466 , 4468 , 4492 , 4498 , 4512 , 4532 , 4550 , 4561 , 4572 , 4591 , 4596 , 4601 , 4650 , 4652 , 4657 , 4665 , 4671 , 4730 , 4737 , 4758 , 4775 , 4824 , 4827 , 4845 , 4880 , 4891 , 4902 , 4941 , 4957 , 4971 , 
5005 , 5036 , 5083 , 5093 , 5102 , 5151 , 5192 , 5212 , 5216 , 5248 , 5267 , 5275 , 5298 , 5343 , 5392 , 5400 , 5416 , 5444 , 5450 , 5479 , 5504 , 5518 , 5523 , 5523 , 5540 , 5616 , 5693 , 5702 , 5704 , 5739 , 5745 , 5783 , 5785 , 5785 , 5856 , 5878 , 5970 , 6000 , 6018 , 6064 , 6091 , 6093 , 6106 , 6120 , 6182 , 6185 , 6210 , 6324 , 6341 , 6354 , 6412 , 6420 , 6465 , 6475 , 6485 , 6508 , 6519 , 6538 , 6555 , 6582 , 6584 , 6600 , 6608 , 6628 , 6629 , 6650 , 6677 , 6694 , 6743 , 6757 , 6764 , 6772 , 6778 , 6804 , 6837 , 6848 , 6855 , 6902 , 6903 , 6938 , 6962 , 7050 , 7072 , 7077 , 7092 , 7116 , 7128 , 7150 , 7183 , 7208 , 7219 , 7243 , 7251 , 7298 , 7306 , 7322 , 7324 , 7390 , 7398 , 7425 , 
7429 , 7449 , 7491 , 7534 , 7598 , 7615 , 7669 , 7669 , 7715 , 7734 , 7747 , 7773 , 7785 , 7787 , 7875 , 7891 , 7899 , 7904 , 7913 , 7915 , 7975 , 7990 , 8020 , 8044 , 8057 , 8082 , 8105 , 8120 , 8129 , 8162 , 8173 , 8196 , 8225 , 8249 , 8252 , 8265 , 8266 , 8306 , 8308 , 8359 , 8366 , 8398 , 8502 , 8502 , 8535 , 8584 , 8625 , 8655 , 8689 , 8746 , 8747 , 8788 , 8824 , 8856 , 8871 , 8892 , 8919 , 8926 , 8932 , 8937 , 9049 , 9074 , 9085 , 9087 , 9087 , 9106 , 9109 , 9147 , 9166 , 9173 , 9218 , 9234 , 9236 , 9345 , 9379 , 9380 , 9450 , 9453 , 9461 , 9473 , 9484 , 9524 , 9541 , 9583 , 9583 , 9625 , 9654 , 9677 , 9700 , 9709 , 9764 , 9776 , 9789 , 9795 , 9803 , 9831 , 9885 , 9923 , 9942 , 

根据 OP 的一些反馈，以下是 800 个项目的输出，其值在 0 到 100 之间:

Comparisions: 638401 swaps: 156393
0 , 
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 
9 , 10 , 10 , 10 , 10 , 11 , 11 , 11 , 11 , 12 , 12 , 12 , 12 , 12 , 12 , 13 , 13 , 13 , 13 , 13 , 13 , 13 , 13 , 14 , 14 , 14 , 14 , 15 , 15 , 15 , 15 , 15 , 15 , 15 , 15 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 16 , 17 , 17 , 17 , 17 , 17 , 18 , 18 , 18 , 18 , 18 , 18 , 18 , 18 , 19 , 19 , 19 , 19 , 19 , 19 , 19 , 19 , 20 , 20 , 20 , 20 , 20 , 21 , 21 , 21 , 21 , 21 , 21 , 21 , 22 , 22 , 22 , 22 , 22 , 22 , 23 , 23 , 23 , 23 , 23 , 23 , 23 , 23 , 24 , 24 , 24 , 24 , 24 , 24 , 
24 , 24 , 24 , 25 , 25 , 25 , 25 , 25 , 25 , 26 , 26 , 26 , 26 , 26 , 26 , 26 , 26 , 26 , 27 , 27 , 27 , 27 , 27 , 27 , 27 , 27 , 28 , 28 , 28 , 28 , 28 , 28 , 28 , 28 , 29 , 29 , 29 , 29 , 29 , 29 , 29 , 29 , 29 , 29 , 29 , 30 , 30 , 31 , 31 , 31 , 31 , 31 , 31 , 31 , 31 , 31 , 31 , 31 , 32 , 32 , 32 , 32 , 32 , 32 , 32 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 33 , 34 , 34 , 34 , 34 , 34 , 34 , 34 , 34 , 34 , 34 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 35 , 
35 , 35 , 35 , 35 , 36 , 36 , 36 , 37 , 37 , 37 , 37 , 37 , 38 , 38 , 38 , 38 , 38 , 38 , 38 , 38 , 38 , 39 , 39 , 39 , 39 , 39 , 40 , 40 , 40 , 40 , 40 , 40 , 40 , 41 , 41 , 41 , 41 , 41 , 42 , 42 , 42 , 42 , 42 , 42 , 42 , 43 , 43 , 43 , 43 , 43 , 44 , 44 , 44 , 44 , 44 , 44 , 44 , 44 , 44 , 44 , 44 , 45 , 45 , 45 , 45 , 45 , 46 , 46 , 46 , 46 , 46 , 46 , 46 , 46 , 46 , 46 , 46 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 47 , 48 , 48 , 48 , 48 , 48 , 48 , 48 , 
48 , 48 , 48 , 48 , 48 , 48 , 48 , 49 , 49 , 49 , 49 , 49 , 49 , 49 , 49 , 49 , 49 , 50 , 50 , 50 , 50 , 50 , 50 , 50 , 50 , 50 , 51 , 51 , 51 , 51 , 51 , 52 , 52 , 52 , 52 , 53 , 53 , 53 , 53 , 53 , 53 , 53 , 54 , 54 , 54 , 54 , 55 , 55 , 56 , 56 , 56 , 56 , 56 , 56 , 56 , 56 , 56 , 56 , 57 , 57 , 57 , 57 , 57 , 57 , 57 , 57 , 57 , 57 , 57 , 58 , 58 , 58 , 58 , 58 , 58 , 58 , 58 , 58 , 58 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 59 , 60 , 60 , 60 , 60 , 60 , 60 , 60 , 60 , 60 , 
60 , 61 , 61 , 61 , 61 , 61 , 61 , 61 , 62 , 62 , 62 , 62 , 62 , 62 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 63 , 64 , 64 , 64 , 64 , 64 , 64 , 65 , 65 , 65 , 65 , 65 , 65 , 65 , 65 , 65 , 65 , 65 , 66 , 66 , 66 , 66 , 66 , 66 , 66 , 66 , 66 , 66 , 66 , 67 , 67 , 67 , 67 , 67 , 67 , 67 , 67 , 67 , 68 , 68 , 68 , 68 , 69 , 69 , 69 , 69 , 69 , 69 , 69 , 69 , 69 , 69 , 70 , 70 , 70 , 70 , 71 , 71 , 71 , 71 , 71 , 71 , 71 , 71 , 72 , 72 , 72 , 72 , 72 , 72 , 72 , 73 , 73 , 73 , 
73 , 73 , 74 , 74 , 74 , 74 , 74 , 74 , 74 , 74 , 74 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 75 , 76 , 76 , 76 , 76 , 76 , 77 , 77 , 77 , 77 , 77 , 77 , 77 , 77 , 78 , 78 , 78 , 78 , 78 , 78 , 78 , 78 , 78 , 78 , 79 , 79 , 79 , 80 , 80 , 80 , 80 , 80 , 80 , 81 , 81 , 81 , 81 , 81 , 82 , 82 , 82 , 82 , 82 , 82 , 82 , 82 , 83 , 83 , 83 , 83 , 83 , 83 , 83 , 84 , 84 , 84 , 84 , 84 , 84 , 84 , 85 , 85 , 85 , 85 , 85 , 85 , 85 , 85 , 85 , 86 , 86 , 86 , 86 , 86 , 86 , 86 , 86 , 
86 , 87 , 87 , 87 , 87 , 87 , 87 , 87 , 87 , 88 , 88 , 88 , 88 , 88 , 88 , 88 , 88 , 88 , 89 , 89 , 90 , 90 , 90 , 90 , 90 , 90 , 90 , 90 , 90 , 90 , 91 , 91 , 91 , 91 , 91 , 91 , 91 , 91 , 92 , 92 , 92 , 92 , 92 , 92 , 92 , 92 , 93 , 93 , 93 , 93 , 93 , 93 , 93 , 94 , 94 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 95 , 96 , 96 , 96 , 96 , 97 , 97 , 97 , 97 , 97 , 97 , 98 , 98 , 98 , 98 , 98 , 98 , 98 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 99 , 100 , 100 , 100 ,