ความมั่นคง (ความมั่นคง)
อัลกอริธึมการเรียงลำดับมีความเสถียร นั่นคือเมื่อมีคีย์ R และ S สองบันทึกที่เท่ากัน และ R ปรากฏก่อน S ในรายการดั้งเดิม R จะปรากฏขึ้นก่อน S ในรายการเรียงลำดับด้วย
การจำแนกประเภทอัลกอริทึมการเรียงลำดับ
สิ่งทั่วไป ได้แก่ การแทรก (การเรียงลำดับการแทรก/การเรียงลำดับฮิลล์) การแลกเปลี่ยน (การเรียงลำดับแบบบับเบิ้ล/การเรียงลำดับแบบด่วน) การเลือก (การเรียงลำดับการเลือก) การผสาน (การเรียงลำดับแบบผสาน) เป็นต้น
1. การเรียงลำดับการแทรก
การเรียงลำดับการแทรก (Insertion Sort) ทำงานโดยการสร้างลำดับการเรียงลำดับ สำหรับข้อมูลที่ไม่มีการเรียงลำดับ ระบบจะสแกนจากหลังไปหน้าในลำดับการจัดเรียงเพื่อค้นหาตำแหน่งที่เกี่ยวข้องแล้วแทรกลงไป ในการใช้งานการเรียงลำดับการแทรก โดยปกติจะใช้การเรียงลำดับแบบแทนที่ (นั่นคือ การเรียงลำดับที่ใช้พื้นที่พิเศษ O(1) เท่านั้น) ดังนั้นในระหว่างกระบวนการสแกนจากด้านหลังไปด้านหน้า จำเป็นต้องทำซ้ำและค่อยๆ เลื่อน จัดเรียงองค์ประกอบไปข้างหลัง โดยให้พื้นที่แทรกสำหรับองค์ประกอบล่าสุด
โดยทั่วไปแล้ว การเรียงลำดับการแทรกจะถูกนำไปใช้กับอาร์เรย์โดยใช้แบบแทนที่ อัลกอริธึมเฉพาะอธิบายไว้ดังนี้:
เริ่มต้นจากองค์ประกอบแรก องค์ประกอบสามารถพิจารณาได้ว่ามีการจัดเรียงแล้ว
รับองค์ประกอบถัดไปและสแกนจากหลังไปด้านหน้าตามลำดับองค์ประกอบ
หากองค์ประกอบ (จัดเรียง) มีขนาดใหญ่กว่าองค์ประกอบใหม่ ให้ย้ายองค์ประกอบไปยังตำแหน่งถัดไป
ทำซ้ำขั้นตอนที่ 3 จนกว่าคุณจะพบตำแหน่งที่องค์ประกอบที่เรียงลำดับน้อยกว่าหรือเท่ากับองค์ประกอบใหม่
หลังจากใส่องค์ประกอบใหม่ในตำแหน่งนั้นแล้ว
ทำซ้ำขั้นตอนที่ 2~5
คัดลอกรหัสรหัส ดังต่อไปนี้:
โมฆะสาธารณะคงที่ insertionSort (ข้อมูล int []) {
สำหรับ (ดัชนี int = 1; ดัชนี < data.length; ดัชนี ++) {
คีย์ int = ข้อมูล [ดัชนี];
ตำแหน่ง int = ดัชนี;
// เลื่อนค่าที่มากขึ้นไปทางขวา
ในขณะที่ (ตำแหน่ง > 0 && ข้อมูล [ตำแหน่ง - 1] > คีย์) {
ข้อมูล [ตำแหน่ง] = ข้อมูล [ตำแหน่ง - 1];
ตำแหน่ง--;
-
ข้อมูล [ตำแหน่ง] = คีย์;
-
-
2. การคัดแยกเนินเขา
Shell Sort เป็นการเรียงลำดับการแทรกประเภทหนึ่ง เป็นการปรับปรุงอัลกอริธึมการเรียงลำดับการแทรกโดยตรง วิธีการนี้เรียกอีกอย่างว่าการลดการเรียงลำดับแบบเพิ่มหน่วยเนื่องจาก DL เชลล์ได้รับการตั้งชื่อตามที่ได้รับการเสนอในปี พ.ศ. 2502
การเรียงลำดับแบบ Hill เสนอวิธีการที่ได้รับการปรับปรุงตามคุณสมบัติสองประการของการเรียงลำดับแบบแทรกต่อไปนี้:
การเรียงลำดับการแทรกจะมีประสิทธิภาพสูงเมื่อทำงานกับข้อมูลที่เกือบจะเรียงลำดับ กล่าวคือ สามารถบรรลุประสิทธิภาพของการเรียงลำดับเชิงเส้นได้
แต่โดยทั่วไปการเรียงลำดับการแทรกจะไม่มีประสิทธิภาพเนื่องจากการเรียงลำดับการแทรกสามารถย้ายข้อมูลได้ครั้งละหนึ่งบิตเท่านั้น
คัดลอกรหัสรหัส ดังต่อไปนี้:
คงที่ <E ขยายการเปรียบเทียบ <? super E>> เป็นโมฆะ shellSort (รายการ <E> a) {
inth = 1;
ในขณะที่ (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) โดย Knuth,1973>: 1, 4, 13, 40, 121, . ..
สำหรับ (; ชั่วโมง >= 1; ชั่วโมง /= 3)
สำหรับ (int i = h; i <a.size(); i++)
สำหรับ (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
-
3. การเรียงลำดับฟอง
Bubble Sort (Bubble Sort แปลจากไต้หวันว่า Bubble Sort หรือ Bubble Sort) เป็นอัลกอริธึมการเรียงลำดับอย่างง่าย โดยจะดำเนินตามลำดับเพื่อจัดเรียงซ้ำๆ โดยเปรียบเทียบสององค์ประกอบในแต่ละครั้ง และสลับองค์ประกอบเหล่านั้นหากอยู่ในลำดับที่ไม่ถูกต้อง งานการเยี่ยมชมอาร์เรย์จะถูกทำซ้ำจนกว่าจะไม่จำเป็นต้องมีการแลกเปลี่ยนอีกต่อไป ซึ่งหมายความว่าอาร์เรย์ได้รับการจัดเรียงแล้ว ชื่อของอัลกอริธึมนี้มาจากความจริงที่ว่าองค์ประกอบที่มีขนาดเล็กกว่าจะค่อยๆ "ลอย" ไปที่ด้านบนของอาร์เรย์ผ่านการสลับ
อัลกอริธึมการเรียงลำดับแบบบับเบิ้ลทำงานดังนี้:
เปรียบเทียบองค์ประกอบที่อยู่ติดกัน และหากองค์ประกอบแรกมากกว่าองค์ประกอบที่สอง ให้สลับทั้งสององค์ประกอบ
ทำเช่นเดียวกันกับองค์ประกอบที่อยู่ติดกันแต่ละคู่ โดยเริ่มจากคู่แรกและลงท้ายด้วยคู่สุดท้าย ซึ่งจุดนี้องค์ประกอบสุดท้ายควรเป็นตัวเลขที่มากที่สุด
ทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบทั้งหมด ยกเว้นองค์ประกอบสุดท้าย
ทำซ้ำขั้นตอนข้างต้นต่อไปเพื่อให้องค์ประกอบน้อยลงในแต่ละครั้งจนกว่าจะไม่มีตัวเลขเหลือให้เปรียบเทียบ
คัดลอกรหัสรหัส ดังต่อไปนี้:
โมฆะสาธารณะแบบคงที่ bubbleSort (ข้อมูล int []) {
อุณหภูมิภายใน = 0;
สำหรับ (int i = data.length - 1; i > 0; --i) {
บูลีน isSort = เท็จ;
สำหรับ (int j = 0; j < i; ++ j) {
ถ้า (ข้อมูล [j + 1] < ข้อมูล [j]) {
อุณหภูมิ = ข้อมูล [j];
ข้อมูล[เจ] = ข้อมูล[เจ + 1];
ข้อมูล [j + 1] = อุณหภูมิ;
isSort = จริง;
-
-
// หากมีการแลกเปลี่ยนเกิดขึ้นในวงใน ให้ทำการเปรียบเทียบต่อไป หากไม่มีการแลกเปลี่ยนเกิดขึ้นในวงใน จะถือว่ามีการเรียงลำดับแล้ว
ถ้า (!isSort)
หยุดพัก;
-
-
4. การเรียงลำดับอย่างรวดเร็ว
Quicksort เป็นการปรับปรุงการเรียงลำดับแบบฟอง เสนอโดย CAR Hoare ในปี พ.ศ. 2505 แนวคิดพื้นฐานคือการแบ่งข้อมูลที่จะจัดเรียงออกเป็นสองส่วนแยกกันผ่านการเรียงลำดับเดียว ข้อมูลทั้งหมดในส่วนหนึ่งมีขนาดเล็กกว่าข้อมูลทั้งหมดในอีกส่วนหนึ่ง จากนั้นใช้วิธีนี้เพื่อแยกข้อมูลทั้งสองส่วนอย่างรวดเร็ว การเรียงลำดับ กระบวนการเรียงลำดับทั้งหมดสามารถดำเนินการซ้ำได้ เพื่อให้ข้อมูลทั้งหมดกลายเป็นลำดับ
การเรียงลำดับอย่างรวดเร็วใช้กลยุทธ์การแบ่งและพิชิตเพื่อแบ่งรายการออกเป็นสองรายการย่อย
ขั้นตอนคือ:
การเลือกองค์ประกอบจากลำดับเรียกว่า "เดือย"
จัดลำดับอาร์เรย์ใหม่เพื่อให้องค์ประกอบทั้งหมดที่เล็กกว่าค่าฐานถูกวางไว้ด้านหน้าฐาน และองค์ประกอบทั้งหมดที่ใหญ่กว่าค่าฐานจะถูกวางไว้ด้านหลังฐาน (หมายเลขเดียวกันสามารถไปด้านใดด้านหนึ่งได้) หลังจากออกจากพาร์ติชันนี้ ฐานจะอยู่ตรงกลางของลำดับ สิ่งนี้เรียกว่าการดำเนินการพาร์ติชัน
เรียงลำดับอาร์เรย์ย่อยขององค์ประกอบที่น้อยกว่าค่าฐานและอาร์เรย์ย่อยขององค์ประกอบที่มากกว่าค่าฐานซ้ำๆ
คัดลอกรหัสรหัส ดังต่อไปนี้:
-
* การใช้งานที่มีประสิทธิภาพมากขึ้นสำหรับการเรียงลำดับอย่างรวดเร็ว <br />
* ใช้ค่ามัธยฐานด้านซ้าย ตรงกลาง และด้านขวา (@see #median()) สำหรับเดือย และ
* วงในที่มีประสิทธิภาพมากขึ้นสำหรับแกนหลักของอัลกอริทึม
-
Quicksort คลาสสาธารณะ {
int สุดท้ายคงสาธารณะ CUTOFF = 11;
-
* อัลกอริธึมการเรียงลำดับอย่างรวดเร็ว <br />
-
* @param เป็นอาร์เรย์ของรายการเปรียบเทียบ <br />
-
สาธารณะคงที่ <T ขยายการเปรียบเทียบ <? super T>> เป็นโมฆะ Quicksort (T [] arr) {
QuickSort(arr, 0, arr.length - 1);
-
-
* รับค่ามัธยฐานด้านซ้าย ตรงกลาง และด้านขวา <br />
* สั่งซื้อสิ่งเหล่านี้และซ่อนเดือยโดยวางไว้ที่ส่วนท้ายของอาร์เรย์ <br />
-
* @param เป็นอาร์เรย์ของรายการเปรียบเทียบ <br />
* @param ออกจากดัชนีด้านซ้ายสุดของอาร์เรย์ย่อย <br />
* @param ขวาดัชนีขวาสุดของอาร์เรย์ย่อย<br />
* @return ต
-
สาธารณะคงที่ <T ขยายการเปรียบเทียบ <? super T>> T ค่ามัธยฐาน (T [] arr, int ซ้าย, int ขวา) {
int center = (ซ้าย + ขวา) / 2;
ถ้า (arr[ซ้าย].compareTo(arr[center]) > 0)
swapRef(arr, ซ้าย, กลาง);
ถ้า (arr[ซ้าย].compareTo(arr[ขวา]) > 0)
swapRef(arr, ซ้าย, ขวา);
ถ้า (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, กลาง, ขวา);
swapRef(arr, กลาง, ขวา - 1);
กลับ arr [ขวา - 1];
-
-
* วิธีการภายในเพื่อเรียงลำดับอาร์เรย์ด้วยอัลกอริธึมการเรียงลำดับอย่างรวดเร็ว <br />
-
* @param เป็นอาร์เรย์ของรายการเปรียบเทียบ <br />
* @param ออกจากดัชนีซ้ายสุดของอาร์เรย์ย่อย <br />
* @param อยู่ทางขวาสุดของอาร์เรย์ย่อย <br />
-
ส่วนตัวคงที่ <T ขยายการเปรียบเทียบ <? super T>> เป็นโมฆะ QuickSort (T [] arr, int ซ้าย, int ขวา) {
ถ้า (ซ้าย + ตัด <= ขวา) {
// ค้นหาเดือย
T pivot = ค่ามัธยฐาน(arr, ซ้าย, ขวา);
// เริ่มการแบ่งพาร์ติชั่น
int i = ซ้าย, j = ขวา - 1;
สำหรับ (;;) {
ในขณะที่ (arr[++i].compareTo(pivot) < 0);
ในขณะที่ (arr[--j].compareTo(pivot) > 0);
ถ้า (ฉัน <เจ)
swapRef(arr, i, j);
อื่น
หยุดพัก;
-
// สลับการอ้างอิงเดือยกลับไปยังคอลเลกชันขนาดเล็ก
swapRef(arr, i, ขวา - 1);
QuickSort(arr, ซ้าย, i - 1); // เรียงลำดับคอลเลกชันขนาดเล็ก
QuickSort(arr, i + 1, ขวา); // เรียงลำดับคอลเลกชันขนาดใหญ่.
} อื่น {
// หากจำนวนรวมน้อยกว่า CUTOFF เราจะใช้การเรียงลำดับการแทรก
// แทน (เพราะมีประสิทธิภาพมากกว่ามาก)
เรียงลำดับ(arr, การแทรก ซ้าย, ขวา);
-
-
-
* วิธีการสลับการอ้างอิงในอาร์เรย์<br />
-
* @param เป็นอาร์เรย์ของ Objects
* @param idx1 ดัชนีขององค์ประกอบแรก <br />
* @param idx2 ดัชนีขององค์ประกอบที่สอง <br />
-
สาธารณะคงที่ <T> เป็นโมฆะ swapRef (T [] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
-
-
* วิธีการเรียงลำดับอาร์เรย์ย่อยตั้งแต่ต้นจนจบด้วยการเรียงลำดับการแทรก
* อัลกอริทึม <br />
-
* @param เป็นอาร์เรย์ของรายการเปรียบเทียบ <br />
* @param เริ่มต้นตำแหน่งเริ่มต้น <br />
* @param สิ้นสุดตำแหน่งสิ้นสุด <br />
-
สาธารณะคงที่ <T ขยายการเปรียบเทียบ <? super T>> void insertionSort (T [] arr, int start, int end) {
ฉัน;
สำหรับ (int j = เริ่มต้น + 1; j <= สิ้นสุด; j ++) {
T tmp = arr[j];
สำหรับ (i = j; i > เริ่มต้น && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
-
arr[i] = tmp;
-
-
โมฆะคงที่ส่วนตัว printArray (จำนวนเต็ม [] c) {
สำหรับ (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
-
โมฆะคงที่สาธารณะ main (String [] args) {
ข้อมูลจำนวนเต็ม [] = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(ข้อมูล);
การเรียงลำดับอย่างรวดเร็ว (ข้อมูล);
printArray(ข้อมูล);
-
-
5. การเรียงลำดับการเลือก
การเรียงลำดับการเลือกเป็นอัลกอริธึมการเรียงลำดับที่เรียบง่ายและใช้งานง่าย นี่คือวิธีการทำงาน ขั้นแรก ค้นหาองค์ประกอบที่เล็กที่สุด (ใหญ่) ในลำดับที่ไม่ได้เรียงลำดับ และเก็บไว้ที่จุดเริ่มต้นของลำดับการเรียงลำดับ จากนั้น ค้นหาองค์ประกอบที่เล็กที่สุด (ใหญ่) จากองค์ประกอบที่ไม่ได้เรียงลำดับที่เหลือ จากนั้นจึงวางไว้ที่ส่วนท้ายของลำดับ ลำดับการจัดเรียง และต่อไปเรื่อยๆ จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง
เนื่องจากแต่ละขั้นตอนในการกำหนดองค์ประกอบจะมีกระบวนการย่อยในการเลือกค่าต่ำสุด ผู้คนจึงเรียกสิ่งนี้ว่าการเรียงลำดับการเลือกอย่างชัดเจน
ตัวอย่างเช่น ในลำดับ 5 8 5 2 9 เรารู้ว่าองค์ประกอบแรก 5 จะถูกแลกเปลี่ยนกับ 2 ในลำดับแรก จากนั้นลำดับสัมพัทธ์ของ 5 สองตัวในลำดับดั้งเดิมจะถูกทำลาย ดังนั้นการเรียงลำดับการเลือกจึงเป็นเช่นนั้น อัลกอริธึมการเรียงลำดับไม่เสถียร
คัดลอกรหัสรหัส ดังต่อไปนี้:
โมฆะคงสาธารณะ selectSort (ข้อมูล int []) {
int minIndex = 0;
อุณหภูมิภายใน = 0;
สำหรับ (int i = 0; i < data.length; i++) {
minIndex = i; //ดัชนีอาร์เรย์ข้อมูลขั้นต่ำของพื้นที่ที่ไม่ได้เรียงลำดับ
for (int j = i + 1; j < data.length; j++) { // ค้นหาข้อมูลที่เล็กที่สุดในพื้นที่ที่ไม่เรียงลำดับและบันทึกตัวห้อยอาร์เรย์
ถ้า (ข้อมูล [j] < ข้อมูล [minIndex]) {
minIndex = เจ;
-
-
if (minIndex != i) { // หากตำแหน่งขั้นต่ำของพื้นที่ที่ไม่ได้เรียงลำดับไม่ใช่ข้อมูลแรกเริ่มต้น ให้แลกเปลี่ยน
อุณหภูมิ = ข้อมูล [i];
ข้อมูล [i] = ข้อมูล [minIndex];
ข้อมูล [minIndex] = อุณหภูมิ;
-
-
-
6. ผสานการเรียงลำดับ
การเรียงลำดับแบบผสานเป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพตามการดำเนินการผสาน อัลกอริธึมนี้เป็นแอปพลิเคชันทั่วไปที่ใช้วิธีแบ่งและพิชิต (Divide and Conquer)
กระบวนการดำเนินการรวมมีดังนี้:
ใช้สำหรับช่องว่างเพื่อให้ขนาดของมันเป็นผลรวมของลำดับที่เรียงลำดับทั้งสอง
ตั้งค่าพอยน์เตอร์สองตัว ตำแหน่งเริ่มต้นคือตำแหน่งเริ่มต้นของลำดับที่เรียงลำดับทั้งสอง
เปรียบเทียบองค์ประกอบที่พอยน์เตอร์ทั้งสองชี้ไป เลือกองค์ประกอบที่มีขนาดค่อนข้างเล็กแล้ววางลงในพื้นที่ผสาน จากนั้นย้ายพอยน์เตอร์ไปยังตำแหน่งถัดไป
ทำซ้ำขั้นตอนที่ 3 จนกระทั่งตัวชี้ไปถึงจุดสิ้นสุดของลำดับ
คัดลอกองค์ประกอบที่เหลือทั้งหมดของลำดับอื่นไปยังจุดสิ้นสุดของลำดับที่ผสานโดยตรง
คัดลอกรหัสรหัส ดังต่อไปนี้:
int แบบคงที่สาธารณะ [] mergeSort (int [] arr) {// ผสานการเรียงลำดับ - การเรียกซ้ำ
ถ้า (ความยาว arr. == 1) {
กลับถึง;
-
int half = arr.length / 2;
int[] arr1 = ใหม่ int[ครึ่ง];
int[] arr2 = int ใหม่[arr.length - ครึ่ง];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, ครึ่ง, arr2, 0, arr2.length);
arr1 = MergeSort(arr1);
arr2 = MergeSort(arr2);
กลับ mergeSortSub (arr1, arr2);
-
int คงที่ส่วนตัว [] mergeSortSub (int [] arr1, int [] arr2) {// รวมรูทีนย่อยการเรียงลำดับ
int[] result = new int[arr1.length + arr2.length];
int i = 0;
อินท์เจ = 0;
int k = 0;
ในขณะที่ (จริง) {
ถ้า (arr1[i] < arr2[j]) {
ผลลัพธ์[k] = arr1[i];
ถ้า (++ i > arr1.length - 1) {
หยุดพัก;
-
} อื่น {
ผลลัพธ์[k] = arr2[j];
ถ้า (++ j > arr2.length - 1) {
หยุดพัก;
-
-
เค++;
-
สำหรับ (; i < arr1.length; i++) {
ผลลัพธ์[++k] = arr1[i];
-
สำหรับ (; j < arr2.length; j++) {
ผลลัพธ์[++k] = arr2[j];
-
ส่งคืนผลลัพธ์;
-
รหัสที่สมบูรณ์ (ยกเว้น QuickSort)
คัดลอกรหัสรหัส ดังต่อไปนี้:
แพ็คเกจ com.clzhang.sample.thinking;
นำเข้า java.util.*;
-
* การใช้งาน Java ของอัลกอริธึมการเรียงลำดับทั่วไปหลายอย่าง
* @ผู้เขียน acer
-
-
CommonSort ระดับสาธารณะ {
-
* อัลกอริธึมเฉพาะของการเรียงลำดับการแทรกมีคำอธิบายดังนี้:
* 1. เริ่มต้นจากองค์ประกอบแรก ถือว่าองค์ประกอบได้รับการจัดเรียงแล้ว
* 2. นำองค์ประกอบถัดไปออกมาและสแกนจากหลังไปด้านหน้าตามลำดับองค์ประกอบที่จัดเรียง
* 3. หากองค์ประกอบ (เรียงลำดับ) มีขนาดใหญ่กว่าองค์ประกอบใหม่ ให้ย้ายองค์ประกอบไปยังตำแหน่งถัดไป
* 4. ทำซ้ำขั้นตอนที่ 3 จนกว่าคุณจะพบตำแหน่งที่องค์ประกอบที่เรียงลำดับน้อยกว่าหรือเท่ากับองค์ประกอบใหม่
* 5. หลังจากใส่องค์ประกอบใหม่ลงในตำแหน่งนี้แล้ว
* 6. ทำซ้ำขั้นตอนที่ 2~5
-
โมฆะสาธารณะคงที่ insertionSort (ข้อมูล int []) {
สำหรับ (ดัชนี int = 1; ดัชนี < data.length; ดัชนี ++) {
คีย์ int = ข้อมูล [ดัชนี];
ตำแหน่ง int = ดัชนี;
// เลื่อนค่าที่มากขึ้นไปทางขวา
ในขณะที่ (ตำแหน่ง > 0 && ข้อมูล [ตำแหน่ง - 1] > คีย์) {
ข้อมูล [ตำแหน่ง] = ข้อมูล [ตำแหน่ง - 1];
ตำแหน่ง--;
-
ข้อมูล [ตำแหน่ง] = คีย์;
-
-
-
* การเรียงลำดับฮิลล์ โปรดดูที่ Wikipedia สำหรับแนวคิดการนำอัลกอริทึมไปใช้ เหมาะสำหรับการดำเนินการเรียงลำดับจำนวนมาก
-
คงที่ <E ขยายการเปรียบเทียบ <? super E>> เป็นโมฆะ shellSort (รายการ <E> a) {
inth = 1;
ในขณะที่ (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) โดย Knuth,1973>: 1, 4, 13, 40, 121, . ..
สำหรับ (; ชั่วโมง >= 1; ชั่วโมง /= 3)
สำหรับ (int i = h; i <a.size(); i++)
สำหรับ (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
-
-
* การทำงานของอัลกอริธึมการเรียงลำดับฟองมีดังนี้:
* 1. เปรียบเทียบองค์ประกอบที่อยู่ติดกัน หากอันแรกใหญ่กว่าอันที่สอง ให้สลับทั้งสองอัน
* 2. ทำเช่นเดียวกันกับองค์ประกอบที่อยู่ติดกันแต่ละคู่ ตั้งแต่คู่แรกที่จุดเริ่มต้นไปจนถึงคู่สุดท้ายในตอนท้าย ณ จุดนี้ องค์ประกอบสุดท้ายควรเป็นตัวเลขที่มากที่สุด
* 3. ทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบทั้งหมด ยกเว้นองค์ประกอบสุดท้าย
* 4. ทำซ้ำขั้นตอนข้างต้นต่อไปเพื่อให้องค์ประกอบน้อยลงเรื่อยๆ ในแต่ละครั้ง จนกว่าจะไม่มีคู่ตัวเลขที่จะเปรียบเทียบ [1]
-
โมฆะสาธารณะแบบคงที่ bubbleSort (ข้อมูล int []) {
อุณหภูมิภายใน = 0;
สำหรับ (int i = data.length - 1; i > 0; --i) {
บูลีน isSort = เท็จ;
สำหรับ (int j = 0; j < i; ++ j) {
ถ้า (ข้อมูล [j + 1] < ข้อมูล [j]) {
อุณหภูมิ = ข้อมูล [j];
ข้อมูล[เจ] = ข้อมูล[เจ + 1];
ข้อมูล [j + 1] = อุณหภูมิ;
isSort = จริง;
-
-
// หากมีการแลกเปลี่ยนเกิดขึ้นในวงใน ให้ทำการเปรียบเทียบต่อไป หากไม่มีการแลกเปลี่ยนเกิดขึ้นในวงใน จะถือว่ามีการเรียงลำดับแล้ว
ถ้า (!isSort)
หยุดพัก;
-
-
-
* แนวคิดพื้นฐานของการเรียงลำดับการเลือกคือ:
* 1. ในระหว่างกระบวนการสำรวจอาร์เรย์ หาก i แทนหมายเลขลำดับปัจจุบันที่ต้องเรียงลำดับ คุณจะต้องค้นหาค่าต่ำสุดจาก [i+1...n-1] ที่เหลือ
* 2. จากนั้นแลกค่าต่ำสุดที่พบกับค่าที่ i ชี้ไป
* เนื่องจากแต่ละขั้นตอนในการกำหนดองค์ประกอบจะมีกระบวนการย่อยในการเลือกค่าต่ำสุด ผู้คนจึงเรียกมันว่าการเรียงลำดับการเลือกอย่างชัดเจน
* ข้อมูล @param
-
โมฆะสาธารณะแบบคงที่ selectSort (ข้อมูล int []) {
int minIndex = 0;
อุณหภูมิภายใน = 0;
สำหรับ (int i = 0; i < data.length; i++) {
minIndex = i; //ดัชนีอาร์เรย์ข้อมูลขั้นต่ำของพื้นที่ที่ไม่ได้เรียงลำดับ
for (int j = i + 1; j < data.length; j++) { // ค้นหาข้อมูลที่เล็กที่สุดในพื้นที่ที่ไม่เรียงลำดับและบันทึกตัวห้อยอาร์เรย์
ถ้า (ข้อมูล [j] < ข้อมูล [minIndex]) {
minIndex = เจ;
-
-
if (minIndex != i) { // หากตำแหน่งขั้นต่ำของพื้นที่ที่ไม่ได้เรียงลำดับไม่ใช่ข้อมูลแรกเริ่มต้น ให้แลกเปลี่ยน
อุณหภูมิ = ข้อมูล [i];
ข้อมูล [i] = ข้อมูล [minIndex];
ข้อมูล [minIndex] = อุณหภูมิ;
-
-
-
-
* กระบวนการดำเนินการรวมมีดังนี้:
* 1. ใช้ช่องว่างเพื่อให้ขนาดของมันเป็นผลรวมของลำดับที่เรียงลำดับทั้งสอง
* 2. ตั้งค่าพอยน์เตอร์สองตัว ตำแหน่งเริ่มต้นคือตำแหน่งเริ่มต้นของลำดับที่เรียงลำดับทั้งสอง
* 3. เปรียบเทียบองค์ประกอบที่ชี้โดยพอยน์เตอร์ทั้งสอง เลือกองค์ประกอบที่มีขนาดค่อนข้างเล็กแล้วใส่ลงในพื้นที่ผสาน และย้ายพอยน์เตอร์ไปยังตำแหน่งถัดไป
* 4. ทำซ้ำขั้นตอนที่ 3 จนกระทั่งตัวชี้ไปถึงจุดสิ้นสุดของลำดับ
* 5. คัดลอกองค์ประกอบที่เหลือทั้งหมดของลำดับอื่นโดยตรงไปยังจุดสิ้นสุดของลำดับที่ผสาน
-
int แบบคงที่สาธารณะ [] mergeSort (int [] arr) {// ผสานการเรียงลำดับ - การเรียกซ้ำ
ถ้า (ความยาว arr. == 1) {
กลับถึง;
-
int half = arr.length / 2;
int[] arr1 = int ใหม่[ครึ่ง];
int[] arr2 = ใหม่ int[arr.length - ครึ่ง];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, ครึ่ง, arr2, 0, arr2.length);
arr1 = MergeSort(arr1);
arr2 = MergeSort(arr2);
กลับ mergeSortSub (arr1, arr2);
-
int คงที่ส่วนตัว [] mergeSortSub (int [] arr1, int [] arr2) {// รวมรูทีนย่อยการเรียงลำดับ
int[] result = new int[arr1.length + arr2.length];
int i = 0;
อินท์เจ = 0;
int k = 0;
ในขณะที่ (จริง) {
ถ้า (arr1[i] < arr2[j]) {
ผลลัพธ์[k] = arr1[i];
ถ้า (++ i > arr1.length - 1) {
หยุดพัก;
-
} อื่น {
ผลลัพธ์[k] = arr2[j];
ถ้า (++ j > arr2.length - 1) {
หยุดพัก;
-
-
เค++;
-
สำหรับ (; i < arr1.length; i++) {
ผลลัพธ์[++k] = arr1[i];
-
สำหรับ (; j < arr2.length; j++) {
ผลลัพธ์[++k] = arr2[j];
-
ส่งคืนผลลัพธ์;
-
โมฆะคงที่ส่วนตัว printArray (int [] c) {
สำหรับ (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
-
โมฆะคงที่สาธารณะ main (สตริง [] args) {
ข้อมูล int[] = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(ก);
bubbleSort(ก);
printArray(ก);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(ข);
เลือกเรียงลำดับ(b);
printArray(ข);
System.out.println("insertSort...");
int[] c = data.clone();
พิมพ์อาร์เรย์(c);
การแทรกประเภท(c);
พิมพ์อาร์เรย์(c);
System.out.println("shellSort...");
รายการ <จำนวนเต็ม> รายการ = ใหม่ ArrayList<จำนวนเต็ม>();
สำหรับ(int i=0;i<data.length;i++)
list.add(ข้อมูล[i]);
System.out.println (รายการ);
shellSort (รายการ);
System.out.println (รายการ);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(ง);
printArray(ผสานSort(d));
-
-