빠 른 정렬 원리

4. 567917. 빠 른 정렬 은 '나 누 어 다스 리 는' 사상 이다. 매번 정렬 할 때마다 현재 서열 의 가장 왼쪽 요 소 를 보초병 으로 설정 하고 두 개의 지침 low 와 high 를 설정 하 며 두 지침 이 가리 키 는 요 소 를 보초병 과 비교 한다.하 이 포인터 가 가리 키 는 보초병 보다 작은 원 소 를 low 의 위치 에 놓 기;로 우 포인터 가 가리 키 는 보초병 보다 큰 원 소 를 하 이 위치 에 놓 습 니 다.low 와 high 가 같은 위 치 를 가리 키 면 이 위 치 는 보초병 의 위치 이 며 이 위 치 를 보초병 에 게 부여 합 니 다.그리고 보초병 을 경계 로 보초병 왼쪽 의 '한 꿰미' 와 보초병 오른쪽 에 있 는 '한 꿰미' 를 이 과정 을 재 귀적 으로 집행 한다
4. 567917. 즉, 매번 정렬 할 때마다 두 가지 작업 을 했다. a. 보초병 보다 작은 요 소 를 보초병 의 왼쪽 에 두 고 보초병 보다 큰 요 소 를 보초병 의 오른쪽 에 두 고 b. 보초병 을 정확 한 위치 에 놓는다
public class QuickSort {
    public int partition(int[] arr, int low, int high) {
        int key = arr[low];
        while (low < high) {
            while (arr[high] >= key && high > low) {
                high--;
            }
            arr[low] = arr[high];
            while (arr[low] <= key && low= high){
            return ;
        }
        int index = partition(arr, low ,high);
        sort(arr, low ,index-1);
        sort(arr, index+1, high);

    }

    //      ,   ;   
    public static int[] generateRandomArray() {
        int length = (int) (Math.random() * 20) + 5;  //  5-20,       1-20
        int[] arr = new int[length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 20) + 1;
        }
        return arr;
    }

    public static void main(String[] args){
        QuickSort quickSort = new QuickSort();
        int testTime = 5;
        for (int i=0;i

python 버 전
def partitions(arr, low, high):
	key = arr[low]
    while(low < high):

        while(arr[high] >= key and high > low):
            high -= 1

        arr[low] = arr[high]
        while(arr[low] <= key and high > low):
            low += 1

        arr[high] = arr[low]

    arr[high] = key
    return high


def sort(arr, low, high):

    if (low >= high):
        return

    index = partitions(arr, low, high)
    sort(arr, low, index - 1)
    sort(arr, index + 1, high)

좋은 웹페이지 즐겨찾기