我知道快速排序是最好的排序演算法，這也是我的第一個想法。但是如果我有以下情況：
typedef struct{
char name[35];
int age;
}person;
如果我有一個包含 N 個元素的型別陣列，person并且我想按姓名對 30-40 歲之間的人進行排序。快速排序在這里仍然是最好的，因為我們不會對陣列中的所有人進行排序，只對年齡在 30 到 40 歲之間的人進行排序。如果是這樣，我將如何選擇樞軸（因為選擇中間元素并不能保證人在正確的年齡范圍內）？我還認為合并排序可能是一個不錯的選擇，因為我可以將陣列拆分為 2 個不同的陣列并放置條件。
uj5u.com熱心網友回復：
首先要做的是找到age30..40 范圍內的專案，并將它們復制到優化的增長資料結構中。這個資料結構是一個陣列，每次沒有足夠的剩余空間（即std::vector在 C 中或例如在 C 中的this）時，其容量都會呈指數增長。
這個新資料結構中的每一項都定義為：
typedef struct {
uint32_t name_prefix;
uint32_t id; /* Assume the number of persons is not bigger than 4 billion */
} person_ref;
wherename_prefix包含的第一個字符，person::namewhereid包含專案在初始未過濾陣列中的位置。假設person::name包含 ASCII/ANSI 字符，例如可以是(p.name[0] << 24) | (p.name[1] << 16) | (p.name[2] << 8) | p.name[3]. 雖然聽起來可能很昂貴，但現代主流處理器只需 1 條快速指令即可做到這一點。如果名稱有一些額外的限制（例如，大寫的可列印 ASCII 字符），您可以在此前綴中包含更多字符。
然后，您可以使用簡單的快速排序（或更好：Introsort）對新資料結構進行排序。請注意，qsort可以在 C 和std::sortC 中使用。比較運算子可以是：
/* For a C code, please use references instead of pointers */
bool compare(const person& p1, const person* p2) {
const uint32_t prefix1 = p1.name_prefix;
const uint32_t prefix2 = p2.name_prefix;
return prefix1 < prefix2 ||
(prefix1 == prefix2 && strcmp(array[p1.id].name, array[p2.id].name) < 0);
}
其中array是包含所有未過濾專案的原始陣列。
最后，您可以通過該欄位將專案復制回來person_ref::id。
這種方法效果很好，因為通常假定名稱的前綴不相等。事實上，比較整數比用 比較兩個字串要快得多strcmp。此外，處理小專案會使排序演算法更快，因為副本成本更低，而且完整陣列可以更好地適應快速 CPU 快取。如果很多前綴相等并且輸入資料結構很大，那么最好使用64位整數前綴，或者在最壞的情況下將過濾后的專案復制到另一個資料結構中（以便更好地使用CPU快取） .
如果過濾專案的數量很大，并且您想要更快的排序，您可以使用線性時間基數排序與介紹排序相結合，以便對共享相同前綴的人進行排序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/413257.html
標籤：
下一篇：呼叫句柄/鉤子的3D字串陣列