Агуулгын хүснэгт:

Та хувин ангилах ажлыг хэрхэн хийдэг вэ?
Та хувин ангилах ажлыг хэрхэн хийдэг вэ?

Видео: Та хувин ангилах ажлыг хэрхэн хийдэг вэ?

Видео: Та хувин ангилах ажлыг хэрхэн хийдэг вэ?
Видео: Хоногийн 24 цагийг илүү үр бүтээлтэй өнгөрүүлэх шалгарсан аргууд 2024, Арваннэгдүгээр
Anonim

Хувин ангилах нь дараах байдлаар ажилладаг

  1. Эхэндээ хоосон массивыг тохируулах " хувин ".
  2. Scatter: Объект бүрийг дотор нь байрлуулж, эх массив дээр оч хувин .
  3. Эрэмбэлэх тус бүр нь хоосон биш хувин .
  4. Цуглуулах: зочилно уу хувин дарааллаар нь тохируулж, бүх элементүүдийг анхны массив руу буцаана.

Түүнээс гадна жишээн дээр хувин ангилах гэж юу вэ?

Мөн та ажил олох болно жишээнүүд -ийн хувин ангилах C, C++, Java болон Python хэл дээр. Хувин ангилах нь ангилах техник тэр төрөл эхлээд элементүүдийг хэд хэдэн бүлэгт хуваах замаар элементүүдийг хувин . Элементүүд эхлээд тархсан байна хувин дараа нь элементүүд хувин байна эрэмбэлсэн.

Цаашилбал, хувин сортыг хаана хэрэглэдэг вэ? Шанаганы төрөл оролт нь мужид жигд тархсан үед голчлон ашигтай байдаг. Жишээлбэл, дараах асуудлыг авч үзье. Эрэмбэлэх 0.0-ээс 1.0 хүртэлх мужид жигд тархсан хөвөгч цэгүүдийн том багц.

Үүнийг анхаарч үзвэл, хувингийн тоог хэрхэн олох вэ?

Хэрэв хувин тус бүр нь 2^k урттай хувин нэг хэмжээтэй, мөн хувин ангилах тоолох болж доройтдог ангилах . Тиймээс, та тус бүрийг хүсч байна хувин хэмжээ 1-ээс их байх. Хэрэв бидэнд n хувин , мөн msbits(x, k) нь 2^k утгыг, дараа нь тус бүрийг буцаана хувин хэмжээ нь 2^k/n.

Хувиныг ангилах цаг хугацааны нарийн төвөгтэй байдал юу вэ?

Дундаж цаг хугацааны нарийн төвөгтэй байдал төлөө Хувин ангилах O(n+k) байна. Хамгийн муу нь цаг хугацааны нарийн төвөгтэй байдал O(n²) байна. Орон зай нарийн төвөгтэй байдал төлөө Хувин ангилах O(n+k) байна.

Зөвлөмж болгож буй: