자바 8 가지 정렬 알고리즘 구현 예시 코드

거품 정렬 O(n2)
두 개의 수가 비교적 크 고,비교적 큰 수가 가라앉 고,비교적 작은 수가 솟 아 오른다.

public static void bubbleSort(int[] a) {
    //    
    int temp;
    //i     ,           ，5     5 
    for (int i = 0; i < a.length; i++) {
      //          ，j         
      for (int j = a.length - 1; j > i; j--) {
        //         
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        }
      }
    }
  }

정렬 O 선택(n2)
길이 가 N 인 무질서 한 배열 에서 처음으로 n-1 개의 수 를 옮 겨 다 니 며 가장 작은 수 치 를 찾 아 첫 번 째 요소 와 교환 합 니 다.
두 번 째 는 n-2 개의 수 를 옮 겨 다 니 며 가장 작은 수 치 를 찾 아 두 번 째 요소 와 교환 합 니 다.
。。。
n-1 번 옮 겨 다 니 며 최소 수 치 를 찾 아 n-1 번 요소 와 교환 하고 정렬 이 완료 되 었 습 니 다.

public static void selectSort(int[] a) {
    //    
    int temp;
    //i     ,              ，5     5 
    for (int i = 0; i < a.length; i++) {
      //     
      int min = i;
      for (int j = i + 1; j < a.length; j++) {
        if (a[min] > a[j]) {
          min = j;
        }
      }
      temp = a[i];
      a[i] = a[min];
      a[min] = temp;
    }
  }

정렬 O 삽입(n2)
정렬 할 그룹의 수 에서 n-1 개의 수가 이미 정렬 되 었 다 고 가정 하고,현재 n 개의 수 를 앞의 질서정연 한 수열 에 꽂 아 n 개의 수도 정렬 되 어 있다.이렇게 모든 순서 가 정 해 질 때 까지 반복 한다.

public static void insertSort(int[] a) {
    int temp;
    //i     ,          ，     a[i]
    //     a[0]        ，  a.length-1 ，       a[a.length-1]  a[0]~a[a.length-2]
    for (int i = 0; i < a.length - 1; i++) {
      //a[j]       ， a[j] a[0]  
      for (int j = i + 1; j > 0; j--) {
        //       ，    
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        } else {
          //    a[0]~a[i]    ，a[i+1] a[i]   ，        
          break;
        }
      }
    }
  }

힐 정렬 O(n 1.5)
정렬 할 그룹의 수 에서 특정한 증 량 에 따라 몇 개의 하위 서열 로 나 누고 하위 서열 에 대해 각각 삽입 정렬 을 한다.
그리고 점차 증 량 을 줄 이 고 상술 한 과정 을 반복 한다.증분 이 1 일 때 까지 데이터 시퀀스 가 기본적으로 질서 가 있 고 마지막 으로 삽입 정렬 을 합 니 다.

public static void shellSort(int[] a) {
    int temp;
    int d = a.length;
    for (; ; ) {
      d = d / 2;
      //          
      for (int k = 0; k < d; k++) {
        //             ，   a[k+d],a[k+2d]...a[k+n*d]
        for (int i = k + d; i < a.length; i += d) {
          // a[j]       ， a[j] a[0]  ,   d
          for (int j = i; j > k; j -= d) {
            //       ，    
            if (a[j] < a[j - d]) {
              temp = a[j];
              a[j] = a[j - d];
              a[j - d] = temp;
            } else {
              //    a[0]~a[i]    ，a[i+1] a[i]   ，        
              break;
            }
          }
        }
      }
      if (d == 1) {
        break;
      }
    }
  }

빠 른 정렬 O(N*logN)
먼저 수열 에서 하나의 수 를 베이스 값 으로 꺼 내기;
이 수 보다 작은 수 를 모두 왼쪽 에 놓 고 크 거나 같은 수 를 모두 오른쪽 에 놓 습 니 다.
구간 별로 한 개의 수 밖 에 없 을 때 까지 좌우 두 개의 작은 수열 에 두 번 째 단 계 를 반복 한다.

public void quickSort(int a[], int l, int r) {
    //        
    if (l >= r) {
      return;
    }
    int i = l;
    int j = r;
    //         
    int base = a[l];
    while (i < j) {
      //          base  ，        ，        i/j  
      while (i < j && a[j] > base) {
        j--;
      }
      //          base  ,        ，        i/j  
      while (i < j && a[i] < base) {
        i++;
      }
      //  
      if (i < j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
      }
    }
    //      i      
    a[i] = base;
    // i   i      
    quickSort(a, l, i - 1);//    
    quickSort(a, i + 1, r);//    
  }

정렬 O 병합(N*logN)
병합 정렬 은 병합 작업 에 있어 서 효과 적 인 정렬 알고리즘 입 니 다.이 알고리즘 은 분 치 법 을 채택 한 매우 전형 적 인 응용 이다.
우선 두 개의 질서 있 는 수열 을 어떻게 합 칠 것 인 가 를 고려 해 보 자.
이것 은 매우 간단 합 니 다.두 수열 의 첫 번 째 숫자 를 비교 하면 작은 사람 이 먼저 가 고 가 져 온 후에 해당 수열 에서 이 수 를 삭제 합 니 다.
그리고 비교 해 보 세 요.수열 이 비어 있 으 면 다른 수열 의 데 이 터 를 순서대로 꺼 내 면 됩 니 다.

private static void mergeSort(int[] a, int first, int last, int temp[]) {
    if (first < last) {
      //   
      int middle = (first + last) / 2;
      //      
      mergeSort(a, first, middle, temp);
      //      
      mergeSort(a, middle + 1, last, temp);
      //      
      mergeArray(a, first, middle, last, temp);
    }
  }

  private static void mergeArray(int a[], int first, int middle, int end, int temp[]) {
    int i = first;
    int m = middle;
    int j = middle + 1;
    int n = end;
    int k = 0;
    while (i <= m && j <= n) {
      if (a[i] <= a[j]) {
        temp[k] = a[i];
        k++;
        i++;
      } else {
        temp[k] = a[j];
        k++;
        j++;
      }
    }
    while (i <= m) {
      temp[k] = a[i];
      k++;
      i++;
    }
    while (j <= n) {
      temp[k] = a[j];
      k++;
      j++;
    }
    for (int r = 0; r < k; r++) {
      a[first + r] = temp[r];
    }
  }

쌓 기 정렬 O(N*logN)
이러한 데이터 구 조 를 이용 하여 디자인 된 정렬 알고리즘더 미 는 완전 이 진 트 리 와 비슷 한 구조 이 고 쌓 인 성질 을 만족 시 킵 니 다.즉,하위 노드 의 키 나 색인 은 항상 부모 노드 보다 작 습 니 다.

public static void heapSort(int a[]) {
    //          （   ）     -1  
    for (int i = a.length - 1; i > 0; i--) {
      //     （   ）
      buildHeap(a, i);
      //          （   ）  
      swap(a, 0, i);
    }
  }

  //     （   ）
  public static void buildHeap(int a[], int lastIndex) {
    //            /2-1，  i      0 ，    
    for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
      //         ，          
      int left = i * 2 + 1;
      int right = i * 2 + 2;
      //max           
      int max = left;
      if (right <= lastIndex) {
        if (a[left] < a[right]) {
          max = right;
        }
      }
      //    
      if (a[i] < a[max]) {
        swap(a, i, max);
      }
    }
  }

  //   
  public static void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

기수 정렬 O(d(n+r)
[d 대표 키 워드 는 d 비트,n 대표 n 개 기록,r 대표 r 개 빈 대기 열]
기수 정렬(radix sort)은 흔히 볼 수 있 는 비교 정렬 에 비해 기수 정렬 은 분배 식 정렬 입 니 다.즉,모든 숫자 를 있 는 위치 에 분배 한 다음 에 원래 배열 로 덮어 정렬 하 는 과정 입 니 다.

public static void radixSort(int[] a) {
    //  
    int digit = 1;
    //           
    int newIndex = 0;
    //            ，      10 0~9，                     
    int[][] container = new int[10][a.length];
    //             ，   10，            ，          8，counter.length=5 ，counter[8]   
    int counterLength = 10;
    if (a.length > 10) {
      counterLength = a.length;
    }
    int[] counter = new int[counterLength];
    //         ，       
    int max = a[0];
    int maxDigit = 0;
    for (int i = 0; i < a.length; i++) {
      if (a[i] > max) {
        max = a[i];
      }
    }
    while (max > 0) {
      max /= 10;
      maxDigit++;
    }
    //       
    while (digit <= maxDigit) {
      //         ,container[remainder]，            counter[remainder]
      for (int num : a) {
        int remainder = (num / digit) % 10;
        container[remainder][counter[remainder]] = num;
        counter[remainder]++;
      }
      //                    
      for (int i = 0; i < 10; i++) {
        for (int j = 0; j < counter[i]; j++) {
          a[newIndex] = container[i][j];
          newIndex++;
        }
        counter[i] = 0;
      }
      digit *= 10;
      newIndex = 0;
    }
  }

이상 은 자바 가 8 가지 정렬 알고리즘 을 실현 하 는 예제 코드 의 상세 한 내용 입 니 다.자바 가 8 가지 정렬 알고리즘 을 실현 하 는 데 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 십시오!