氣泡排序到間隙排序修改

我遇到了問題，需要您的指導。基本上我設法創建了這個Bubble Sort方法。我該如何修改這個空隙排序，而不是每次通過列表比較相鄰元素，比較一些數字（i）的位置相隔的元素，其中（i）是小於n的整數。例如，第一個元素將與第（i + 1）個元素，第（i + 2）個元素的第2個元素，（ni）元素的第n個元素等進行比較。當所有元素已經進行了比較。在接下來的迭代，我之前是一些大於1的減少和過程繼續進行，直到i小於1氣泡排序到間隙排序修改

public static void bubbleSort (Comparable[] data, int maxlength){ 
    int position, scan; 
    Comparable temp; 

    for (position = maxlength; position >= 1; position--){ 
     for (scan = 0; scan <= position – 1; scan++){ 
      if (data[scan].compareTo(data[scan+1]) > 0){ 
       // Swap the values 
       temp = data[scan]; 
       data[scan] = data[scan + 1]; 
       data[scan + 1] = temp; 
      } 
     } 
    } 
}

來源

2012-04-03 serge

您是否在尋找GapSort實現？看看這個鏈接的第二篇文章：http://www.daniweb.com/software-development/java/threads/238791/gap-sort – Fido 2012-04-03 07:18:51

thnx。但你能解釋一下嗎？「雙SF = 1.3;」爲什麼這很有用？ – serge 2012-04-03 07:28:46

這個想法是從一個很大的差距開始，並縮小每個循環。 SF就像是一個「收縮係數」（我在文章中假設的意思是「收縮因子」），在這種情況下大約爲76％（這意味着在每次迭代中差距減少到76％值）。 – Fido 2012-04-03 07:33:53

此代碼（在http://www.daniweb.com/software-development/java/threads/238791/gap-sort找到）可以幫助你：

public static void gapSort (Comparable [] data, int size) { 
    int index; 
    int gap, top; 
    Comparable temp; 
    boolean exchanged; 

    double SF = 1.3; 
    gap = size; 

    do { 
     exchanged = false; 
     gap = (int) (gap/SF); 
     if (gap == 0){ 
      gap = 1; 
     } 
     for (index = 1; index <= size - gap; index++) { 
      if (data [index].compareTo(data [index + gap]) > 0) { 
       temp = data [index]; 
       data [index] = data [index + gap]; 
       data [index + gap] = temp; 
       exchanged = true; 
      } 
     } 
    } while (exchanged || gap > 1); 
}

記住實現Comparable接口的對象數組排序的最簡單方法通常是Arrays.Sort()

來源

2012-04-03 07:51:06 Fido

氣泡排序到間隙排序修改

回答

相關問題