Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)

Concept

빠른 정렬은 교환 정렬입니다. 단계는 비교를 위해 베이스 요소를 사용하고, 베이스 요소보다 작은 것을 한쪽으로 이동하고, 베이스 요소보다 큰 것을 반대쪽으로 이동하는 것입니다. 따라서 배열을 두 부분으로 나누고 두 부분에서 참조 요소를 선택하고 위의 단계를 반복합니다. 프로세스는 다음과 같습니다:

(추천 동영상: java 동영상 튜토리얼)

Purple: 기준 요소
녹색: 기본 요소보다 큼
노란색: 기본 요소보다 작음

이 아이디어를 분할 및 정복 방법이라고 합니다.

기본요소

기본요소 선택은 랜덤으로 선택 가능합니다. 다음 사용에서는 첫 번째 요소를 기본 요소로 사용하겠습니다.

정렬 과정

정렬 및 분할 과정은 아래와 같습니다.

보라색은 기본 요소, (매 라운드마다 다시 선택)
녹색은 기타 요소

첫 번째 라운드

두 번째 라운드

3라운드

위 그림과 같이:

#🎜🎜 #요소의 경우 숫자는 n입니다. 정렬 과정에서 모든 요소를 ​​비교해야 하므로 시간 복잡도는 O(n)입니다.

평균적으로 정렬 라운드에는 logn 라운드가 필요하므로 평균 시간 복잡도는 빠른 정렬의 수는 O(nlogn)입니다.

정렬 구현 방법

구현 방법에는 양측 순환 방식과 일측 순환 방식이 포함됩니다

#🎜 🎜 #양방향 루프 방법

첫 번째 선택은 피벗 요소(피벗) 4를 선택하고 왼쪽과 오른쪽 포인터가 배열의 가장 왼쪽과 가장 오른쪽 요소를 가리키도록 설정하고,

# 🎜🎜#

첫 번째 루프에서는 오른쪽 포인터(rightData)가 가리키는 데이터부터 시작하여 기본 요소와 비교합니다#🎜 🎜#rightData >= 피벗이면 오른쪽 포인터가 왼쪽으로 이동을 가리키고, rightData 왼쪽 포인터가 데이터를 가리킵니다(leftData ) 기본 요소와 비교합니다. leftData 피벗이면 왼쪽과 오른쪽이 가리키는 요소를 바꿉니다.

포인터 이동의 첫 번째 라운드 후 다음 구조가 얻어집니다.

그런 다음 왼쪽 및 오른쪽 요소가 교환되는 지점:

루프의 첫 번째 라운드가 종료되고 다시 오른쪽 포인터로 전환하고 위 단계를 반복합니다.

두 번째 라운드 후 얻은 결과:

세 번째 라운드 후 얻은 결과:

#🎜 🎜#

네 번째 반복 라운드 후에 다음을 얻습니다.

요소의 경우 오른쪽 포인터가 이동을 멈추고 피벗 요소와 포인터 요소가 교환되며 결과는 다음과 같습니다.

# 🎜🎜#은 사이클의 끝을 선언하고 Pivot 요소를 기반으로 여러 부분으로 분할합니다. 두 부분, 이 두 부분의 배열은 위 단계에 따라 작동됩니다.

구현 코드

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="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-12.jpg" class="lazy" alt="Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)"></p>
<p>然后交换元素</p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/040/baca0480a2a4ba4850e39cd5916f2819-13.jpg" class="lazy" 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="https://www.php.cn/java/base/" target="_blank">java教程</a>栏目，欢迎学习！  </p>

위 내용은 Java 정렬 알고리즘을 빠르게 마스터하세요 - 빠른 정렬(그림 및 텍스트)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!