การวิเคราะห์เชิงลึกของการเรียงลำดับอาร์เรย์ใหม่ (วิธีใส่เลขคี่ทั้งหมดก่อนเลขคู่ทั้งหมด)

ที่นี่เราขอแนะนำอัลกอริธึมที่มีประสิทธิภาพซึ่งสามารถทำได้ภายในความซับซ้อนของเวลา O(n)

แนวคิดหลักคือ กำหนดพอยน์เตอร์สองตัว โดยตัวชี้ A หนึ่งตัวจะสแกนจากด้านหน้าไปด้านหลัง และตัวชี้ B หนึ่งตัวจะสแกนจากด้านหลังไปด้านหน้า ตัวชี้ A สแกนเป็นเลขคู่และหยุดชั่วคราว ตัวชี้ B สแกนเป็นเลขคี่และหยุดชั่วคราว จากนั้นจึงแลกเปลี่ยนตัวเลขทั้งสอง หลังจากการแลกเปลี่ยน ให้สแกนและแลกเปลี่ยนต่อดังข้างต้นจนกว่าตัวชี้ A และตัวชี้ B ตรงกันและหยุด

รหัส Java ของอัลกอริทึมนี้เป็นดังนี้:

คัดลอกรหัสรหัส ดังต่อไปนี้:

สั่งซื้อแพ็คเกจใหม่;

สั่งซื้อคลาสสาธารณะใหม่ {

โมฆะคงที่สาธารณะ main (String [] args) {

รายการ int[] = { 1, 2, 3, 4, 5, 7, 9, 11 };

จัดลำดับ OddEven ใหม่ (รายการ);

-

โมฆะคงสาธารณะ reorderOddEven (รายการ int []) {

ความยาว int = list.length;

สำหรับ (int i = 0; i <ความยาว; i++) {

System.out.print (รายการ [i] + " ");

-

System.out.print("/n");

int เริ่มต้น = 0;

สิ้นสุด int = ความยาว - 1;

ในขณะที่ (เริ่มต้น <สิ้นสุด) {

ในขณะที่ (เริ่มต้น <สิ้นสุด && (รายการ[เริ่มต้น] & 0x1) != 0)

เริ่มต้น++;

ในขณะที่ (เริ่มต้น <สิ้นสุด && (รายการ [สิ้นสุด] & 0x1) == 0)

จบ--;

ถ้า (เริ่มต้น <สิ้นสุด) {

int temp = รายการ [เริ่มต้น];

รายการ[เริ่มต้น] = รายการ[สิ้นสุด];

รายการ [สิ้นสุด] = อุณหภูมิ;

-

-

สำหรับ (int i = 0; i <ความยาว; i++) {

System.out.print (รายการ [i] + " ");

-

-

-