자바 는 빠 른 정렬, 병합 정렬, 쌓 기 정렬 과 힐 정렬 을 실현 합 니 다.

빠 른 정렬
알고리즘 사상
1. 배열 의 첫 번 째 요 소 를 target 으로 하고 두 개의 포인터 i 와 j 를 정의 합 니 다.2. 포인터 i, 왼쪽 에서 오른쪽으로 첫 번 째 target 보다 큰 요 소 를 찾 습 니 다. 포인터 j 는 오른쪽 에서 왼쪽으로 첫 번 째 target 보다 작은 요 소 를 찾 습 니 다. i 가 j 보다 작 으 면 i, j 포인터 가 가리 키 는 요소 의 값 을 교환 합 니 다.3. 포인터 i 는 왼쪽 에서 오른쪽으로 계속 검색 합 니 다. 포인터 j 는 오른쪽 에서 왼쪽으로 계속 검색 합 니 다. 2 단계 에서 한 번 멈 춘 후에 i > j 를 반복 합 니 다. 이때 target 과 j 가 가리 키 는 요소 의 위 치 를 교환 하면 target 왼쪽 요소 가 모두 작 고 target 오른쪽 요소 가 모두 그것 보다 크다 는 것 을 보증 할 수 있 습 니 다.4. target 좌우 두 부분 으로 재 귀적 하여 하나의 요소 만 남 을 때 까지 합 니 다.평균, 가장 좋 은 시간 복잡 도: O (nlgn) 최 악의 시간 복잡 도: O (n ^ 2) 공간 복잡 도: O (1) (필요 한 공간 은 O (n) 라 고 할 수 있 습 니 다. 재 귀적 호출 시 스 택 의 비용 이 있 기 때문에 최 악의 경우 O (n), 평균 O (logn)) 입 니 다.
코드 구현

public class QuickSort {
    public static void quickSort(int[] R, int low, int high){
        if(low >= high)
            return;
        int i = low+1;
        int j = high;
        while(iwhile(R[i]<=R[low] && iwhile(R[j]>R[low] && j>low)
                j--;

            if(iint temp = R[i];
                R[i] = R[j];
                R[j] = temp;
            }

        }
        int temp = R[j];
        R[j] = R[low];
        R[low] = temp;

        quickSort(R, low, j - 1);
        quickSort(R , j+1, high);
    }

    public static void main(String[] args) {

        int[] arr = new int[10000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.abs(r.nextInt(1000));
        }

        quickSort(arr, 0, arr.length - 1);
        if (check(arr)) System.out.println("right");
        else System.out.println("wrong");

    }
    public static boolean check(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                System.out.println(arr[i - 1] + "   " + arr[i]);
                System.out.println("position is " + i);
                return false;
            }
        }
        return true;
    }
}

정렬
알고리즘 사상
1. 원래 의 배열 을 계속 2 분 으로 나 누 어 잎 노드 에 하나의 요소 만 남 을 때 까지 2. 같은 부모 노드 에 속 하 는 두 아들 을 질서 있 는 배열 로 합 친다. 이 부모 노드 는 질서 있 는 배열 로 바 꾸 고 3. 재 귀적 인 구분 과 합병 하면 최종 질서 있 는 배열 의 평균, 가장 좋 고 최 악의 시간 복잡 도 를 얻 을 수 있다. O (nlgn) 공간 복잡 도: O (n)

public class mergeSort {
    public static void merge(int[] R, int low1, int high1, int low2, int high2){
        int i = low1;
        int j = low2;
        int[] temp = new int[high1-low1+1+high2-low2+1];
        int index = 0;
        while(i<=high1 && j<=high2){
            if(R[i]<=R[j]){
                temp[index] = R[i];
                i ++;
            }
            else{
                temp[index] = R[j];
                j ++;
            }
            index ++;
        }

        if(i>high1){
            while(j<=high2){
                temp[index] = R[j];
                j ++;
                index ++;
            }
        }

        if(j>high2){
            while(i<=high1){
                temp[index] = R[i];
                i ++;
                index ++;
            }
        }

        int m = low1;
        for(int k=0;kpublic static void MergeSort(int[] R, int low, int high){
        if(low >= high)
            return;
        int mid = (low+high)/2;
        MergeSort(R, low, mid);
        MergeSort(R, mid+1, high);
        merge(R, low, mid, mid+1, high);
    }

    public static void main(String[] args){
        int[] R = {5,7,3,19,4,9,17,15,12,31,23,30,5,8,1,17,16,5,3};
        MergeSort(R, 0, R.length-1);
        for(int i=0;iout.printf("%d ",R[i]);
    }
}

더미 정렬

public class HeapSort {

    public static void rebuildHeap(int[] A, int start, int end){
        int i = start;
        while(i<=end/2 -1) {
            if(A[i]>A[2*i+1] && 2*i+2A[2*i+2]|| A[i]>A[2*i+1] && 2*i+2>end )
                break;
            else{
                if(2*i+2if (A[2*i + 1] >= A[2*i + 2]) {
                        swap(A, i, 2 * i + 1);
                        i = 2*i + 1;
                    }
                    else {
                        swap(A,i,2*i +2);
                        i = 2*i + 2;
                    }
                }
                else{
                    swap(A, i, 2 * i + 1);
                    i = 2*i + 1;
                }
            }
        }
    }

    public static void HeapSort(int[] A){
        int n = A.length;
        int start = n/2 - 1;
        for(int i=start;i>=0;i-- ){
            rebuildHeap(A, i, n-1);
        }
        for(int j=n-1;j>0;j--){
            swap(A, 0, j);
            rebuildHeap(A,0,j-1);
        }
    }
    public static void swap(int[] A,int a,int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
    public static void main(String[] args){
        int[] A = new int[]{6,12,3,7,8,2,9,11,35,12,8,22};
        HeapSort(A);
        for(int i:A){
            System.out.println(i);
        }
    }
}

힐 정렬

public class ShellSort {
    public static void shellSort(int[] A){
        for(int gap = A.length/2; gap > 0; gap/=2)
            for(int i=gap;ifor(int j=i;j>=gap;j-=gap){
                    if(A[j]int temp = A[j];
A[j] = A[j-gap];
A[j-gap] = temp;
}
else break;
}
}
}
public static void main(String[] args){
int[] A = new int[]{6,2,12,3,5,14,22,24,7};
shellSort(A);
for(int x:A)
System.out.println(x);
}
}