並行實現氣泡排序

Question

該項目的主要思想是並行氣泡排序。我的這個項目的方法是，創建一個大數組，然後根據線程數將它分成幾部分（4或5）。例如，如果數組的大小爲10，我將它分成2個子數組，0-4和5-9，然後一個線程必須掃描大數組，如果數值在0-4之間，則分配第一個子數組，如果沒有分配給下一個子數組。然後將泡泡排序算法同時應用於所有子陣列。最後，所有的子數組應該被添加到線程安全隊列中。 現在我有三個類，我創建數組的主類，用於洗牌數組的U tiles類，查找數組的最小和最大值以及具有泡沫排序算法的冒泡排序類。 我現在面臨的挑戰是，如何將大數組分成小的子數組，並用值填充子數組。 我會感謝所有的建議和幫助。下是我的課程。

package com.company; 

import javax.xml.transform.sax.SAXSource; 
import java.util.Random; 

public class Main { 

    public static void main(String[] args) {  

     // filling the array with integer values 
     int[] anArray = Utils.fillArray((int) 10);   
     Utils.shuffleArray(anArray); 

    // find the min and max of the array 
     System.out.println("************************"); 


     BubbleSort sort = new BubbleSort(anArray); 
     profiler.start(); 
     sort.sortMethod(); 
//  Utils.printArray(anArray);  
     Utils.findMinMax(anArray); 

    } 

} 

package com.company; 


import java.util.Arrays; 
import java.util.List; 
import java.util.concurrent.ThreadLocalRandom; 

public class Utils { 

    private static volatile int max; 
    private static volatile int min; 
    private static int[][] arrays; 


     public Utils(int[][] arrays,int[] array) { 
     max = array[0]; 
     min = array[0]; 
    } 

    // taken from the kings class 
    // source: http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array 
    // Implementing Fisher�Yates shuffle 
    public static void shuffleArray(int[] ar) { 
     // If running on Java 6 or older, use `new Random()` on RHS here 
     ThreadLocalRandom rnd = ThreadLocalRandom.current(); 
     for (int i = ar.length - 1; i > 0; i--) { 
      int index = rnd.nextInt(i + 1); 
      // Simple swap 
      int a = ar[index]; 
      ar[index] = ar[i]; 
      ar[i] = a; 
     } 
    } 

    public static void printArray(int[] anArray) { 
     System.out.print("Array: "); 
     for (int i=0; i< anArray.length; i++){ 
      System.out.print(anArray[i]+" "); 
     } 
     System.out.println(); 
    } 


    public static int[] fillArray(int amount) { 
     int[] result = new int[amount]; 
     for (int i=0; i<amount; i++){ 
      result[i] = i; 
     } 
     return result; 
    } 
    public static void findMinMax(int[] array) { 
     int i = 0; 
     for (; i < (array.length)/2; i++) { 
      int num1 = array[1 * 2]; 
      int num2 = array[i * 2 + 1]; 
      if (num1 >= num2) { 
       if (num1 > max) 
        max = num1; 
       if (num2 < min) 
        min = num2; 
      } else { 
       if (num2 > max) { 
        max = num2; 
        if (num1 < min) 
         min = num1; 
       } 
      } 
     } 
     if (i * 2 < array.length) { 
      int num = array[i * 2]; 
      if (num > max) 
       max = num; 
      if (num < min) 
       min = num; 
     } 

     System.out.println("min is: " + min); 
     System.out.println("max is : " + max); 

    } 
       } 

public static int getMax() { 
     return max; 
     } 

    public static int getMin() { 
     return min; 
    } 
    public static void print(int[] anArray, int i) { 
    } 
} 

Answer 1

我想你應該嘗試合併排序，使用Fork/Join。

喜歡這裏：

import java.util.Random; 
import java.util.concurrent.*; 

/** 
* Example of Merge Sort using Fork/Join framework. 
* 
* @author L.Gobinath 
*/ 
public class ForkJoinArraySort { 
// From Java 7 '_' can be used to separate digits. 
public static final int ARRAY_SIZE = 10_000_000; 

public static void main(String[] args) { 
    // Create a pool of threads 
    ForkJoinPool pool = new ForkJoinPool(); 
    int[] array = createArray(ARRAY_SIZE); 
    long startTime; 
    long endTime; 

    MergeSort mergeSort = new MergeSort(array, 0, array.length - 1); 
    startTime = System.currentTimeMillis(); 

    pool.invoke(mergeSort); // Start execution and wait for result/return 

    endTime = System.currentTimeMillis(); 
    System.out.println("Time taken: " + (endTime - startTime) + " millis"); 
} 

/** 
* Create an array with random numbers. 
* @param size Size of the array. 
* @return  An array with the given size. 
*/ 
private static int[] createArray(final int size) { 
    int[] array = new int[size]; 
    Random rand = new Random(); 
    for (int i = 0; i < size; i++) { 
     array[i] = rand.nextInt(1000); 
    } 
    return array; 
} 
} 

/** 
* Extends RecursiveAction. 
* Notice that the compute method does not return anything. 
*/ 
class MergeSort extends RecursiveAction { 
private int array[]; 
private int left; 
private int right; 

public MergeSort(int[] array, int left, int right) { 
    this.array = array; 
    this.left = left; 
    this.right = right; 
} 

/** 
* Inherited from RecursiveAction. 
* Compare it with the run method of a Thread. 
*/ 
@Override 
protected void compute() { 
    if (left < right) { 
     int mid = (left + right)/2; 
     RecursiveAction leftSort = new MergeSort(array, left, mid); 
     RecursiveAction rightSort = new MergeSort(array, mid + 1, right); 
     invokeAll(leftSort, rightSort); 
     merge(left, mid, right); 
    } 
} 

/** 
* Merge two parts of an array in sorted manner. 
* @param left Left side of left array. 
* @param mid Middle of separation. 
* @param right Right side of right array. 
*/ 
private void merge(int left, int mid, int right) { 
    int temp [] = new int[right - left + 1]; 
    int x = left; 
    int y = mid + 1; 
    int z = 0; 

//There some kind of sort at the leaf 
//You can use your BubbleSort class 
//*************************************************************** 
    while (x <= mid && y <= right) { 
     if (array[x] <= array[y]) { 
      temp[z] = array[x]; 
      z++; 
      x++; 
     } else { 
      temp[z] = array[y]; 
      z++; 
      y++; 
     } 
    } 
//*************************************************************** 


    while (y <= right) { 
     temp[z++] = array[y++]; 
    } 
    while (x <= mid) { 
     temp[z++] = array[x++]; 
    } 

    for (z = 0; z < temp.length; z++) { 
     array[left + z] = temp[z]; 
    } 
} 
} 

（我有我自己的算法，在這裏我使用的合併排序，並與冒泡排序排序，當我研究algorithmization葉節點但這是很久以前的事，我輸了，對不起）

PS我認爲回想一下Array.sort仍然會比個人實現泡泡分類更快速是多餘的。