java - 不同的排序算法在大型阵列上失败-6ren

java - 不同的排序算法在大型阵列上失败

转载作者：行者123 更新时间：2023-11-30 08:07:56

我正在尝试使用不同的算法对数组进行排序。当我使用少量数组运行应用程序时，它可以工作并产生结果。当数组大于：131072时，它将停止响应。

可能是什么原因？这段代码有什么问题吗？

这是我的功能：

boolean runTest(String[] text, int[] number, String url, String out, Sort sort) {
  PrintWriter filename;
  boolean tobeReturned = true;
  String beforeSorting = "";
  String afterSorting = "";

  long startTime;
  double timeTaken;
  try {
    filename = createWriter(out);

    for(File directory : new File(url).listFiles()){
      File[] listOfFiles = directory.listFiles();     
      filename.println("Number of Records: \t" + directory.getName());

      for (File file : listOfFiles) {
        text = loadStrings(file);
        number = int(text);
        if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };

        startTime = startTime();       
        sort.sortInteger(number);        
        timeTaken = stopTime(startTime);

        if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };

        filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
        timeTaken = 0;
      }
      filename.println("\n");
    }
    filename.flush();
    filename.close();
  } 
  catch (Exception e) {
    tobeReturned = false;
  }
  return tobeReturned;
}

接口：

interface Sort{
   public int[] sortInteger(int[] input);
}

排序类之一（插入）

class Insertion implements Sort{

  Insertion() {
  }

  int[] sortInteger(int[] input) {
    int i, j, tobeSorted;
    for (i = 1; i < input.length; i++) {
      tobeSorted = input[i];
      j = i;
      while (j > 0 && input[j - 1] > tobeSorted) {
        input[j] = input[j - 1];
        j--;
      }
      input[j] = tobeSorted;
    }
    //println(input);
    return input;
  }
}

数字文件夹：

档案：

记录：

插入结果排序：

合并排序的结果：

******更新******

完整的简化处理代码

import java.util.*; 

long a = 9; // total loop, 9 means = 65536, 10 means = 131072 ...
long b = 2;  // multiplier, 2 means = 512,1024,2048...
long c = 512; // starting number
long d = 5; // times random text file

String url; 

Insertion insertion;
Merge merge;
Bubble bubble;
Shell shell;
QuickSort quickSort;

void setup() {
  url = sketchPath("_numbers/");  

  insertion = new Insertion();
  merge = new Merge();
  bubble = new Bubble();
  shell = new Shell();
  quickSort = new QuickSort();

  generateFiles(a,b,c,d);

  boolean runSortTest = false;
    runSortTest = runTest(url, "_results/a_insertion.txt", insertion);
    runSortTest = runTest(url, "_results/b_merge.txt", merge);
    runSortTest = runTest(url, "_results/c_bubble.txt", bubble);
    runSortTest = runTest(url, "_results/d_shell.txt", shell);
    runSortTest = runTest(url, "_results/e_quickSort.txt", quickSort);

    if(runSortTest){
      println("Done");
    }else{
      println("Error");
    }

}

boolean generateFiles(long totalLoop, long multiplier, long power, long fileNumber){
  PrintWriter pw;
  //int orderCount = 1;
  int count = 1;
  //boolean tobeReturned = true;
  try {
    for (int i = 1; i < totalLoop; i = i+1) {   
      for (int j = 1; j < fileNumber+1; j = j+1) {
        pw = createWriter("/_numbers/" + power + "/" + count + ".txt"); 

        for (int k = 0; k < power; k = k+1) { 
          pw.println(randomNumber(0, power));
          //pw.write(int(randomNumber(0, power)) + "\t");
        }
        count++;

        pw.flush(); // Writes the remaining data to the file
        pw.close(); // Finishes the file
      }
      count = 1;
      //orderCount++;
      power *= multiplier; 
    }
    //orderCount = 1;
    return  true;
  } catch (Exception e) {
    return false;
  }
}

long randomNumber(long min, long max){
  long randomN = (long)random(min,(max + 1));
  return randomN;
}

//####################################################################################################
//## Runs the test and produces a log file for each algorithms
//####################################################################################################

boolean runTest(String url, String out, Sort sort) {
  PrintWriter filename;
  boolean tobeReturned = true;
  String beforeSorting = "";
  String afterSorting = "";

  long startTime;
  double timeTaken;
  try {
    filename = createWriter(out);

    for(File directory : new File(url).listFiles()){
      File[] listOfFiles = directory.listFiles();     
      filename.println("Number of Records: \t" + directory.getName());

      for (File file : listOfFiles) {
        String[] text; int[] number;
        text = loadStrings(file);
        number = int(text);
        if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };

        startTime = startTime();       
        sort.sortInteger(number);        
        timeTaken = stopTime(startTime);

        if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };

        filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
        timeTaken = 0;
        Arrays.fill(text, null);
        number = null;
      }
      filename.println("\n");
    }
    filename.flush();
    filename.close();

  } 
  catch (Exception e) {
    e.printStackTrace();
    tobeReturned = false;
  }
  return tobeReturned;
}



boolean isSorted(int[] array) {
  for (int i = 0; i < array.length-1; i ++) {
    if (array[i] > array[i+1]) {
      return false;
    }
  }
  return true;
}

//####################################################################################################
//## Time comparison
//####################################################################################################

long startTime() {
  return System.nanoTime();
}

double stopTime(long startTime) {
  double finalTime = (System.nanoTime() - startTime)/1000000000.0;
  return finalTime;
}

/*

Interface
 # Last update: 20 October 2015 
*/

interface Sort{
   public int[] sortInteger(int[] input);
}

/*

Insertion class, implements Sort interface
 # Last update: 25 October 2015
*/


class Insertion implements Sort{

  Insertion() {
  }

  int[] sortInteger(int[] input) {
    int i, j, tobeSorted;
    for (i = 1; i < input.length; i++) {
      tobeSorted = input[i];
      j = i;
      while (j > 0 && input[j - 1] > tobeSorted) {
        input[j] = input[j - 1];
        j--;
      }
      input[j] = tobeSorted;
    }
    //println(input);
    return input;
  }
}

/*

Merge class, implements Sort interface
 # Last update: 25 October 2015 
*/


class Merge implements Sort{

  Merge() {
  }

  int[] sortInteger(int[] input) {
    if (input.length > 1) {
      // split array into two halves
      int[] left = leftHalf(input);
      int[] right = rightHalf(input);

      // recursively sort the two halves
      sortInteger(left);
      sortInteger(right);

      // merge the sorted halves into a sorted whole
      merge(input, left, right);
    }
    return input;
  }

  // Returns the first half of the given array.
  int[] leftHalf(int[] array) {
    int size1 = array.length / 2;
    int[] left = new int[size1];
    for (int i = 0; i < size1; i++) {
      left[i] = array[i];
    }
    return left;
  }

  // Returns the second half of the given array.
  int[] rightHalf(int[] array) {
    int size1 = array.length / 2;
    int size2 = array.length - size1;
    int[] right = new int[size2];
    for (int i = 0; i < size2; i++) {
      right[i] = array[i + size1];
    }
    return right;
  }

  void merge(int[] result, int[] left, int[] right) {
    int i1 = 0;   // index into left array
    int i2 = 0;   // index into right array

    for (int i = 0; i < result.length; i++) {
      if (i2 >= right.length || (i1 < left.length &&
        left[i1] <= right[i2])) {
        result[i] = left[i1];    // take from left
        i1++;
      } else {
        result[i] = right[i2];   // take from right
        i2++;
      }
    }
  }

}

/*

 Bubble class, implements Sort interface
 # Last update: 25 October 2015
 */


class Bubble implements Sort {

  Bubble() {
  }

  int[] sortInteger(int[] input) {
    boolean swapped = true;
    int j = 0;
    int tmp;
    while (swapped) {
      swapped = false;
      j++;
      for (int i = 0; i < input.length - j; i++) {                                       
        if (input[i] > input[i + 1]) {                          
          tmp = input[i];
          input[i] = input[i + 1];
          input[i + 1] = tmp;
          swapped = true;
        }
      }
    }
    return input;
  }
}

/*

 Shell class, implements Sort interface
 # Last update: 25 October 2015 
 */


class Shell implements Sort {

  Shell() {
  }

  int[] sequence = {59724292, 26544130, 11797391, 5243258, 2330349, 1035711, 460316, 204585, 90927, 40412, 17961, 7983, 3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1};
  /*
  int number = 701;
   for(int i=0; i<15; i++){    
   int newN = int(number*2.25);
   println(number);
   number =  newN;    
   }
   */

  int[] sortInteger (int[] input) {
    int size = input.length;
    int i, j, temp;
    for ( int s : sequence ) {
      i = s;
      while ( i < size ) {
        temp = input[i];
        j = i-s;
        while ( j >= 0 && input[j] > temp ) {
          input[j + s] = input[j];
          j -= s;
        }
        input[j + s] = temp;
        i ++;
      }
    }
    return input;
  }

}

/*

 QuickSort class, implements Sort interface
 # Last update: 26 October 2015 
 */


class QuickSort implements Sort {

  QuickSort() {
  }

  int[] sortInteger(int[] input) {
    quickSort(input, 0, input.length-1) ;
    return  input;
  }

  public void quickSort(int arr[], int low, int high) 
  {
    int i = low, j = high;
    int temp;
    int pivot = arr[(low + high) / 2];

    /** partition **/
    while (i <= j) 
    {
      while (arr[i] < pivot)
        i++;
      while (arr[j] > pivot)
        j--;
      if (i <= j) 
      {
        /** swap **/
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        i++;
        j--;
      }
    }

    /** recursively sort lower half **/
    if (low < j)
      quickSort(arr, low, j);
    /** recursively sort upper half **/
    if (i < high)
      quickSort(arr, i, high);
  }
}

最佳答案

解决这个问题的第一步是找出问题所在。这就是我们要求MCVE时的意思。您必须弄清楚问题出在哪里。一种简单的方法是添加println()语句：

  boolean runSortTest = false;
  println("1");
  runSortTest = runTest(url, "_results/a_insertion.txt", insertion);
  println("2");
  runSortTest = runTest(url, "_results/b_merge.txt", merge);
  println("3");
  runSortTest = runTest(url, "_results/c_bubble.txt", bubble);
  println("4");
  runSortTest = runTest(url, "_results/d_shell.txt", shell);
  println("5");
  runSortTest = runTest(url, "_results/e_quickSort.txt", quickSort);
  println("6");

这样做，我们将看到打印出1、2和3，但不会打印出4、5和6。这意味着您会陷入气泡的某个地方。我们可以通过注释掉气泡排序并查看会发生什么来确认这一点：

  boolean runSortTest = false;
  println("1");
  runSortTest = runTest(url, "_results/a_insertion.txt", insertion);
  println("2");
  runSortTest = runTest(url, "_results/b_merge.txt", merge);
  println("3");
  //runSortTest = runTest(url, "_results/c_bubble.txt", bubble);
  println("4");
  runSortTest = runTest(url, "_results/d_shell.txt", shell);
  println("5");
  runSortTest = runTest(url, "_results/e_quickSort.txt", quickSort);
  println("6");

现在，程序执行正常。因此，现在我们已经知道问题在于气泡排序，因此我们可以摆脱其他所有问题：

import java.util.*; 

long a = 9; // total loop, 9 means = 65536, 10 means = 131072 ...
long b = 2;  // multiplier, 2 means = 512,1024,2048...
long c = 512; // starting number
long d = 5; // times random text file

String url; 

Bubble bubble;

void setup() {
  url = sketchPath("_numbers/");  

  bubble = new Bubble();
  generateFiles(a, b, c, d);

  boolean runSortTest = false;
  runSortTest = runTest(url, "_results/c_bubble.txt", bubble);

  if (runSortTest) {
    println("Done");
  } else {
    println("Error");
  }
}

boolean generateFiles(long totalLoop, long multiplier, long power, long fileNumber) {
  PrintWriter pw;
  //int orderCount = 1;
  int count = 1;
  //boolean tobeReturned = true;
  try {
    for (int i = 1; i < totalLoop; i = i+1) {   
      for (int j = 1; j < fileNumber+1; j = j+1) {
        pw = createWriter("/_numbers/" + power + "/" + count + ".txt"); 

        for (int k = 0; k < power; k = k+1) { 
          pw.println(randomNumber(0, power));
          //pw.write(int(randomNumber(0, power)) + "\t");
        }
        count++;

        pw.flush(); // Writes the remaining data to the file
        pw.close(); // Finishes the file
      }
      count = 1;
      //orderCount++;
      power *= multiplier;
    }
    //orderCount = 1;
    return  true;
  } 
  catch (Exception e) {
    return false;
  }
}

long randomNumber(long min, long max) {
  long randomN = (long)random(min, (max + 1));
  return randomN;
}

//####################################################################################################
//## Runs the test and produces a log file for each algorithms
//####################################################################################################

boolean runTest(String url, String out, Sort sort) {
  PrintWriter filename;
  boolean tobeReturned = true;
  String beforeSorting = "";
  String afterSorting = "";

  long startTime;
  double timeTaken;
  try {
    filename = createWriter(out);

    for (File directory : new File(url).listFiles()) {
      File[] listOfFiles = directory.listFiles();     
      filename.println("Number of Records: \t" + directory.getName());

      for (File file : listOfFiles) {
        String[] text; 
        int[] number;
        text = loadStrings(file);
        number = int(text);
        if (isSorted(number)) { 
          beforeSorting = "Sorted";
        } else { 
          beforeSorting = "NOT Sorted";
        };

        startTime = startTime();       
        sort.sortInteger(number);        
        timeTaken = stopTime(startTime);

        if (isSorted(number)) { 
          afterSorting = "Sorted";
        } else { 
          afterSorting = "NOT Sorted";
        };

        filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
        timeTaken = 0;
        Arrays.fill(text, null);
        number = null;
      }
      filename.println("\n");
    }
    filename.flush();
    filename.close();
  } 
  catch (Exception e) {
    e.printStackTrace();
    tobeReturned = false;
  }
  return tobeReturned;
}



boolean isSorted(int[] array) {
  for (int i = 0; i < array.length-1; i ++) {
    if (array[i] > array[i+1]) {
      return false;
    }
  }
  return true;
}

//####################################################################################################
//## Time comparison
//####################################################################################################

long startTime() {
  return System.nanoTime();
}

double stopTime(long startTime) {
  double finalTime = (System.nanoTime() - startTime)/1000000000.0;
  return finalTime;
}

/*

 Interface
 # Last update: 20 October 2015 
 */

interface Sort {
  public int[] sortInteger(int[] input);
}


/*
 Bubble class, implements Sort interface
 # Last update: 25 October 2015
 */
class Bubble implements Sort {

  Bubble() {
  }

  int[] sortInteger(int[] input) {
    boolean swapped = true;
    int j = 0;
    int tmp;
    while (swapped) {
      swapped = false;
      j++;
      for (int i = 0; i < input.length - j; i++) {                                       
        if (input[i] > input[i + 1]) {                          
          tmp = input[i];
          input[i] = input[i + 1];
          input[i + 1] = tmp;
          swapped = true;
        }
      }
    }
    return input;
  }
}

这可能会进一步缩短，但是想法是这样的：删除与该问题没有直接关系的所有内容。

现在，我们已经消除了一些额外的信息，我们可以仔细看看您的气泡排序。同样， println()语句是您最好的朋友：

  int[] sortInteger(int[] input) {

    println("input length: " + input.length);

使用它，您可以看到它确实仍在运行，因为已打印出以下内容：

input length: 1024
input length: 1024
input length: 1024
input length: 1024
input length: 1024
input length: 16384
input length: 16384
input length: 16384
input length: 16384
input length: 16384
input length: 2048
input length: 2048
input length: 2048
input length: 2048
input length: 2048
input length: 32768
input length: 32768
input length: 32768
input length: 32768
input length: 32768
input length: 4096
input length: 4096
input length: 4096
input length: 4096
input length: 4096
input length: 512
input length: 512
input length: 512
input length: 512
input length: 512
input length: 65536
input length: 65536
input length: 65536
input length: 65536
input length: 65536
input length: 8192
input length: 8192
input length: 8192
input length: 8192
input length: 8192
Done

实际上：这很好，您只需花几分钟。这是我在 c_bubble.txt中得到的输出：

记录数：1024

File Set 1.txt:         NOT Sorted:     Sorted:     0.009598049335181713
File Set 2.txt:         NOT Sorted:     Sorted:     0.0011289309477433562
File Set 3.txt:         NOT Sorted:     Sorted:     0.0026859149802476168
File Set 4.txt:         NOT Sorted:     Sorted:     0.002715847920626402
File Set 5.txt:         NOT Sorted:     Sorted:     0.0015163590433076024


Number of Records:  16384
File Set 1.txt:         NOT Sorted:     Sorted:     0.38029658794403076
File Set 2.txt:         NOT Sorted:     Sorted:     0.37928950786590576
File Set 3.txt:         NOT Sorted:     Sorted:     0.3931492865085602
File Set 4.txt:         NOT Sorted:     Sorted:     0.3918215036392212
File Set 5.txt:         NOT Sorted:     Sorted:     0.38513386249542236


Number of Records:  2048
File Set 1.txt:         NOT Sorted:     Sorted:     0.0040453351102769375
File Set 2.txt:         NOT Sorted:     Sorted:     0.0041389851830899715
File Set 3.txt:         NOT Sorted:     Sorted:     0.004071420058608055
File Set 4.txt:         NOT Sorted:     Sorted:     0.004472961183637381
File Set 5.txt:         NOT Sorted:     Sorted:     0.0041146110743284225


Number of Records:  32768
File Set 1.txt:         NOT Sorted:     Sorted:     1.6499463319778442
File Set 2.txt:         NOT Sorted:     Sorted:     1.6393990516662598
File Set 3.txt:         NOT Sorted:     Sorted:     1.628066897392273
File Set 4.txt:         NOT Sorted:     Sorted:     1.6488127708435059
File Set 5.txt:         NOT Sorted:     Sorted:     1.6586071252822876


Number of Records:  4096
File Set 1.txt:         NOT Sorted:     Sorted:     0.0184687077999115
File Set 2.txt:         NOT Sorted:     Sorted:     0.018312623724341393
File Set 3.txt:         NOT Sorted:     Sorted:     0.018741531297564507
File Set 4.txt:         NOT Sorted:     Sorted:     0.01845288649201393
File Set 5.txt:         NOT Sorted:     Sorted:     0.018356671556830406


Number of Records:  512
File Set 1.txt:         NOT Sorted:     Sorted:     3.81015008315444E-4
File Set 2.txt:         NOT Sorted:     Sorted:     3.322649863548577E-4
File Set 3.txt:         NOT Sorted:     Sorted:     3.3953398815356195E-4
File Set 4.txt:         NOT Sorted:     Sorted:     3.314100031275302E-4
File Set 5.txt:         NOT Sorted:     Sorted:     3.42526996973902E-4


Number of Records:  65536
File Set 1.txt:         NOT Sorted:     Sorted:     6.721750736236572
File Set 2.txt:         NOT Sorted:     Sorted:     6.752647399902344
File Set 3.txt:         NOT Sorted:     Sorted:     6.7578630447387695
File Set 4.txt:         NOT Sorted:     Sorted:     6.696788787841797
File Set 5.txt:         NOT Sorted:     Sorted:     6.759160995483398


Number of Records:  8192
File Set 1.txt:         NOT Sorted:     Sorted:     0.08915259689092636
File Set 2.txt:         NOT Sorted:     Sorted:     0.09149085730314255
File Set 3.txt:         NOT Sorted:     Sorted:     0.0899868980050087
File Set 4.txt:         NOT Sorted:     Sorted:     0.08892638236284256
File Set 5.txt:         NOT Sorted:     Sorted:     0.08631659299135208

现在我们知道您的气泡排序完成了，让我们回头看看整个过程是否完成。是的，它确实：

这样可以很好地完成工作，并且似乎可以提供结果。

我想您实际上并没有问题，但是您希望草图做些视觉效果，而不是仅仅显示一个灰色框。但是，由于您没有 draw()函数，因此只会看到一个灰色框。如果不希望弹出窗口，请尝试在 exit()函数末尾添加对 setup()的调用。

如果您仍然认为它不起作用，请考虑以下事项：

添加更多打印语句，以便您可以更好地了解代码中的情况。
检查输出目录中的文件。
请注意，由于您没有 draw()函数，因此您的程序没有任何视觉效果，因此它所做的只是显示一个灰色框。这并不意味着您的程序没有响应！这只是意味着您没有告诉它做任何事情。考虑在 exit()函数的末尾添加对 setup()的调用。
如果其他所有方法均失败，请尝试通过上述过程来找出问题所在。尝试将其缩小到几行不符合您期望的行，而不是整个草图。

编辑

您提到获得类似的结果，并且只有在增加输入大小时才看到问题。这正是您应该期望的。

同样，添加打印语句是您最好的朋友。让我们从插入排序开始：

  int[] sortInteger(int[] input) {
    println("input length: " + input.length);

这将显示您的输入长度为1,048,576。由于插入排序为O（n ^ 2），这意味着您必须进行1,048,576 ^ 2个比较。这是1,099,511,627,776个比较！假设您的计算机每秒可以进行1,000次比较，则此算法需要34年才能完成。

（您的计算机每秒可能执行1000多次比较。但是，如果每秒可以进行100万次比较，则仍需要12天才能完成。如果每秒可以进行10亿次比较，则需要18分钟，并且仅用于一次运行一种算法。）

为了进一步对此进行调查，再次， println()语句是您最好的朋友。尝试添加一个 println()语句，该语句在插入排序循环中向您显示 i的值：

int i, j, tobeSorted;
    for (i = 1; i < input.length; i++) {
      tobeSorted = input[i];
      j = i;
      while (j > 0 && input[j - 1] > tobeSorted) {
        input[j] = input[j - 1];
        j--;
      }
      input[j] = tobeSorted;

      println("i: " + i);
    }

在您的程序运行时，您会看到这个数字上升。即使计算机速度很快，处理整个输入仍需要很长时间。这表明您的程序没有挂在任何地方，只需要很长时间即可执行。

这是研究这些算法的全部重点。计算机不是魔术计算器，在合理的时间内它们可以进行的计算数量是有限的。这就是为什么您的算法是线性扩展还是指数扩展都很重要：将输入大小增加一倍会花费两倍的时间，还是会花费更长的时间？

如果您仍然不相信结果，请继续尝试找出问题所在。当您认为程序“只是坐在那里”时，请尝试弄清楚程序在做什么。您应该确切地知道程序需要进行多少次计算，然后只需打印出到目前为止已完成的多少次计算即可。换句话说：打印出循环应执行的次数，然后打印出到目前为止循环已执行的次数。您将看到第一个值是一个大数字，然后看到第二个数字需要多长时间。

编辑2

这是草图的简化版本，可让您更轻松地更改输入长度，以更“灵活的方式”获得不同算法的特定时间：

void setup() {
  int[] input = getInput(1000);

  int start = millis();
  bubbleSort(input);
  int elapsed = millis() - start;
  println("Elapsed: " + elapsed);
  exit();
}

int[] getInput(int n) {
  int[] input = new int[n];

  for (int i = 0; i < n; i++) {
    input[i] = (int)random(n);
  }

  return input;
}

int[] bubbleSort(int[] input) {

  boolean swapped = true;
  int j = 0;
  int tmp;
  while (swapped) {
    swapped = false;
    j++;
    for (int i = 0; i < input.length - j; i++) {                                       
      if (input[i] > input[i + 1]) {                          
        tmp = input[i];
        input[i] = input[i + 1];
        input[i + 1] = tmp;
        swapped = true;
      }
    }
  }
  return input;
}

只需更改传递给 getInput()函数的值，就可以看到它如何影响算法完成的时间。

这是气泡排序：

N: 1,000     Time: 7
N: 10,000    Time: 145
N: 100,000   Time: 14600
N: 1,000,000 Time: 1467533

因此，您看到将输入大小乘以10并不会将时间乘以10，而是乘以100。这是因为气泡排序为O（n ^ 2），所以它花费的时间是平方的，而不仅仅是线性的。如果我们尝试将N增加到10,000,000，则气泡排序将需要大约40个小时！

合并排序更为宽容，因为它是O（n * log（n））：

N: 1,000      Time: 1
N: 10,000     Time: 5
N: 100,000    Time: 38
N: 1,000,000  Time: 221
N: 10,000,000 Time: 2202

这是要学习的重要课程：冒泡排序需要40个小时才能排序1000万个项目，而合并排序仅需要2秒钟！

因此，大输入需要很长时间才能进行排序这一事实正是要点。这不是错误。您的程序没有挂起，只是需要很长时间才能对那么多项目进行排序。像我的例子一样，尝试将问题分解成较小的草图，这样您可以更轻松地更仔细地了解它的作用。然后添加 println()语句以查看程序在哪里花费时间。这就是您解决问题的方式。

编辑3

现在，您提到在任务管理器中收到“未响应”消息。同样，这正是我所期望的。您要让Processing进行很多计算，并且在运行这些计算时，程序将不会响应。大型输入可能需要数小时（或数天，甚至更长！）才能完成。因此，您的程序不会在一夜之间完成，并且操作系统表示它没有响应，这也不足为奇。这是线程概念变得有用的地方，但这是完全独立的蠕虫病毒。

如果仍然遇到问题，请考虑使用我的小例子来重复该问题，然后您可以提出一个更具体的问题（在新问题中，而不是对此问题进行编辑）。确保包括正在使用的确切排序算法，正在使用的N值以及程序是否仍在执行或是否引发了错误。同样， println()语句是您最好的朋友。

关于java - 不同的排序算法在大型阵列上失败，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33387339/

文章推荐： javascript - 用变量缩短函数名

文章推荐： javascript - 使用 Dustjs 遍历对象数组

文章推荐：具有 0 延迟问题的 Javascript setTimeout

文章推荐： javascript - 如何检查此回调的返回

java - Java 方法如何检索属于该特定方法的方法对象？ ( java )
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger，它应该
java - (Java) Java 找不到我的图像文件
我是 Java 新手。我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做，因为我只是得到了想要的外观第一的)。这是我的主课代码: packag
java - java Java 有手动垃圾回收吗？
好的，今天我在接受采访，我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题，我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样？”。她是想骗我吗？还是我的一生都
java - Java 之谜 - Java
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
java - Java 字节码是否兼容不同版本的 Java？
如果我将使用 Java 5 代码的应用程序编译成字节码，生成的 .class 文件是否能够在 Java 1.4 下运行？如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
java - Java 缺少无符号原始类型是 Java 平台的特征还是 Java 语言的特征？
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索，似乎 Scala 也不支持无符号数据类型。限制是Java和S
java - Java 7 的 Java 字节码可以在其他版本的 Java 中工作吗
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行最佳答案通常，字节码无需修改即可在较新版本的 Java 上运行。它不会在旧版本上运行，除非您使用特殊参数 (
java -cp 。 test.java 与 java test.java
我有一个关于在命令提示符下执行 java 程序的基本问题。在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
java - 使用 Java (Java EE/Java SE) 的数据库应用程序设计模式
我已经阅读 StackOverflow 有一段时间了，现在我才鼓起勇气提出问题。我今年 20 岁，目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。基本上，我有一家提供簿记应用
java - Java 中的解析可在 Java 中访问
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
java - Java 中的解释性语言以及对 Java 方法的调用
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
java - java 序数 - Java I 类
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序，提示用户输入 1 到 10 之间的任意整数，然后以序数形式显示该整数并附加后缀。 public
java - 如何从 Java 执行 Java？
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
java - 延迟不适用于 java gui(java)
我想在 GUI 上添加延迟。我放置了 2 个 for 循环，然后重新绘制了一个标签，但这 2 个 for 循环一个接一个地执行，并且标签被重新绘制到最后一个。我能做什么？ for(int i=0;
java - Java 类中的硬编码 Java 列表
我正在对对象 Student 的列表项进行一些测试，但是我更喜欢在 java 类对象中创建硬编码列表，然后从那里提取数据，而不是连接到数据库并在结果集中选择记录。然而，自从我这样做以来已经很长时间了，
java - java 幕后对象创建(java 对象实例化)
我知道对象创建分为三个部分: 声明实例化初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化它必须使用
java - 车辆跟踪系统[java/Java EE]
我有兴趣使用 GPRS 构建车辆跟踪系统。但是，我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗？人们意识到任何问题吗？我计划使用 Java/Java EE - 有更好的技术吗？如果
java - 逆数组(Java)//逆数组(Java)
我可以通过递归方法反转数组，例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组，我不知道为什么，请帮助我。 public class Recursion { p
java - Java/Java EE 的构建和集成环境
有这样的标准方式吗？包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器最后我希望有一个自动构建和集成环境。
java - 我将如何从 java 程序打印文本？ ( java )
我什至不知道这是否可能，我非常怀疑它是否可能，但如果可以，您能告诉我怎么做吗？我只是想知道如何从打印机打印一些文本。有什么想法吗？最佳答案这里有更简单的事情。 import javax.swin

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

java - 不同的排序算法在大型阵列上失败