ใช้อัลกอริทึมการเรียงลำดับการนับใน Java

อัลกอริทึมการเรียงลำดับการนับคืออะไร?

Counting sort อัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพสำหรับ small ranges of integers ทำงานโดยการนับจำนวนครั้งที่เกิดขึ้นของแต่ละค่าในอาร์เรย์อินพุต จากนั้นใช้ข้อมูลนั้นเพื่อวางแต่ละค่าในตำแหน่งที่ถูกต้องในอาร์เรย์เอาต์พุต

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n+k) โดยที่ n คือขนาดของอินพุตอาร์เรย์ และ k คือช่วงของจำนวนเต็ม

CrunchifyCountingSortAlgo.java

นี่คือการใช้งาน Counting Sort ใน Java อย่างสมบูรณ์ เพียงคัดลอกลงใน IDEA ที่คุณต้องการแล้วเรียกใช้

 แพ็คเกจ crunchify.com.java.tutorials;

นำเข้า java.util.Arrays;

/**
 * @ผู้เขียน Crunchify.com
 * โปรแกรม: วิธีการใช้อัลกอริทึมการเรียงลำดับการนับใน java?
 * Counting sort เป็นอัลกอริทึมการเรียงลำดับที่เรียงลำดับองค์ประกอบของอาร์เรย์ 
 * โดยการนับจำนวนการเกิดขึ้นของแต่ละองค์ประกอบที่ไม่ซ้ำกันในอาร์เรย์
 */

CrunchifyCountingSortAlgo คลาสสาธารณะ {

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

        // อาร์เรย์จำนวนเต็ม 10 องค์ประกอบ
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("อาร์เรย์ดั้งเดิม:" + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

        CrunchifyCountingSortAlgo crunchify = ใหม่ CrunchifyCountingSortAlgo();
        crunchify.crunchifyCountingSortAlgorithm (crunchifyArray);

        crunchifyPrint ("\n");
        crunchifyPrint("ผลลัพธ์ของอัลกอริทึมการเรียงลำดับการนับแบบ Crunchify:" + Arrays.toString(crunchifyArray));
    }

    โมฆะคงที่ส่วนตัว crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * ผู้แต่ง: App Shah (Crunchify.com)
     *
     * การนับลอจิกการเรียงลำดับ:
     * นี่คือการใช้งานการเรียงลำดับการนับ ซึ่งเป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพสำหรับจำนวนเต็มช่วงเล็กๆ
     * ทำงานโดยการนับจำนวนครั้งที่เกิดขึ้นของแต่ละค่าในอาร์เรย์อินพุต
     * จากนั้นใช้ข้อมูลนั้นเพื่อวางแต่ละค่าในตำแหน่งที่ถูกต้องในอาร์เรย์เอาต์พุต
     * ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n+k)
     * โดยที่ n คือขนาดของอาร์เรย์อินพุต และ k คือช่วงของจำนวนเต็ม
     */


    int คงที่สาธารณะ [] crunchifyCountingSortAlgorithm (int [] crunchifyArray) {

        // getAsInt(): ถ้ามีค่าอยู่ ให้ส่งกลับค่า มิฉะนั้น ส่ง NoSuchElementException
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = ใหม่ int[crunchifyMax + 1];

        // crunchifyCount การเกิดขึ้นของแต่ละค่าในอาร์เรย์อินพุต
        สำหรับ (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("การเพิ่ม 1 เพื่อ crunchifyCount[" + crunchifyArray[i] 
                    + "], อาร์เรย์ crunchifyCount อยู่ในขณะนี้: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        int k = 0;
        สำหรับ (int i = 0; i <= crunchifyMax; i++) {
            สำหรับ (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("การเพิ่ม " + i + " ไปยังตำแหน่ง " + (k - 1) 
                        + " ในเอาต์พุตอาร์เรย์ ตอนนี้เอาต์พุตอาร์เรย์คือ: " + Arrays.toString(crunchifyArray));
            }
        }

        กลับ crunchifyArray;
    }

}

เพียงเรียกใช้โปรแกรมด้านบนเป็น Java Application ใน IntelliJ IDEA หรือ Eclipse IDE และคุณจะได้ผลลัพธ์ดังนี้

ผลลัพธ์คอนโซล IntelliJ IDEA

 อาร์เรย์ดั้งเดิม: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


การเพิ่ม 1 ให้กับ crunchifyCount[9] ตอนนี้อาร์เรย์ของ crunchifyCount คือ: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[3] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[6] ตอนนี้อาร์เรย์ของ crunchifyCount คือ: [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[6] ตอนนี้อาร์เรย์ของ crunchifyCount คือ: [0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[1] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[12] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
การเพิ่ม 1 ให้กับ crunchifyCount[32] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
การเพิ่ม 1 ให้กับ crunchifyCount[29] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
การเพิ่ม 1 ให้กับ crunchifyCount[2] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
การเพิ่ม 1 ให้กับ crunchifyCount[9] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
การเพิ่ม 1 ให้กับ crunchifyCount[3] ตอนนี้อาร์เรย์ crunchifyCount คือ: [0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]


การเพิ่ม 1 ไปยังตำแหน่ง 0 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตคือ: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
การเพิ่ม 2 ในตำแหน่งที่ 1 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตคือ: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
การเพิ่ม 3 ในตำแหน่งที่ 2 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตคือ: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
การเพิ่ม 3 ในตำแหน่งที่ 3 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตคือ: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
การเพิ่ม 6 ในตำแหน่งที่ 4 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตคือ: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
การเพิ่ม 6 ไปที่ตำแหน่ง 5 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตจะเป็น: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
การเพิ่ม 9 ไปยังตำแหน่ง 6 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตจะเป็น: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
การเพิ่ม 9 ไปยังตำแหน่ง 7 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตจะเป็น: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
การเพิ่ม 12 ไปที่ตำแหน่ง 8 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตจะเป็น: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
การเพิ่ม 29 ไปที่ตำแหน่ง 9 ในอาร์เรย์เอาต์พุต ตอนนี้อาร์เรย์เอาต์พุตจะเป็น: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
การเพิ่ม 32 ไปที่ตำแหน่ง 10 ในอาร์เรย์เอาต์พุต ขณะนี้อาร์เรย์เอาต์พุตคือ: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


ผลลัพธ์ของอัลกอริทึมการเรียงลำดับการนับแบบขบเคี้ยว: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

กระบวนการเสร็จสิ้นด้วยรหัสออก 0 

แจ้งให้เราทราบหากคุณประสบปัญหาใด ๆ ที่ทำงานเหนือโปรแกรม Counting Sort Algorithm Java