Concept
빠른 정렬은 교환 정렬입니다. 단계는 비교를 위해 베이스 요소를 사용하고, 베이스 요소보다 작은 것을 한쪽으로 이동하고, 베이스 요소보다 큰 것을 반대쪽으로 이동하는 것입니다. 따라서 배열을 두 부분으로 나누고 두 부분에서 참조 요소를 선택하고 위의 단계를 반복합니다. 프로세스는 다음과 같습니다:
(추천 동영상: java 동영상 튜토리얼)
Purple: 기준 요소
녹색: 기본 요소보다 큼
노란색: 기본 요소보다 작음
이 아이디어를 분할 및 정복 방법이라고 합니다.
기본요소
기본요소 선택은 랜덤으로 선택 가능합니다. 다음 사용에서는 첫 번째 요소를 기본 요소로 사용하겠습니다.
정렬 과정
정렬 및 분할 과정은 아래와 같습니다.
보라색은 기본 요소, (매 라운드마다 다시 선택)
녹색은 기타 요소
첫 번째 라운드
두 번째 라운드 
3라운드 
위 그림과 같이:
#🎜🎜 #요소의 경우 숫자는 n입니다. 정렬 과정에서 모든 요소를 비교해야 하므로 시간 복잡도는 O(n)입니다.평균적으로 정렬 라운드에는 logn 라운드가 필요하므로 평균 시간 복잡도는 빠른 정렬의 수는 O(nlogn)입니다.
정렬 구현 방법
구현 방법에는 양측 순환 방식과 일측 순환 방식이 포함됩니다#🎜 🎜 #양방향 루프 방법첫 번째 선택은 피벗 요소(피벗) 4를 선택하고 왼쪽과 오른쪽 포인터가 배열의 가장 왼쪽과 가장 오른쪽 요소를 가리키도록 설정하고,
# 🎜🎜#
첫 번째 루프에서는 오른쪽 포인터(rightData)가 가리키는 데이터부터 시작하여 기본 요소와 비교합니다#🎜 🎜#rightData >= 피벗이면 오른쪽 포인터가 왼쪽으로 이동을 가리키고, rightData 왼쪽 포인터가 데이터를 가리킵니다(leftData ) 기본 요소와 비교합니다. leftData 피벗이면 왼쪽과 오른쪽이 가리키는 요소를 바꿉니다.
그런 다음 왼쪽 및 오른쪽 요소가 교환되는 지점:
포인터 이동의 첫 번째 라운드 후 다음 구조가 얻어집니다.
두 번째 라운드 후 얻은 결과:
#🎜 🎜#
네 번째 반복 라운드 후에 다음을 얻습니다.
요소의 경우 오른쪽 포인터가 이동을 멈추고 피벗 요소와 포인터 요소가 교환되며 결과는 다음과 같습니다.
구현 코드
public class DoubleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//递归结束条件
if (startIndex >= endIndex) {
return;
}
// 基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个元素为基准元素，也可以随机抽取
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right) {
// 控制right指针比较并左移
while (left = pivot) {
right--;
}
// 控制left指针比较并右移
while (left <p></p>일방 순환 방식 <p id="实现代码" style="white-space: normal;"><strong></strong>양방향 순환 방식 비교 배열의 양쪽에서 요소를 교환하는 반면, 단방향 루프 규칙은 배열의 한쪽에서 순회하여 거꾸로 비교 및 교환하므로 구현이 더 간단합니다. </p>과정은 다음과 같습니다: <p id="单边循环法" style="white-space: normal;"><strong></strong>먼저 피벗 요소를 선택합니다(임의로 선택 가능). </p>시작 위치를 가리키도록 마크 포인터를 설정합니다. 피벗 요소보다 작은 피벗 요소를 나타내는 배열 영역 경계(이해가 안 되시면 나중에 요소를 교환할 때 사용하는 것으로 이해하시면 됩니다) <p><br>#🎜 🎜#원래 배열은 다음과 같습니다: </p><blockquote>#🎜🎜 #<p></p>
<blockquote><p>从基准元素下一位开始遍历数组<br>如果该元素大于基准元素，继续往下遍历<br>如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。</p></blockquote>
<p>遍历到元素3时，因为3 </p>
<p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg" alt="Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)"></p>
<p>然后交换元素</p>
<p><img src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg" alt="Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)"></p>
<p>然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。</p>
<p id="实现代码-1" style="white-space: normal;"><strong>实现代码</strong></p>
<pre class="brush:php;toolbar:false">public class SingleSort {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
//递归结束条件
if (startIndex >= endIndex) {
return;
}
// 基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（单边循环法）
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
public static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个元素为基准元素，也可以随机抽取
int pivot = arr[startIndex];
int mark = startIndex;
for(int i = startIndex + 1; i<p id="总结" style="white-space: normal;"><strong>总结</strong></p><p>本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。</p><p>参考资料：《小灰的算法之旅》 第四章。</p><p>本文来自php中文网，<a href="//m.sbmmt.com/java/base/" target="_blank">java教程</a>栏目，欢迎学习！ </p>
위 내용은 Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!