นำเข้า java.util.สุ่ม;
-
* การเรียงลำดับคลาสทดสอบ
-
* การจำแนกประเภทของอัลกอริธึมการเรียงลำดับมีดังนี้: 1. การเรียงลำดับการแทรก (การเรียงลำดับการแทรกโดยตรง, การเรียงลำดับการแทรกครึ่งหนึ่ง, การเรียงลำดับแบบ Hill); 2. การเรียงลำดับแบบแลกเปลี่ยน (การเรียงลำดับแบบฟอง, การเรียงลำดับแบบรวดเร็ว);
* 3. การเรียงลำดับการเลือก (การเรียงลำดับโดยตรง, การเรียงลำดับฮีป); 4. การเรียงลำดับแบบรวม; 5. การเรียงลำดับ Radix
-
* เกี่ยวกับการเลือกวิธีการเรียงลำดับ: (1) หาก n มีขนาดเล็ก (เช่น n≤50) สามารถใช้การแทรกโดยตรงหรือการเรียงลำดับการเลือกโดยตรงได้
* เมื่อขนาดบันทึกมีขนาดเล็ก การเรียงลำดับการแทรกโดยตรงจะดีกว่า มิฉะนั้น เนื่องจากจำนวนบันทึกที่ย้ายโดยการเลือกโดยตรงน้อยกว่าการเรียงลำดับโดยตรง การเรียงลำดับโดยตรงจะดีกว่า
* (2) หากสถานะเริ่มต้นของไฟล์เป็นไปตามลำดับ (อ้างอิงถึงลำดับที่เป็นบวก) ควรใช้การแทรกโดยตรง บับเบิล หรือการเรียงลำดับอย่างรวดเร็วแบบสุ่ม
* (3) ถ้า n มีขนาดใหญ่ ควรใช้วิธีการเรียงลำดับที่มีความซับซ้อนเวลาเป็น O(nlgn): การเรียงลำดับแบบด่วน การเรียงลำดับฮีป หรือการเรียงลำดับแบบผสาน
-
-
คลาสสาธารณะเรียงลำดับ {
-
* วิธีการเริ่มต้นอาร์เรย์ทดสอบ
-
* @return อาร์เรย์เริ่มต้น
-
int สาธารณะ [] createArray () {
สุ่ม สุ่ม = สุ่มใหม่();
int[] array = ใหม่ int[10];
สำหรับ (int i = 0; i <10; i++) {
array[i] = Random.nextInt(100) - Random.nextInt(100); // สร้างตัวเลขสุ่มสองตัวแล้วลบออกเพื่อให้แน่ใจว่าตัวเลขที่สร้างขึ้นมีลบ
-
System.out.println("==========ลำดับเดิม==========");
printArray(อาร์เรย์);
ส่งคืนอาร์เรย์;
-
-
* พิมพ์องค์ประกอบในอาร์เรย์ไปยังคอนโซล
-
* @param แหล่งที่มา
-
โมฆะสาธารณะ printArray (ข้อมูล int []) {
สำหรับ (int i : ข้อมูล) {
System.out.print(i + " ");
-
System.out.println();
-
-
* แลกเปลี่ยนตำแหน่งของทั้งสององค์ประกอบที่ระบุในอาร์เรย์
-
* ข้อมูล @param
* @param x
* @param ย
-
การแลกเปลี่ยนโมฆะส่วนตัว (ข้อมูล int [], int x, int y) {
int temp = ข้อมูล [x];
ข้อมูล[x] = ข้อมูล[y];
ข้อมูล [y] = อุณหภูมิ;
-
-
* Bubble sort ---- ประเภทของการแลกเปลี่ยน
* วิธีการ: เปรียบเทียบองค์ประกอบสองรายการที่อยู่ติดกันและแลกเปลี่ยนหากจำเป็น หลังจากเสร็จสิ้นแต่ละรอบ องค์ประกอบที่ใหญ่ที่สุดจะถูกจัดอันดับเป็นอันดับสุดท้าย (เช่น การเรียงลำดับจากเล็กไปใหญ่)
* ประสิทธิภาพ: จำนวนการเปรียบเทียบ O(n^2),n^2/2; จำนวนการแลกเปลี่ยน O(n^2),n^2/4
-
* ข้อมูล @param
* อาร์เรย์ที่จะเรียงลำดับ
* @param sortType
* ประเภทการเรียงลำดับ
* @กลับ
-
โมฆะสาธารณะ bubbleSort (ข้อมูล int [], สตริง sortType) {
if (sortType.equals("asc")) { // การเรียงลำดับเชิงบวกจากเล็กไปใหญ่
// จำนวนรอบการเปรียบเทียบ
สำหรับ (int i = 1; i < data.length; i++) {
// เปรียบเทียบตัวเลขสองตัวที่อยู่ติดกัน แล้วตัวเลขที่มากกว่าจะเด้งขึ้นมา
สำหรับ (int j = 0; j < data.length - i; j++) {
ถ้า (ข้อมูล [j] > ข้อมูล [j + 1]) {
// สลับตัวเลขสองตัวที่อยู่ติดกัน
สลับ (ข้อมูล, j, j + 1);
-
-
-
} else if (sortType.equals("desc")) { // เรียงลำดับย้อนกลับจากใหญ่ไปเล็ก
// จำนวนรอบการเปรียบเทียบ
สำหรับ (int i = 1; i < data.length; i++) {
// เปรียบเทียบตัวเลขสองตัวที่อยู่ติดกัน แล้วตัวเลขที่มากกว่าจะเด้งขึ้นมา
สำหรับ (int j = 0; j < data.length - i; j++) {
ถ้า (ข้อมูล [j] < ข้อมูล [j + 1]) {
// สลับตัวเลขสองตัวที่อยู่ติดกัน
สลับ (ข้อมูล, j, j + 1);
-
-
-
} อื่น {
System.out.println("ประเภทการเรียงลำดับที่คุณป้อนไม่ถูกต้อง!");
-
printArray(data);//ส่งออกค่าอาร์เรย์หลังจากการเรียงลำดับแบบบับเบิล
-
-
* วิธีการเรียงลำดับการเลือกโดยตรง ---- ประเภทของการเรียงลำดับการเลือก
* วิธีการ: ในแต่ละรอบ องค์ประกอบที่เล็กที่สุด (หรือใหญ่ที่สุด) จะถูกเลือกจากองค์ประกอบข้อมูลที่จะจัดเรียง และลำดับจะถูกวางไว้ที่ส่วนท้ายของอาร์เรย์ที่เรียงลำดับจนกว่าองค์ประกอบข้อมูลทั้งหมดที่จะจัดเรียงจะถูกจัดเรียง
* ประสิทธิภาพ: จำนวนการเปรียบเทียบ O(n^2),n^2/2
* จำนวนการแลกเปลี่ยน O(n),n
* จำนวนการแลกเปลี่ยนน้อยกว่าการเรียงลำดับแบบฟองสบู่มาก เนื่องจากการแลกเปลี่ยนต้องใช้เวลา CPU มากกว่าการเปรียบเทียบ การเรียงลำดับแบบเลือกจึงเร็วกว่าการเรียงลำดับแบบฟอง
* แต่เมื่อ N ค่อนข้างมาก เวลา CPU ที่จำเป็นสำหรับการเปรียบเทียบจะมีอิทธิพลเหนือกว่า ดังนั้นประสิทธิภาพในเวลานี้จึงไม่แตกต่างจาก Bubble sort มากนัก แต่จะเร็วกว่าอย่างไม่ต้องสงสัย
-
* ข้อมูล @param
* อาร์เรย์ที่จะเรียงลำดับ
* @param sortType
* ประเภทการเรียงลำดับ
* @กลับ
-
-
โมฆะสาธารณะ selectSort (int [] ข้อมูล, สตริง sortType) {
if (sortType.equals("asc")) { // การเรียงลำดับเชิงบวกจากเล็กไปใหญ่
ดัชนี int;
สำหรับ (int i = 1; i < data.length; i++) {
ดัชนี = 0;
สำหรับ (int j = 1; j <= data.length - i; j++) {
ถ้า (ข้อมูล [j] > ข้อมูล [ดัชนี]) {
ดัชนี = เจ;
-
-
//แลกเปลี่ยนตัวเลขสองตัวที่ตำแหน่ง data.length-i และดัชนี (ค่าสูงสุด)
สลับ (ข้อมูล, data.length - i, ดัชนี);
-
} else if (sortType.equals("desc")) { // เรียงลำดับย้อนกลับจากใหญ่ไปเล็ก
ดัชนี int;
สำหรับ (int i = 1; i < data.length; i++) {
ดัชนี = 0;
สำหรับ (int j = 1; j <= data.length - i; j++) {
ถ้า (ข้อมูล [j] < ข้อมูล [ดัชนี]) {
ดัชนี = เจ;
-
-
//แลกเปลี่ยนตัวเลขสองตัวที่ตำแหน่ง data.length-i และดัชนี (ค่าสูงสุด)
สลับ (ข้อมูล, data.length - i, ดัชนี);
-
} อื่น {
System.out.println("ประเภทการเรียงลำดับที่คุณป้อนไม่ถูกต้อง!");
-
printArray(data);//ส่งออกค่าอาร์เรย์หลังจากการเรียงลำดับการเลือกโดยตรง
-
-
-
* การเรียงลำดับการแทรก
-
* วิธีการ: แทรกบันทึกลงในรายการเรียงลำดับ (อาจเป็นรายการว่าง) เพื่อให้ได้รายการเรียงลำดับใหม่โดยมีจำนวนบันทึกเพิ่มขึ้น 1
* ประสิทธิภาพ: จำนวนการเปรียบเทียบ O(n^2),n^2/4
* จำนวนสำเนา O(n),n^2/4
* จำนวนการเปรียบเทียบเป็นค่าเฉลี่ยระหว่างสองรายการแรก และการคัดลอกต้องใช้เวลา CPU น้อยกว่าการสลับ ดังนั้นประสิทธิภาพจึงมากกว่าสองเท่าของการเรียงลำดับแบบฟองและเร็วกว่าการเรียงลำดับแบบเลือก
-
* ข้อมูล @param
* อาร์เรย์ที่จะเรียงลำดับ
* @param sortType
* ประเภทการเรียงลำดับ
-
โมฆะสาธารณะ insertSort (int [] ข้อมูล String sortType) {
if (sortType.equals("asc")) { // การเรียงลำดับเชิงบวกจากเล็กไปใหญ่
// จำนวนรอบการเปรียบเทียบ
สำหรับ (int i = 1; i < data.length; i++) {
// ตรวจสอบให้แน่ใจว่าได้เรียงลำดับหมายเลข i+1 แรกแล้ว
สำหรับ (int j = 0; j < i; j ++) {
ถ้า (ข้อมูล [j] > ข้อมูล [i]) {
// สลับตัวเลขสองตัวที่ตำแหน่ง j และ i
สลับ (ข้อมูล, i, j);
-
-
-
} else if (sortType.equals("desc")) { // เรียงลำดับย้อนกลับจากใหญ่ไปเล็ก
// จำนวนรอบการเปรียบเทียบ
สำหรับ (int i = 1; i < data.length; i++) {
// ตรวจสอบให้แน่ใจว่าได้เรียงลำดับหมายเลข i+1 แรกแล้ว
สำหรับ (int j = 0; j < i; j ++) {
ถ้า (ข้อมูล [j] < ข้อมูล [i]) {
// สลับตัวเลขสองตัวที่ตำแหน่ง j และ i
สลับ (ข้อมูล, i, j);
-
-
-
} อื่น {
System.out.println("ประเภทการเรียงลำดับที่คุณป้อนไม่ถูกต้อง!");
-
printArray(data);//ส่งออกค่าอาร์เรย์หลังจากการเรียงลำดับการแทรก
-
-
-
* วิธีการกลับอาร์เรย์
-
* ข้อมูล @param
* อาร์เรย์แหล่งที่มา
-
โมฆะสาธารณะย้อนกลับ (ข้อมูล int []) {
ความยาว int = data.length;
int temp = 0;//ตัวแปรชั่วคราว
สำหรับ (int i = 0; i <ความยาว / 2; i++) {
อุณหภูมิ = ข้อมูล [i];
ข้อมูล [i] = ข้อมูล [ความยาว - 1 - i];
ข้อมูล [ความยาว - 1 - i] = อุณหภูมิ;
-
printArray(data);//ส่งออกค่าไปยังอาร์เรย์ที่แปลงแล้ว
-
-
-
* เรียงลำดับด่วน
-
* การเรียงลำดับอย่างรวดเร็วใช้กลยุทธ์การแบ่งและพิชิตเพื่อแบ่งลำดับ (รายการ) ออกเป็นสองลำดับย่อย (รายการย่อย)
-
*ขั้นตอนคือ:
* 1. เลือกองค์ประกอบจากลำดับที่เรียกว่า "pivot"
* 2. จัดลำดับใหม่เพื่อให้องค์ประกอบทั้งหมดที่มีขนาดเล็กกว่าค่าฐานถูกวางไว้ด้านหน้าฐาน และองค์ประกอบทั้งหมดที่ใหญ่กว่าค่าฐานจะถูกวางไว้ด้านหลังฐาน (สามารถวางหมายเลขเดียวกันไว้ที่ด้านใดด้านหนึ่งได้) หลังจากการแยกนี้ ข้อมูลจะอยู่ในตำแหน่งสุดท้าย สิ่งนี้เรียกว่าการดำเนินการพาร์ติชัน
* 3. เรียงลำดับอาร์เรย์ย่อยขององค์ประกอบที่เล็กกว่าค่าฐานและอาร์เรย์ย่อยขององค์ประกอบที่มากกว่าค่าฐานแบบวนซ้ำ
-
* กรณีด้านล่างของการเรียกซ้ำคือเมื่อขนาดของอาร์เรย์เป็นศูนย์หรือหนึ่ง นั่นคือ จะมีการเรียงลำดับอยู่เสมอ แม้ว่ามันจะเกิดซ้ำไปเรื่อยๆ แต่อัลกอริธึมนี้จะสิ้นสุดเสมอ เพราะในการวนซ้ำแต่ละครั้ง (การวนซ้ำ) มันจะย้ายอย่างน้อยหนึ่งองค์ประกอบไปยังตำแหน่งสุดท้าย
-
* ข้อมูล @param
* อาร์เรย์ที่จะเรียงลำดับ
* @param ต่ำ
* @param สูง
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
-
-
โมฆะสาธารณะ QuickSort (int [] ข้อมูล String sortType) {
if (sortType.equals("asc")) { // การเรียงลำดับเชิงบวกจากเล็กไปใหญ่
qsort_asc(ข้อมูล, 0, data.length - 1);
} else if (sortType.equals("desc")) { // เรียงลำดับย้อนกลับจากใหญ่ไปเล็ก
qsort_desc(ข้อมูล, 0, data.length - 1);
} อื่น {
System.out.println("ประเภทการเรียงลำดับที่คุณป้อนไม่ถูกต้อง!");
-
-
-
-
* การใช้งานเฉพาะของการเรียงลำดับอย่างรวดเร็วการเรียงลำดับที่ถูกต้อง
-
* ข้อมูล @param
* @param ต่ำ
* @param สูง
-
โมฆะส่วนตัว qsort_asc (int data [], int ต่ำ, int สูง) {
ฉัน, เจ, x;
if (low < high) { // เงื่อนไขนี้ใช้เพื่อสิ้นสุดการเรียกซ้ำ
ฉัน = ต่ำ;
เจ = สูง;
x = ข้อมูล [i];
ในขณะที่ (ฉัน <เจ) {
ในขณะที่ (i < j && data[j] > x) {
j--; // ค้นหาตัวเลขตัวแรกที่น้อยกว่า x จากขวาไปซ้าย
-
ถ้า (ฉัน <เจ) {
ข้อมูล [i] = ข้อมูล [j];
ฉัน++;
-
ในขณะที่ (i < j && data[i] < x) {
i++; ค้นหาจำนวนแรกที่มากกว่า x จากซ้ายไปขวา
-
ถ้า (ฉัน <เจ) {
ข้อมูล[j] = ข้อมูล[i];
เจ--;
-
-
ข้อมูล[i] = x;
qsort_asc(ข้อมูล, ต่ำ, i - 1);
qsort_asc (ข้อมูล, i + 1, สูง);
-
-
-
-
* การใช้งานการเรียงลำดับแบบด่วนโดยเฉพาะ เรียงลำดับแบบย้อนกลับ
-
* ข้อมูล @param
* @param ต่ำ
* @param สูง
-
-
โมฆะส่วนตัว qsort_desc (int data [], int ต่ำ, int สูง) {
ฉัน, เจ, x;
if (low < high) { // เงื่อนไขนี้ใช้เพื่อสิ้นสุดการเรียกซ้ำ
ฉัน = ต่ำ;
เจ = สูง;
x = ข้อมูล [i];
ในขณะที่ (ฉัน <เจ) {
ในขณะที่ (i < j && data[j] < x) {
j--; // ค้นหาตัวเลขตัวแรกที่น้อยกว่า x จากขวาไปซ้าย
-
ถ้า (ฉัน <เจ) {
ข้อมูล [i] = ข้อมูล [j];
ฉัน++;
-
ในขณะที่ (i < j && data[i] > x) {
i++; ค้นหาจำนวนแรกที่มากกว่า x จากซ้ายไปขวา
-
ถ้า (ฉัน <เจ) {
ข้อมูล[j] = ข้อมูล[i];
เจ--;
-
-
ข้อมูล[i] = x;
qsort_desc(ข้อมูล, ต่ำ, i - 1);
qsort_desc(ข้อมูล, i + 1, สูง);
-
-
-
-
* การค้นหาไบนารีสำหรับตำแหน่งของจำนวนเต็มเฉพาะในอาร์เรย์จำนวนเต็ม (เรียกซ้ำ)
-
* ค้นหารายการเชิงเส้นต้องเป็นรายการเรียงลำดับ
-
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
-
-
สาธารณะ int binarySearch (ชุดข้อมูล int [], ข้อมูล int, int beginningIndex, int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // เทียบเท่ากับ mid = (ต่ำ + สูง)
// / 2 แต่ประสิทธิภาพจะสูงขึ้น
ถ้า (ข้อมูล < ชุดข้อมูล [beginIndex] || ข้อมูล > ชุดข้อมูล [endIndex] || beginningIndex > endIndex)
กลับ -1;
ถ้า (ข้อมูล <ชุดข้อมูล [midIndex]) {
กลับ binarySearch (ชุดข้อมูล, ข้อมูล, beginningIndex, midIndex - 1);
} อื่น ๆ ถ้า (ข้อมูล > ชุดข้อมูล [midIndex]) {
ส่งคืน binarySearch (ชุดข้อมูล, ข้อมูล, midIndex + 1, endIndex);
} อื่น {
กลับ midIndex;
-
-
-
-
* การค้นหาไบนารีสำหรับตำแหน่งของจำนวนเต็มเฉพาะในอาร์เรย์จำนวนเต็ม (ไม่เรียกซ้ำ)
-
* ค้นหารายการเชิงเส้นต้องเป็นรายการเรียงลำดับ
-
* @paramdataset
* @paramdata
* @returnindex
-
-
int binarySearch สาธารณะ (ชุดข้อมูล int [], ข้อมูล int) {
int startIndex = 0;
int endIndex = ชุดข้อมูล ความยาว - 1;
int midIndex = -1;
ถ้า (ข้อมูล < ชุดข้อมูล [beginIndex] || ข้อมูล > ชุดข้อมูล [endIndex] || beginningIndex > endIndex)
กลับ -1;
ในขณะที่ (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // เทียบเท่ากับ midIndex =
// (beginIndex +
// endIndex) / 2 แต่ประสิทธิภาพจะสูงขึ้น
ถ้า (ข้อมูล <ชุดข้อมูล [midIndex]) {
endIndex = ดัชนีกลาง - 1;
} อื่น ๆ ถ้า (ข้อมูล > ชุดข้อมูล [midIndex]) {
BeginIndex = ดัชนีกลาง + 1;
} อื่น {
กลับ midIndex;
-
-
กลับ -1;
-
โมฆะสาธารณะคงหลัก (สตริง [] args) {
เรียงลำดับ sortTest = เรียงลำดับใหม่();
int[] array = sortTest.createArray();
System.out.println("==========หลังจากการเรียงลำดับฟอง (ลำดับที่เป็นบวก)==========");
sortTest.bubbleSort(อาร์เรย์, "asc");
System.out.println("==========หลังจากการเรียงลำดับฟอง (ลำดับย้อนกลับ)==========");
sortTest.bubbleSort(อาร์เรย์, "คำอธิบาย");
อาร์เรย์ = sortTest.createArray();
System.out.println("==========หลังจากย้อนกลับอาร์เรย์==========");
sortTest.reverse (อาร์เรย์);
อาร์เรย์ = sortTest.createArray();
System.out.println("==========หลังจากการเรียงลำดับการเลือก (ลำดับที่เป็นบวก)==========");
sortTest.selectSort(อาร์เรย์, "asc");
System.out.println("==========หลังจากการเรียงลำดับการเลือก (ลำดับย้อนกลับ)==========");
sortTest.selectSort(อาร์เรย์, "คำอธิบาย");
อาร์เรย์ = sortTest.createArray();
System.out.println("==========หลังจากการเรียงลำดับการแทรก (ลำดับที่เป็นบวก)==========");
sortTest.insertSort(อาร์เรย์, "asc");
System.out.println("==========หลังจากการเรียงลำดับการแทรก (ลำดับย้อนกลับ)==========");
sortTest.insertSort(อาร์เรย์, "คำอธิบาย");
อาร์เรย์ = sortTest.createArray();
System.out.println("==========หลังจากการเรียงลำดับอย่างรวดเร็ว (ลำดับที่เป็นบวก)==========");
sortTest.quickSort(อาร์เรย์, "asc");
sortTest.printArray(อาร์เรย์);
System.out.println("==========หลังจากการเรียงลำดับอย่างรวดเร็ว (ลำดับย้อนกลับ)==========");
sortTest.quickSort(อาร์เรย์, "คำอธิบาย");
sortTest.printArray(อาร์เรย์);
System.out.println("==========การค้นหาแบบไบนารีในอาร์เรย์==========");
System.out.println("หมายเลขที่คุณกำลังมองหาอยู่ที่" + sortTest.binarySearch(array, 74)
+ "ที่นั่ง (ตัวห้อยคำนวณจาก 0)");
-
-