메이투안 인터뷰: 빠른 일정을 손으로 써주세요. 깜짝 놀랐습니다!

오늘 면접관님이 즉석에서 퀵소트를 작성해 달라고 하셨습니다. 현장은 다음과 같습니다.

인터뷰어: 계속해서 데이터 구조와 알고리즘에 대해 이야기해 주실 수 있나요? (말하면서 이력서를 넘기더니 펜을 건넸다. 이력서 뒷면에 써달라는 뜻이었다.)

루키나: 무슨 말이야? 여기에 쓰시겠어요? (이력서를 가리키며)

면접관: 응

신입 나: 아니

면접관: 자, 오늘 면접은 여기까지

신입 나: (너무 화가 나요. 노사에 고발하고 싶어요. 코드를 재개하시겠습니까? 그냥 쓰세요, 어차피 종이 한 장일 뿐입니다.

사실 퀵큐는 쉽지만 손으로 ​​못쓰는 분들도 많을 것 같은데요, 여러모로 그 자리에서 손으로 쓰는 분들도 많죠?

초보인데 아직 손으로 쓸 수 있거든요. 결국 인터뷰 전에는 일부러 "빠른 받아쓰기

Background

백과사전에서:

빠른 정렬은 1962년 C. A. R. Hoare에 의해 제안되었습니다. 기본 아이디어는 한 번의 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나눈 다음, 이 방법을 사용하여 데이터의 두 부분을 빠르게 분리하는 것입니다. . 정렬은 전체 정렬 프로세스를 [재귀적으로] 수행하여 전체 데이터가 정렬된 시퀀스가 ​​되도록 할 수 있습니다.

이 개념을 이해하는 것은 꽤 어렵습니다.

다음과 같이 이해될 수 있습니다.

퀵 정렬은 버블 정렬의 향상된 버전입니다. 전체 프로세스는 항목을 제거하고 패치하고, 찢고, 패치하고, 찢고 패치하는 것입니다. 모든 요소는 정렬된 상태에 도달합니다.

핵심 아이디어:

먼저 시퀀스에서 숫자를 기본 숫자로 가져온 다음 크기 분할을 수행합니다.

파티션 프로세스에서 이 숫자보다 큰 숫자는 모두 오른쪽에 배치되고, 그보다 작은 숫자는 오른쪽에 배치됩니다. 또는 그와 같으면 모두 왼쪽에 놓습니다.

각 간격에 하나의 숫자만 있을 때까지 왼쪽 및 오른쪽 간격에 대해 두 번째 단계를 반복하고 정렬이 완료됩니다.

구현사례

사진과 글을 통해 차근차근 분해해보겠습니다.

이 배열을 [4,1,6,2,9,3]예로 들어보세요.

첫 번째 패스:

• 먼저 [4,1,6,2,9,3]을 분할하고 요소 4를 피벗점으로 선택합니다
• 1 < 4(피벗점)인지 확인하세요
• 6 < 4인지 확인하세요. (피벗 포인트)
• 2 < 4(피벗 포인트)인지 확인하세요.
• 2 < 4(피벗 포인트)가 true인지 확인하세요. 인덱스 2를 저장된 인덱스 6으로 바꾸세요.
• (피벗 포인트)
• 3 < 4(피벗 포인트)인지 확인
• 3 < 4(피벗 포인트)인 경우 인덱스 3과 6을 저장합니다.
• 피벗 포인트 4를 교환하고 저장합니다. index 3
• 이때 피벗점 4의 왼쪽은 모두 4보다 작고, 오른쪽은 4보다 큽니다

현재 배열 순서는 [3, 1, 2, 4, 9, 6].

다음 단계:

• 먼저 왼쪽을 정렬하세요
• 요소 3을 피벗점으로 선택하세요
• 1 < 3(피벗점)인지 확인하세요
• 2 < ; (피벗 포인트)
• 피벗 포인트 3과 저장 인덱스 값 2를 교환
• 이제 피벗 포인트가 정렬된 위치에서 분할되었습니다
• [2,1] 2를 피벗 포인트로 선택
• 1<2(피벗 포인트)인지 확인
• 왼쪽의 순회가 완료되고 피벗 포인트 2와 저장 인덱스 1이 교환됩니다

오른쪽도 마찬가지입니다... 시각적인 것은 피하세요 피로도를 하나씩 설명하지는 않겠지만 아래 동적 시연 사진을 보시면 됩니다.

2. 빠른 정렬 방법의 전체 프로세스

3. 아래에서는 Java 언어를 사용하여 이전 빠른 정렬 사례를 구현합니다.

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤：
    //1.比较startIndex和endIndex，更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就没有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基准大，right比基准小，进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

로그인 후 복사

출력 결과:

[1, 2, 3, 4, 6, 9]

코드 구현, 이해하기 쉽도록 이전 애니메이션과 결합하는 것이 좋습니다.

퀵 정렬을 작성하는 방법에는 여러 가지가 있습니다. 관심이 있으시면 Wikipedia에서 퀵 정렬이 어떻게 소개되는지 직접 찾아보실 수도 있습니다.

4. 복잡도 분석

시간 복잡도:

최악의 시나리오는 매번 검색되는 요소가 배열에서 가장 작거나 가장 큰 요소라는 것입니다. 한 요소씩 순서대로 정렬)

이 경우 시간 복잡도는 쉽게 계산할 수 있는데, 이는 버블 정렬의 시간 복잡도입니다. T[n] = n * (n-1) = n^2 + n ;

가장 좋은 경우는 O(nlog2n)이며, 도출 과정은 다음과 같습니다:

(재귀 알고리즘의 시간 복잡도 공식: T[n] = aT[n/b] + f(n) )

https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.png

그래서 평균 시간 복잡도는 O(nlog2n)

공간 복잡성:

공간 퀵 정렬에서 사용하는 것은 상수 수준인 O(1)이며 실제로 공간을 소비하는 것은 재귀 호출입니다. 각 재귀는 일부 데이터를 유지해야 하기 때문입니다.

최적의 경우 공간 복잡성은 다음과 같습니다. O(log2n ); 그룹이 매번 동일하게 분할되는 경우

최악의 공간 복잡도는 O(n) 버블 정렬의 경우로 변질됩니다

그러므로 평균 공간 복잡도는 O(log2n)

5. 빠른 정렬 방법 요약

• 기본적으로 첫 번째 요소가 피벗점으로 사용됩니다. (피벗점 확인으로 "빠른 정렬 방법"과 "임의 정렬 방법"이 구분됩니다.) 두 가지 알고리즘, 무작위 정렬은 요소를 피벗 포인트로 무작위로 지정합니다.
• 인접하지 않은 두 요소가 교환되면 한 번의 교환으로 여러 역순이 제거되어 정렬 프로세스가 빨라집니다.

Postscript