การเรียงลำดับเป็นหนึ่งในการดำเนินการพื้นฐานที่เราดำเนินการกับวัตถุ แม้ในวัยเด็ก เด็ก ๆ จะถูกสอนให้เรียงลำดับเมื่อพวกเขาพัฒนาทักษะการคิด คอมพิวเตอร์และซอฟต์แวร์ก็ไม่มีข้อยกเว้น มีอัลกอริธึมการเรียงลำดับที่หลากหลายในJava ฉันขอแนะนำให้คุณตรวจสอบว่ามันคืออะไรและทำงานอย่างไร ถ้าวันหนึ่งคุณถูกถามเกี่ยวกับหนึ่งในนั้นในการสัมภาษณ์ล่ะ?
![Java webinar]()
L จะเท่ากับ
การแนะนำ
องค์ประกอบการเรียงลำดับเป็นหนึ่งในหมวดหมู่ของอัลกอริทึมที่นักพัฒนาต้องรู้ ถ้าตอนที่ฉันเรียนวิทยาการคอมพิวเตอร์ไม่ได้เอาจริงเอาจัง นักเรียนสมัยนี้ต้องสามารถใช้งานและเข้าใจอัลกอริทึมการเรียงลำดับได้ อัลกอริธึมพื้นฐาน ง่ายที่สุด ดำเนินการโดยใช้for loop โดยปกติแล้ว ในการจัดเรียงคอลเล็กชันขององค์ประกอบต่างๆ เช่น อาร์เรย์ คุณต้องผ่านคอลเล็กชันนั้นด้วยวิธีใดวิธีหนึ่ง ตัวอย่างเช่น:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
int i) จาก 0 เป็นองค์ประกอบสุดท้ายในอาร์เรย์ อันที่จริง เรากำลังนำแต่ละองค์ประกอบในอาร์เรย์และพิมพ์เนื้อหาออกมา ยิ่งองค์ประกอบในอาร์เรย์มากเท่าไหร่ โค้ดก็จะยิ่งใช้เวลานานขึ้นเท่านั้น นั่นคือ if nคือจำนวนขององค์ประกอบ เมื่อโปรแกรมn = 10จะใช้เวลาทำงานนานกว่าเมื่อถึงสองเท่า n = 5หากโปรแกรมของเรามีลูปเดียว เวลาดำเนินการจะเพิ่มขึ้นเป็นเส้นตรง ยิ่งมีองค์ประกอบมาก เวลาดำเนินการก็จะยิ่งนานขึ้น ปรากฎว่าอัลกอริทึมด้านบนทำงานในเวลาเชิงเส้น (ฟังก์ชันเชิงเส้นของ n) ในกรณีเช่นนี้ เรากล่าวว่าความซับซ้อนของอัลกอริทึมคือ "O(n)" สัญลักษณ์นี้เรียกอีกอย่างว่า "big O" หรือ "พฤติกรรมเชิงเส้นกำกับ" แต่คุณก็จำได้"
อัลกอริทึมการเรียงลำดับที่ง่ายที่สุด (การเรียงลำดับแบบฟอง)
สมมติว่าเรามีอาร์เรย์และเราสามารถวนซ้ำได้ ยอดเยี่ยม. ทีนี้ลองเรียงลำดับจากน้อยไปมาก สิ่งนี้หมายความว่า? หมายความว่าเมื่อกำหนดสององค์ประกอบ (เช่น ,a = 6) b = 5เราต้องจัดเรียงใหม่aและbif aมากกว่าb(if a > b) สิ่งนี้หมายความว่าอย่างไรเมื่อเราใช้ดัชนีเพื่อทำงานกับคอลเลกชัน (เช่นเดียวกับกรณีของอาร์เรย์) หมายความว่าหากองค์ประกอบที่มีดัชนี a มีขนาดใหญ่กว่าองค์ประกอบที่มีดัชนีb( array[a] > array[b]) จะต้องสลับองค์ประกอบนั้น มีวิธีการเปลี่ยนสถานที่ต่างๆ แต่เราจะใช้เทคนิคที่เรียบง่าย เข้าใจ และจำง่าย:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
array[i] < array[i-1]จะใช้ไม่ได้สำหรับ0ดัชนี การทำเช่นนี้ยังช่วยปกป้องเราจากกรณีที่อาร์เรย์ไม่มีองค์ประกอบหรือมีเพียงองค์ประกอบเดียว และทำให้โค้ดดูดีขึ้น แต่อาร์เรย์ที่เป็นผลลัพธ์ยังคงไม่เรียงลำดับ เพราะการผ่านเพียงครั้งเดียวไม่เพียงพอสำหรับการเรียงลำดับ เราจะต้องเพิ่มการวนซ้ำอีกครั้งซึ่งเราจะดำเนินการผ่านซ้ำแล้วซ้ำอีกจนกว่าเราจะได้อาร์เรย์ที่เรียงลำดับ:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
while) จนกว่าเราจะตัดสินใจว่าไม่ต้องการวนซ้ำอีก ตามค่าเริ่มต้น ก่อนการวนซ้ำแต่ละครั้ง เราจะถือว่าอาร์เรย์ของเราถูกจัดเรียงแล้ว และเราไม่ต้องวนซ้ำอีกต่อไป ดังนั้นเราจึงย้ายองค์ประกอบตามลำดับและตรวจสอบสมมติฐานนี้ แต่ถ้าองค์ประกอบไม่อยู่ในลำดับ เราจะสลับองค์ประกอบและเข้าใจว่าตอนนี้เราไม่รับประกันว่าองค์ประกอบจะอยู่ในลำดับที่ถูกต้อง ซึ่งหมายความว่าเราจำเป็นต้องทำซ้ำอีกครั้ง ตัวอย่างเช่น สมมติว่าเรา[3, 5, 2]มี 5เป็นมากกว่า3— ทุกอย่างเรียบร้อยดี แต่2น้อยกว่า5. อย่างไรก็ตาม[3, 2, 5]ต้องใช้บัตรอื่นเนื่องจาก3 > 2และจำเป็นต้องเปลี่ยน เนื่องจากเรากำลังใช้ลูปภายในลูป ความซับซ้อนของอัลกอริทึมของเราจึงเพิ่มขึ้น กำหนดnองค์ประกอบ มันจะกลายn * nเป็น นั่นO(n^2)คือ สิ่งนี้เรียกว่าความซับซ้อนกำลังสอง โดยทั่วไป เราไม่สามารถทราบได้แน่ชัดว่าจะต้องทำซ้ำกี่ครั้ง การแสดงออกของความซับซ้อนของอัลกอริทึมแสดงให้เห็นว่าความซับซ้อนเพิ่มขึ้นอย่างไรในกรณีที่เลวร้ายที่สุด นั่นคือมันบ่งชี้ว่าเวลาดำเนินการจะเพิ่มขึ้นเท่าใดเมื่อจำนวนองค์ประกอบnเปลี่ยนไป Bubble sort เป็นหนึ่งในอัลกอริทึมการเรียงลำดับที่ง่ายและไม่มีประสิทธิภาพที่สุด บางครั้งก็เรียกว่า "โง่เขลา" เนื้อหาในหัวข้อนี้:
เรียงลำดับการเลือก
อัลกอริทึมการเรียงลำดับอื่นคือการเรียงลำดับแบบเลือก นอกจากนี้ยังมีความซับซ้อนกำลังสอง แต่จะเพิ่มเติมในภายหลัง ดังนั้นแนวคิดง่ายๆ ในแต่ละรอบ เราเลือกองค์ประกอบที่เล็กที่สุดและเปลี่ยนไปยังจุดเริ่มต้น นอกจากนี้ การส่งแต่ละครั้งจะเริ่มต้นไปทางขวาหนึ่งก้าว กล่าวอีกนัยหนึ่ง การผ่านครั้งแรกเริ่มจากองค์ประกอบที่ 0 การผ่านครั้งที่สองจากครั้งแรก ฯลฯ จะมีลักษณะดังนี้:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
การเรียงลำดับการแทรก
การเรียงลำดับการแทรกยังมีความซับซ้อนแบบกำลังสอง เนื่องจากเรามีลูปภายในลูปอีกครั้ง อะไรทำให้การเรียงลำดับการแทรกแตกต่างกัน อัลกอริทึมการเรียงลำดับนี้ "เสถียร" ซึ่งหมายความว่าองค์ประกอบที่เหมือนกันจะไม่เปลี่ยนลำดับสัมพัทธ์ อีกครั้ง เราหมายถึงเหมือนกันในแง่ของลักษณะที่เรากำลังจัดเรียงตาม
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
กระสือเรียง
มีอัลกอริธึมการเรียงลำดับอย่างง่ายอีกอย่างหนึ่ง: การเรียงลำดับแบบกระสวย สิ่งนี้เรียกอีกอย่างว่าการจัดเรียงฟองแบบสองทิศทางหรือการเรียงลำดับเครื่องปั่นค็อกเทล ชื่ออื่นเหล่านี้บอกเราว่าการจัดเรียงกระสวยไม่เกี่ยวกับกระสวยอวกาศ มันเกี่ยวกับสิ่งที่เคลื่อนไหวไปมา ตอนนี้คุณสามารถคิดได้เมื่อคุณนึกถึงอัลกอริทึมนี้ สาระสำคัญของอัลกอริทึมคืออะไร? สาระสำคัญของอัลกอริทึมคือการวนซ้ำจากซ้ายไปขวา สลับองค์ประกอบและตรวจสอบว่าองค์ประกอบใดที่เหลืออยู่ในทิศทางอื่นจำเป็นต้องเปลี่ยนหรือไม่
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
เรียงเปลือก
อัลกอริธึมการเรียงลำดับอย่างง่ายอีกอย่างหนึ่งคือการเรียงลำดับเชลล์ สาระสำคัญของมันคล้ายกับการเรียงลำดับแบบฟอง แต่ในการทำซ้ำแต่ละครั้งเรามีช่องว่างที่แตกต่างกันระหว่างองค์ประกอบที่เปรียบเทียบ มันถูกตัดครึ่งด้วยการวนซ้ำแต่ละครั้ง นี่คือการใช้งาน:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
ผสานการจัดเรียง
นอกจากอัลกอริธึมการเรียงลำดับอย่างง่ายเหล่านี้แล้ว ยังมีอัลกอริธึมการเรียงลำดับที่ซับซ้อนกว่าด้วย ตัวอย่างเช่น การเรียงลำดับการผสาน มีสองสิ่งที่ควรทราบ ประการแรก การเรียกซ้ำมาช่วยเราที่นี่ ประการที่สอง ความซับซ้อนของอัลกอริทึมไม่ได้เป็นกำลังสองอีกต่อไป อย่างที่เราคุ้นเคย ความซับซ้อนของอัลกอริทึมนี้คือลอการิทึม นี้เขียนเป็นO(n log n). ลองนำไปใช้กัน ก่อนอื่น เราจะเขียนการเรียกซ้ำไปยังวิธีการเรียงลำดับ:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
mergeSort(array, 0, array.length-1). อย่างที่คุณเห็น กระบวนการจะจบลงที่การยอมรับอาร์เรย์อินพุตพร้อมกับการระบุจุดเริ่มต้นและจุดสิ้นสุดของส่วนที่จำเป็นต้องจัดเรียง เมื่อการเรียงลำดับเริ่มต้นขึ้น สิ่งเหล่านี้คือจุดเริ่มต้นและจุดสิ้นสุดของอาร์เรย์ จากนั้นเราจะคำนวณตัวคั่นซึ่งเป็นดัชนีที่เราจะแบ่งอาร์เรย์ ถ้าสามารถแบ่งอาร์เรย์ออกเป็น 2 ส่วน เราจะเรียกวิธีการเรียงลำดับซ้ำสำหรับสองซีกของอาร์เรย์ เราเตรียมบัฟเฟอร์เสริมที่เราจะแทรกส่วนที่จัดเรียงไว้ จากนั้น ตั้งค่าดัชนีที่จุดเริ่มต้นของส่วนที่จะจัดเรียง และเริ่มดำเนินการผ่านแต่ละองค์ประกอบของบัฟเฟอร์ที่ว่างเปล่า เติมด้วยองค์ประกอบที่เล็กที่สุด หากองค์ประกอบที่ดัชนีชี้ไปน้อยกว่าองค์ประกอบที่ตัวคั่นชี้ไป เราจะใส่องค์ประกอบนั้นในบัฟเฟอร์และเปลี่ยนดัชนี มิฉะนั้น, เราวางองค์ประกอบที่ตัวคั่นชี้ไปที่บัฟเฟอร์และเปลี่ยนตัวคั่น ทันทีที่ตัวคั่นเกินขอบเขตของส่วนที่จัดเรียงหรือเราเติมอาร์เรย์ทั้งหมด ช่วงที่ระบุจะถือว่าถูกจัดเรียงเนื้อหาในหัวข้อนี้:
การเรียงลำดับการนับและการเรียงลำดับฐาน
อัลกอริธึมการเรียงลำดับที่น่าสนใจอีกอย่างหนึ่งคือการเรียงลำดับการนับ ความซับซ้อนของอัลกอริทึมในที่นี้คือจำนวนองค์ประกอบอยู่O(n+k)ที่ไหน และ เป็นค่าสูงสุดขององค์ประกอบ อัลกอริทึมนี้มีข้อบกพร่องอย่างหนึ่ง: เราจำเป็นต้องทราบค่าต่ำสุดและค่าสูงสุดในอาร์เรย์ ต่อไปนี้เป็นตัวอย่างของการเรียงลำดับการนับ: nk
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
จัดเรียงอย่างรวดเร็ว
ได้เวลาของหวานแล้ว — การจัดเรียงอย่างรวดเร็ว หนึ่งในอัลกอริทึมการเรียงลำดับที่มีชื่อเสียงที่สุด มันมีความซับซ้อนของลอการิทึม:O(n log n). อัลกอริธึมการเรียงลำดับนี้พัฒนาโดย Tony Hoare ที่น่าสนใจคือ เขาประดิษฐ์มันขึ้นในขณะที่อาศัยอยู่ในสหภาพโซเวียต ซึ่งเขาได้ศึกษาการแปลด้วยคอมพิวเตอร์ที่มหาวิทยาลัยมอสโก และพัฒนาหนังสือวลีภาษารัสเซีย-อังกฤษ ยิ่งไปกว่านั้น Java ใช้เวอร์ชันที่ซับซ้อนของอัลกอริทึมนี้ในArrays.sort. แล้วCollections.sort? ทำไมไม่ลองดูว่าสิ่งต่าง ๆ ถูกจัดเรียง "ภายใต้ประทุน" อย่างไร นี่คือรหัส:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
int[]แหล่งที่มา) เราสร้างเครื่องหมายสองตัว: ซ้าย ( L) และขวา ( R) ระหว่างการเรียกใช้เมธอดแรก จะสอดคล้องกับจุดเริ่มต้นและจุดสิ้นสุดของอาร์เรย์ จากนั้นเราจะระบุองค์ประกอบเดือยซึ่งตั้งชื่ออย่างpivotเหมาะสม หลังจากนี้ งานของเราคือย้ายค่าที่เล็กกว่าไปpivotทางซ้ายของpivotและค่าที่ใหญ่กว่าไปทางขวา ในการดำเนินการนี้ ขั้นแรกให้เลื่อนLเครื่องหมายจนกว่าเราจะพบค่าที่pivotมากกว่า หากไม่พบค่าที่น้อยกว่าpivot. จากนั้นเราย้าย เครื่องหมายจนกว่าเรา จะ
Rพบค่าที่น้อยกว่า
pivotถ้าไม่พบค่าที่มากกว่า ก็จะ
Rมีค่า
pivotเท่ากับ ต่อไป หาก
Lเครื่องหมายอยู่ก่อน
Rเครื่องหมายหรือตรงกับเครื่องหมาย เราจะพยายามสลับองค์ประกอบหาก
Lองค์ประกอบน้อยกว่า
Rองค์ประกอบ จากนั้นเราเลื่อน
Lไปทางขวาทีละ 1 และเลื่อน
Rไปทางซ้ายทีละ 1 เมื่อ
Lเครื่องหมายเคลื่อนเลย
Rเครื่องหมาย แสดงว่าการสลับเสร็จสมบูรณ์ ค่าที่น้อยกว่าจะอยู่ทางด้านซ้ายของ
pivotค่าที่มากขึ้นจะอยู่ทางด้านขวาของ
pivot. หลังจากนี้ เราจะเรียกวิธีการจัดเรียงแบบเดียวกันนี้ซ้ำๆ ในแถบย่อย — จากจุดเริ่มต้นของส่วนที่จะจัดเรียงไปยังเครื่องหมายด้านขวา และจากเครื่องหมายด้านซ้ายไปยังจุดสิ้นสุดของส่วนเพื่อจัดเรียง ทำไมตั้งแต่ต้นถึงเครื่องหมายถูก? เนื่องจากเมื่อสิ้นสุดการวนซ้ำ ปรากฎว่าเครื่องหมายด้านขวาเคลื่อนมากพอที่จะกลายเป็นขอบเขตของส่วนด้านซ้าย อัลกอริทึมนี้ซับซ้อนกว่าการเรียงลำดับอย่างง่าย ดังนั้น ทางที่ดีควรร่างไว้ หยิบกระดาษสีขาวแล้วเขียน: 4 2 6 7 3 จากนั้นเขียน
pivotตรงกลางเช่นใต้หมายเลข 6 วงกลม ต่ำกว่า 4 ให้เขียน
Lและต่ำกว่า 3 ให้
Rเขียน 4 น้อยกว่า 6, 2 น้อยกว่า 6 เราลงเอย
Lที่
pivotตำแหน่งเพราะ
Lเลื่อนผ่านไม่ได้
pivotตามสภาพ. เขียนอีกครั้ง 4 2 6 7 3 วงกลม 6 (
pivot) แล้ววางไว้
Lข้างใต้ ตอนนี้ย้าย
Rเครื่องหมาย 3 น้อยกว่า 6 ดังนั้นใส่ เครื่องหมายบน 3 เนื่องจาก 3
Rน้อยกว่า 6 (
pivot) เราจึงทำ
swapเขียนผลลัพธ์: 4 2 3 7 6. วงกลม 6 เนื่องจากยังคงเป็น
pivot. เครื่องหมาย
Lอยู่ที่ 3 เครื่องหมายอยู่ ที่
R6 โปรดจำไว้ว่าเราเลื่อนเครื่องหมายจนกว่า
Lจะเคลื่อนที่เลย
Rเลื่อน
Lไปที่หมายเลขถัดไป ในที่นี้ ผมอยากสำรวจความเป็นไปได้สองประการ: 1) กรณีที่หมายเลขสุดท้ายคือ 7 และ 2) กรณีที่หมายเลขสุดท้ายคือ 1 ไม่ใช่ 7
หากหมายเลขสุดท้ายคือ 1:ย้าย
Lเครื่องหมายไปที่ 1 เนื่องจากเราสามารถย้าย
Lตราบใดที่
Lเครื่องหมายชี้ไปที่จำนวนที่น้อย
pivotกว่า แต่เราไม่สามารถย้าย
Rออกจาก 6 ได้ เพราะเราจะย้าย R ได้ก็ต่อเมื่อ เครื่องหมายชี้ไปที่ ตัวเลข
Rที่มากกว่า
pivotเราไม่ทำ a
swapเพราะ 1 น้อยกว่า 6 เขียนสถานการณ์ปัจจุบัน: 4 2 3 1 6 วงกลม 6 (
pivot)
Lเลื่อนไปมา
pivotและหยุดเคลื่อนไหว
Rไม่ขยับ เราไม่ทำการแลกเปลี่ยน เปลี่ยน
Lและ
Rโดยตำแหน่งเดียว เขียน
Rเครื่องหมายภายใต้ 1
Lเครื่องหมายอยู่นอกขอบเขต เพราะ
Lอยู่นอกขอบเขตเราไม่ทำอะไร แต่เราเขียน 4 2 3 1 อีกครั้ง เพราะนี่คือด้านซ้ายของเรา ซึ่งน้อยกว่า
pivot(6) เลือกใหม่
pivotและเริ่มต้นใหม่อีกครั้ง :)
หากหมายเลขสุดท้ายคือ 7:เลื่อน
Lเครื่องหมายไปที่ 7 เราไม่สามารถเลื่อนเครื่องหมายไปทางขวาได้ เพราะมันชี้ไปที่เดือยแล้ว 7 มากกว่า ดังนั้น เรา
pivotจึงทำ
swapเขียนผลลัพธ์: 4 2 3 6 7. วงกลม 6 เนื่องจากเป็น
pivot. ตอนนี้ เครื่องหมาย
Lถูกเลื่อนไปที่ 7 และ
Rเครื่องหมายถูกเลื่อนไปที่ 3 มันไม่สมเหตุสมผลเลยที่จะเรียงลำดับส่วนจาก
Lไปยังจุดสิ้นสุด เนื่องจากมีองค์ประกอบเพียง 1 รายการ อย่างไรก็ตาม เราส่งชิ้นส่วนจาก 4 ไปยัง
Rเครื่องหมายเพื่อจัดเรียง เราเลือก a
pivotแล้วเริ่มต้นใหม่ทั้งหมด :) เมื่อมองแวบแรกอาจดูเหมือนว่าถ้าคุณเพิ่มค่าจำนวนมากเท่ากับ
pivotจากนั้นคุณจะทำลายอัลกอริทึม แต่นี่ไม่ใช่กรณี คุณสามารถคิดชุดค่าผสมที่ยุ่งยากและบนกระดาษเพื่อโน้มน้าวใจตัวเองว่าทุกอย่างถูกต้องและประหลาดใจที่การกระทำง่ายๆ ดังกล่าวใช้กลไกการเรียงลำดับที่เชื่อถือได้ ข้อเสียเพียงอย่างเดียวคืออัลกอริธึมการเรียงลำดับนี้ไม่เสถียร เนื่องจากการสลับอาจเปลี่ยนลำดับสัมพัทธ์ขององค์ประกอบที่เหมือนกัน หากพบองค์ประกอบใดองค์ประกอบหนึ่งก่อนหน้า
pivotก่อนที่องค์ประกอบอื่นๆ จะถูกสลับไปยังส่วนก่อน
pivotหน้า
GO TO FULL VERSION