Java를 사용하여 정렬 알고리즘을 구현하는 방법

불안정한 정렬

선택 정렬:
1차 비교 후 얻은 가장 작은 레코드를 첫 번째 레코드의 위치로 바꾼 후, 첫 번째 레코드를 제외한 레코드에 대해 2차 비교를 수행하고 그 결과 가장 작은 레코드가 두 번째 레코드와 교환됩니다.
시간 복잡도: O(n^2)
공간 복잡도: O(1)

    public static void selectSort(int[] arr){        
    if (arr == null || arr.length == 0)            
    return;        
    int len = arr.length;        
    for (int i = 0; i < len; i++) {            
        int min = arr[i];            
        int index = i;            
        for (int j = i+1; j < len; j++) {                
        if (arr[j] < min) {                    
            min = arr[j];
          index = j;
          }
       }
       arr[index] = arr[i];
       arr[i] = min;
     }
    }

빠른 정렬:
주어진 레코드 세트에 대해 각 정렬 단계 후에는 시퀀스가 두 부분으로 나누어져 전자 부분의 모든 레코드가 후자 부분의 모든 레코드보다 작으며 그 전후 두 부분의 레코드가 빠르게 정렬됩니다.
시간 복잡도: O(nlogn ) 최악의 경우: O(n^2 )
공간 복잡도: O(nlogn)

    public int Partition(int[] a,int start,int end){        int std = a[start];
        while (start < end){
             while(start < end && a[end] >= std)                 
             end--;
             a[start] = a[end];
             while(start < end && a[start] <= std)                 
             start++;
             a[end] = a[start];
        }
        a[start] = std;
        return start;
    }
    public void quickSort(int[] a,int start,int end){        
            if(start >= end){
            return;
        }
        int index = Partition(a,start,end);
        quickSort(a,start,index-1);
        quickSort(a,index+1,end);
    }

힙 정렬: 완전한 이진 트리
이진 트리를 큰 최상위 힙으로 조정한 다음 힙의 마지막 요소를 최상위 힙과 교환 힙의 요소(즉, 이진 트리의 루트 노드), 힙의 마지막 요소가 가장 큰 레코드이고 첫 번째 n-1 요소가 가장 큰 최상위 힙으로 조정되고 그 다음에는 힙의 최상위 요소가 조정됩니다. 힙은 현재 힙의 마지막 요소와 교환되어 두 번째로 큰 레코드를 얻습니다. 조정될 때까지 이 과정을 반복합니다. 힙에 요소가 하나만 남을 때까지 해당 요소는 최소 레코드가 될 수 있습니다.
시간 복잡도: O(nlogn)
공간 복잡도: O(1)

   public void HeapSort(int[] a){        
            for (int i = a.length/2 - 1; i >= 0 ; i--) {
            HeapAdjust(a,i,a.length-1);
        }        
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a,0,i);
            HeapAdjust(a,0,i-1);
        }
    }    
    private void swap(int[] a, int i, int j) {        
            int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }    
    public void HeapAdjust(int[] arr,int s,int len){        
            int tmp = arr[s];        
            for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {            
                    if (i < len && arr[i] < arr[i+1]){
                i++;
            }            
            if (tmp > arr[i])                
            break;
            arr[s] = arr[i];
            s = i; //s记录被替换的子结点的索引
        }
        arr[s] = tmp;
    }

안정 정렬

직접 삽입 정렬:
첫 번째 레코드는 자체적으로 순서가 지정된 시퀀스로 간주될 수 있으며 나머지 레코드는 호출됩니다. 순서가 없는 시퀀스. 그런 다음 두 번째 레코드부터 시작하여 현재 처리 중인 레코드를 이전 정렬된 시퀀스에 레코드 크기에 따라 순서대로 삽입하고 마지막 레코드가 정렬된 시퀀스에 삽입될 때까지
시간 복잡도: O(n^2)
공간 복잡도 : O(1)

    public static void insertSort(int[] arr){        
            if (arr == null || arr.length == 0)            
            return;        
            int len = arr.length;        
            for (int i = 1; i < len; i++) {            
            int curr = arr[i];            
            int j = i;            
            if (arr[j-1] > curr){                
                while (j > 0 && arr[j-1]> curr){
                arr[j] = arr[j-1];
                j--;
                }
            }
          arr[j] = curr;
        }
    }

버블 정렬:
첫 번째 레코드부터 시작하여 인접한 두 레코드를 순서대로 비교합니다. 이전 레코드가 다음 레코드보다 크면 위치가 바뀌며 비교 및 ​​전치 후에 n개 레코드 중 가장 큰 레코드가 위치하게 됩니다. n번째 레코드 비트를 생성한 다음 이전 n-1 레코드에 대해 두 번째 비교를 수행하고 비교할 레코드가 하나만 남을 때까지 프로세스를 반복합니다
시간 복잡도: O(n^2)
공간 복잡도: O(1)

    public void bubbleSort(int[] arr){        
            boolean flag = true;        
            for (int i = 0; i < arr.length && flag; i++) {
            flag = false;            
            for (int j = 0; j < arr.length - i - 1; j++) {                
                    if (arr[j] > arr[j+1]){
                flag = true;
                swap(arr,j,j+1);
                }
            }
        }
    }    
    private void swap(int[] arr, int j, int i) {        
            int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

병합 정렬: 재귀: 재귀, 합집합: 개별 데이터의 순서대로 병합
길이가 1인 인접한 두 하위 시퀀스를 모두 병합하여 길이가 2 또는 1인 n/2개의 정렬된 하위 시퀀스를 얻은 다음 두 개를 병합하고 정렬된 시퀀스를 얻을 때까지 이 프로세스를 반복합니다. 시간 복잡도: O(nlogn)
공간 복잡도: O(n)

   public static void mergeSort(int[] arr,int begin,int end){        
              int mid = (begin+end)/2;        
              if (begin < end){
            mergeSort(arr,begin,mid);
            mergeSort(arr,mid+1,end);
            Merge(arr,begin,end,mid);
        }
    }    
    public static void Merge(int[] arr,int begin,int end,int mid){        
            int[] temp = new int[end-begin+1];        
            int i = begin;        
            int j = mid+1;        
            int k=0;        
            while (i <= mid && j <= end){            
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }        
        while (i <= mid){
            temp[k++] = arr[i++];
        }        
        while (j <= end){
            temp[k++] = arr[j++];
        }        
        for (int m = 0;m < temp.length;m++){
            arr[m+begin] = temp[m];
        }
    }

위 내용은 Java를 사용하여 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!