Bucket sort runs in linear time on

Bucket sort runs in linear time on the average. It assumes that the input is generated by a random process that distributes elements uniformly over the interval [0, 1).

The idea of Bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over (0, 1), we don't expect many numbers to fall into each bucket. To produce the output, simply sort the numbers in each bucket and then go through the bucket in order, listing the elements in each.

The code assumes that input is in n-element array A and each element in A satisfies 0 ≤ A[i] ≤ 1. We also need an auxiliary array B[0 . . n -1] for linked-lists (buckets).

ผลลัพธ์ (ไทย) 1:

เรียงลำดับกลุ่มที่ทำงานในเวลาเชิงเส้นโดยเฉลี่ย จึงสันนิษฐานว่า การป้อนข้อมูลถูกสร้างขึ้น โดยกระบวนการสุ่มที่กระจายองค์ประกอบสม่ำเสมอเมื่อเทียบเคียงผ่านช่วง [0, 1)ความคิดของการเรียงลำดับกลุ่มจะแบ่งช่วง [0, 1) subintervals ขนาดเท่ากับ n หรือถัง ยกหมายเลขสำหรับการป้อนค่า n เป็นกลุ่ม เนื่องจากปัจจัยการผลิตสม่ำเสมอเมื่อเทียบเคียงกระจายผ่าน (0, 1), เราไม่คาดว่าตัวเลขมากตกถังละ การผลิตผลผลิต เพียงแค่เรียงลำดับหมายเลขในแต่ละกลุ่ม และผ่านถังตามลำดับ องค์ประกอบในแต่ละรายการรหัสสันนิษฐานว่า มีใน n องค์ประกอบแถวลำดับ A และแต่ละองค์ประกอบใน A ตรง 0 ≤≤ [i] 1 เราต้องเป็นแถวเสริม B [0 .. n -1] การเชื่อมโยงรายการ (กลุ่ม)

ผลลัพธ์ (ไทย) 2:

จัดเรียงถังวิ่งในเส้นเวลาโดยเฉลี่ย จะถือว่าการป้อนข้อมูลที่ถูกสร้างขึ้นโดยกระบวนการสุ่มที่กระจายองค์ประกอบสม่ำเสมอตลอดช่วง [0, 1). ความคิดของการจัดเรียงถังคือการแบ่งช่วง [0, 1) เป็น n subintervals ขนาดเท่ากับหรือถัง, และ แล้วแจกจ่ายป้อนข้อมูลตัวเลขที่ n ลงในถัง เนื่องจากปัจจัยการผลิตที่มีการกระจายไป (0, 1) เราไม่ได้คาดหวังตัวเลขมากจะตกอยู่ในถังแต่ละ ในการผลิตการส่งออกเพียงแค่การจัดเรียงตัวเลขในแต่ละถังแล้วไปผ่านถังในการสั่งซื้อรายชื่อองค์ประกอบในแต่ละ. รหัสอนุมานว่าการป้อนข้อมูลอยู่ในอาร์เรย์ n-ธาตุและองค์ประกอบในการตอบสนองแต่ละ 0 ≤ [i ] ≤ 1. เรายังต้อง B อาร์เรย์เสริม [0 . -1] สำหรับรายการที่เชื่อมโยง (ถัง)

ผลลัพธ์ (ไทย) 3:

ประเภทถังวิ่งในเวลาเชิงเส้นโดยเฉลี่ย สมมุติว่าการป้อนข้อมูลจะถูกสร้างขึ้นโดยการสุ่มกระบวนการกระจายองค์ประกอบอย่างสม่ำเสมอมากกว่าช่วง [ 0 , 1 ) .

ความคิดเรียงถังคือการแบ่งช่วง [ 0 , 1 ) ใน subintervals N ขนาดเท่ากัน หรือถัง แล้วกระจาย n ใส่หมายเลขลงในถัง เนื่องจากกระผมเป็นจุดกระจาย ( 0 , 1 )เราไม่ได้คาดหวังว่าตัวเลขที่ตกอยู่ในแต่ละถัง เพื่อผลิตออก เพียงแค่เรียงลำดับตัวเลขในแต่ละถัง และผ่านถังน้ำเพื่อรายชื่อขององค์ประกอบในแต่ละ

รหัสอนุมานว่าใส่ใน n-element เรย์และแต่ละองค์ประกอบในระบบ 0 ≤ [ i ] ≤ 1 เรายังต้องช่วยเรย์ b [ 0 - 1 ] รายการที่เชื่อมโยง ( ถัง ) .