فرز التحديد البسيط: (حدد الحد الأدنى للقيمة ، ضعها أولاً ، ثم يتحرك البت الأول للخلف ، لذلك الحلقة) يقارن البت الأول مع كل واحدة بعد التالي ، في كل مرة يتم فيها تصدرت أصغر البتات ، والبت الأولى للخلف الترويج (أي أن الرقم الأول المحدد للتو هو الحد الأدنى لقيمة ، لم يعد يشارك في المقارنة ، يتم تقليل عدد المقارنات بمقدار 1)
التعقيد: عدد العمليات المطلوبة لأداء حركة السجلات هو 0-- 3 (N-1). / 2. إجمالي تعقيد الوقت هو O (N2) ؛
تعقيد الفضاء O (1)
تحسين الخوارزمية: في كل مرة تقارن فيها ، فإن وضع أصغر قيمة في المقام الأول ، بحيث يمكنك مقارنتها بالنهاية ، والعثور على القيمة الدنيا ، ووضعها مباشرة في المقام الأول ، مما يلغي عمليات التبديل والتحريك بلا معنى. يمكنك أيضًا تغيير الاتجاه ، ومقارنة الشيء الأخير مع كل واحد سابق ، وجعل الحد الأقصى لقيمة القيمة في كل مرة ، وادفع آخر شيء للأمام.
رمز المصدر جافا:
نسخة الكود كما يلي:
Selectsorts SelectSort (Date [] Days) {
int min
تاريخ التاريخ
لـ (int i = 0 ؛ i <days.length ؛ i ++) {
min = i ؛
لـ (int j = min+1 ؛ j <days.length ؛ j ++) {
if (Days [min] .compare (days [j])> 0) {
min = j ؛
}
}
if (min! = i) {
temp = days [i] ؛
أيام [i] = أيام [دقيقة] ؛
أيام [دقيقة] = درجة الحرارة ؛
}
}
}
تاريخ الفصل {
سنة ، الشهر ، اليوم ؛
التاريخ (int y ، int m ، int d) {
سنة = ص ؛
الشهر = م ؛
اليوم = د ؛
}
int العامة مقارنة (تاريخ التاريخ) {
سنة العودة
: شهر> تاريخ؟
: اليوم> يوم؟
}
print print print () {
System.out.println (year + "" + month + "" + day) ؛
}
}
نوع الاختيار البسيط:
يشبه فرز التحديد البسيط فرز الفقاعات (فرز الفقاعات). الفرق الوحيد هو أن فرز الفقاعات يتبادل موقع العنصر في كل مرة يجد أن تكون أصغر (أو أكبر من القيمة الحالية) ، في حين أن فرز التحديد البسيط هو تحديد أكبر قيمة في العناصر المتبقية وبيانات التبادل في الموقف الحالي.
على سبيل المثال ، لمجموعة العناصر r = {37 ، 40 ، 38 ، 42 ، 461 ، 5 ، 7 ، 9 ، 12}
بالترتيب الأول: يتم تبادل 37 مباشرة بـ 5 ، ويشكل تسلسلًا جديدًا R1 = {5،40،38،46،461،37،7،9،12}
بالترتيب الثاني: يتم تبادل 40 مباشرة بـ 7 ، ويشكل تسلسلًا جديدًا R2 = {5،7،38،42،461،37،40،9،12}
وما إلى ذلك حتى العنصر الأخير (ملاحظة: بالترتيب الثاني ، 38 أصغر من 42 ، لكنها لا تبادل البيانات).
فيما يلي إصدار تنفيذ Java يختار ببساطة الفرز:
نسخة الكود كما يلي:
SelectionSort static static static (int []) {
if (data == null || data.length <= 1)
يعود؛
int i ، j ، value ، minpos ، len = data.length ؛
int outer = len - 1 ، tmp ؛
لـ (i = 0 ؛ i <Outer ؛ i ++) {
القيمة = البيانات [i] ؛
minpos = -1 ؛
لـ (j = i+1 ؛ j <len ؛ j ++) {
if (data [j] <value) {
minpos = j ؛
القيمة = البيانات [J] ؛
}
}
if (minpos! = -1) {
TMP = البيانات [i] ؛
البيانات [i] = القيمة ؛
البيانات [minpos] = TMP ؛
}
// لـ (int k = 0 ؛ k <len ؛ k ++) {
// system.out.print (data [k] + "،") ؛
//}
// system.out.println () ؛
}
}
الفراغ الثابت العام الرئيسي (سلسلة [] args) {
int [] coll = {
37 ، 40 ، 38 ، 42 ، 461 ، 5 ، 7 ، 9 ، 12
} ؛
Selectionort (Coll) ؛
لـ (int i = 0 ؛ i <coll.length ؛ i ++) {
System.out.print (coll [i] + "،") ؛
}
}
نوع اختيار الأشجار
خوارزمية فرز اختيار الأشجار هي خوارزمية نموذجية تتداول مساحة للوقت مقارنة بفرز الاختيار البسيط. تتمثل الفكرة في علاج العناصر N المرتبة ، وبناء أرقام صغيرة نسبيًا (N+1)/2 ، ثم بناء أرقام صغيرة نسبيًا [N+1]/4 حتى يكون هناك عنصر واحد فقط. شيدت في شجرة ثنائية تماما.
عند الفرز ، يكون العنصر هو الأصغر.
فيما يلي نسخة تنفيذ Java من فرز اختيار الأشجار:
نسخة الكود كما يلي:
TreeSelectionSort {بيانات الفراغ الثابتة العامة (int []) {
if (data == null || data.length <= 1)
يعود؛
int len = data.length ، low = 0 ، i ، j ؛
// إضافة مساحة مساعدة
int [] tmp = new int [2*len -1] ؛
int tsize = tmp.length ؛
// بناء شجرة
لـ (i = len-1 ، j = tmp.length-1 ؛ i> = 0 ؛ i-، j-) {
TMP [j] = البيانات [i] ؛
}
لـ (i = tsize -1 ؛ i> 0 ؛ i- = 2) {
TMP [(I-1)/2] = TMP [I]> TMP [I-1]؟
}
//نهاية
// إزالة الحد الأدنى من العقدة.
بينما (منخفض <len) {
البيانات [low ++] = tmp [0] ؛
لـ (j = tsize-1 ؛ tmp [j]! = tmp [0] ؛ j--) ؛
tmp [j] = integer.max_value ؛
بينما (j> 0) {
إذا (j ٪ 2 == 0) {// إذا كانت العقدة اليمنى
TMP [(J-1)/2] = TMP [J]> TMP [J-1]؟ TMP [J-1]: TMP [J] ؛
J = (J-1)/2 ؛
} آخر {// إذا كانت العقدة اليسرى
TMP [J/2] = TMP [J]> TMP [J+1]؟
j = j/2 ؛
}
}
}
}
عند إنشاء شجرة ثنائية كاملة ، يلزم 2*n -1 المساحة المساعدة لمجموعة من عناصر n.
شفرة:
نسخة الكود كما يلي:
بينما (j> 0) {
إذا (j ٪ 2 == 0) {// إذا كانت العقدة اليمنى
TMP [(J-1)/2] = TMP [J]> TMP [J-1]؟ TMP [J-1]: TMP [J] ؛
J = (J-1)/2 ؛
} آخر {// إذا كانت العقدة اليسرى
TMP [J/2] = TMP [J]> TMP [J+1]؟
j = j/2 ؛
}
}
ثم قم بتنفيذ البناء العودية للحد الأدنى من القيمة في المجموعة الجديدة.