創建快速排序，無遞歸和堆棧

我有一個任務寫在Java中的快速排序（只有posivite數字）algorythm（我不能使用任何導入，但掃描儀），但沒有遞歸和沒有堆棧。
我有兩個問題吧：創建快速排序，無遞歸和堆棧

我做堆和遞歸版本understeand迭代快速排序，但我無法想象如何做到這一點離不開它。我聽說過一些'就地'實施，但我真的不明白 - 是我的問題的解決方案？
如果有人能告訴我一種方法來做到這一點（如果可以的話，不要發佈實現，我只是想讓它不要複製某人的代碼），或者推薦一些我可以找到它的書（或者類似的問題）。
正在實施排序插入一些小陣列是一個好主意？如果是的話有多大應該是N在此代碼：
```
if (arraySize < N) 
    insertionSort 
else 
    quickSort 
fi 
```

2015-05-01 MaLiN2223

要回答最後一個問題，大約有15個。 – EJP

顯然，我的任務是找到只 posivite號，這裏是我的解決方案：

public static void quickSort(final int size) { 
    int l = 0; 
    int r = size - 1; 
    int q, i = 0; 
    int tmpr = r; 
    while (true) { 
     i--; 
     while (l < tmpr) { 
      q = partition(l, tmpr); 
      arr[tmpr] = -arr[tmpr]; 
      tmpr = q - 1; 
      ++i; 
     } 
     if (i < 0) 
      break; 
     l++; 
     tmpr = findNextR(l, size); 
     arr[tmpr] = -arr[tmpr]; 
    } 
} 

private static int findNextR(final int l, final int size) { 
    for (int i = l; i < size; ++i) { 
     if (arr[i] < 0) 
      return i; 
    } 
    return size - 1; 
} 

private static int partition(int l, int r) { 
    long pivot = arr[(l + r)/2]; 
    while (l <= r) { 
     while (arr[r] > pivot) 
      r--; 
     while (arr[l] < pivot) 
      l++; 
     if (l <= r) { 
      long tmp = arr[r]; 
      arr[r] = arr[l]; 
      arr[l] = tmp; 
      l++; 
      r--; 
     } 
    } 
    return l; 
}

我的數組排序是在我班上一個靜態數組。它基於查找和創建負數。通過使用數組中的中間元素創建分區，但使用中位數也很好（取決於數組）。我希望有人會找到這個有用的。

來源

2015-05-23 23:31:28 MaLiN2223

-1

「非遞歸快速」 A谷歌生產的答案擺......包括這一個：Non recursive QuickSort「你的語言可能會有所不同，」但基本原則不會。

我個人認爲，如果你要排序的話，不妨在所有情況下使用Quicksort。。。

除非，當然，你可以簡單地在你最喜歡的目標語言使用sort()功能，它留給語言實現者選擇了一個巧妙的算法（Joey：嗯，它可能快速排序...）你。如果你沒有有指定一個算法來做這樣一個共同的任務，「不要！」 :-)

來源

2015-05-04 22:20:24

是的，google非常有用，但我找不到任何非遞歸quicksort堆棧（如問題所述）。我創建了這個算法，因爲它是我的任務來創建它不使用一些內置函數，但感謝您的答案。 – MaLiN2223

我從來沒有見過*不是遞歸的QuickSort實現。但是......「以非遞歸方式表達遞歸算法並不那麼困難......」 –

就像Arrays.sort（int []）的Java8實現使用閾值47一樣，任何小於該值的值都會使用插入進行排序。然而，他們的快速排序實施非常複雜，並有一些初始開銷，因此將47視爲上限。

來源

2015-05-12 22:28:15

創建快速排序，無遞歸和堆棧

回答

相關問題