자바 각종 정렬 알고리즘

1) 분류:
1) 정렬 삽입 (정렬 직접 삽입, 힐 정렬)
2) 교환 정렬 (거품 정렬, 빠 른 정렬)
3) 정렬 선택 (정렬, 정렬 직접 선택)
4) 병합 정렬
5) 분배 정렬 (상자 정렬, 기수 정렬)
필요 한 보조 공간 최대: 병합 정렬
필요 한 보조 공간 최소: 쌓 기 정렬
평균 속도 가 가장 빠르다: 빠 른 정렬
불안정: 빠 른 정렬, 힐 정렬, 쌓 기 정렬.
1) 정렬 알고리즘 을 선택 할 때
1. 데이터 의 규모;  2. 데이터 의 유형;  3. 데이터 가 있 는 순서
일반적으로 데이터 규모 가 시간 에 비해 정렬 이나 거품 정렬 을 직접 삽입 하 는 것 을 선택해 야 한다.모든 정렬 알고리즘 은 데이터 양 시간 에 기본적으로 차 이 를 나타 내지 못 한다.데이터 의 유형 을 고려 합 니 다. 예 를 들 어 모두 정수 라면 통 으로 정렬 하 는 것 이 가장 좋 습 니 다.  데이터 의 기 존 순 서 를 고려 하면 빠 른 배열 은 불안정 한 정렬 (당연히 개선 할 수 있 습 니 다) 이 고 대부분 배 열 된 데이터 에 대해 빠 른 배열 은 대량의 불필요 한 절 차 를 낭비 할 수 있 습 니 다.데 이 터 는 양 이 매우 적 고 시작 은 이미 기본적으로 순 서 를 정 했 으 며 거품 이 나 는 것 이 가장 좋 은 선택 이다.우 리 는 빨리 배열 하 라 고 말 하 는 것 은 대량의 랜 덤 데이터 에서 빠 른 배열 효과 가 가장 이상 적 이라는 것 을 말한다.모든 상황 이 아니 라
3) 요약:
- 평균 시간 성능 에 따라 나 뉜 다.
     1) 시간 복잡 도가 O (nlogn) 인 방법 은 빠 른 정렬, 쌓 기 정렬 과 병합 정렬 이 있 는데 그 중에서 빠 른 정렬 이 가장 좋다.
     2) 시간 복잡 도가 O (n2) 인 것 은 정렬, 거품 정렬 과 간단 한 정렬 을 직접 삽입 하 는 것 이 가장 좋다.          키워드 에 대한 질서 있 는 기록 서열 이 특히 그렇다.
     3) 시간 복잡 도가 O (n) 인 정렬 방법 은 기수 정렬 뿐이다.
대기 기록 서열 이 키워드 순서에 따라 질서 가 있 을 때 정렬 과 거품 정렬 을 직접 삽입 하면 O (n) 의 시간 복잡 도 에 도달 할 수 있다.빠 른 정렬 에 있어 서 이것 은 가장 좋 지 않 은 상황 이다. 이때 의 시간 성능 은 O (n2) 로 탈바꿈 하기 때문에 가능 한 한 피해 야 할 상황 이다.정렬, 정렬, 정렬, 정렬 을 간단하게 선택 하 는 시간 성능 은 기록 시퀀스 의 키워드 분포 에 따라 달라 지지 않 습 니 다.
- 평균 적 인 공간 성능 에 따라 나 뉜 다 (정렬 과정 에서 필요 한 보조 공간 크기 를 말한다).
     1) 모든 간단 한 정렬 방법 (직접 삽입, 거품 과 간단 한 선택 포함) 과 정렬 된 공간 복잡 도 는 O (1) 이다.
     2) 빠 른 정렬 은 O (logn) 로 스 택 에 필요 한 보조 공간 입 니 다.
     3) 정렬 에 필요 한 보조 공간 이 가장 많 고 공간 복잡 도 는 O (n) 이다.
     4) 체인 기수 정렬 은 대기 열의 수미 지침 을 첨부 해 야 하 며 공간 복잡 도 는 O (rd) 이다.
- 정렬 방법의 안정성:
     1) 안정 적 인 정렬 방법 은 두 키워드 가 같은 기록 에 대해 서열 의 상대 적 인 위 치 를 가리 키 며 정렬 전과 정렬 을 거 친 후에 변 하지 않 는 다.
     2) 다 중 키워드 의 기록 서열 을 LSD 방법 으로 정렬 할 때 안정 적 인 정렬 방법 을 사용 해 야 한다.
     3) 불안정한 정렬 방법 에 대해 실례 를 들 어 설명 하면 된다.
     4) 빠 른 정렬, 힐 정렬 과 쌓 기 정렬 은 불안정한 정렬 방법 이다.
4) 정렬 삽입:
정렬 을 직접 삽입 하 는 것 을 포함 하여 힐 은 정렬 을 삽입 합 니 다.
정렬 직접 삽입: 정렬 된 질서 표 에 기록 을 삽입 합 니 다.
      1. sorted 배열 의 0 번 째 위치 에 데 이 터 를 넣 지 않 았 습 니 다.
      2, sorted 두 번 째 데이터 부터 처리 합 니 다:
              만약 이 데이터 가 앞의 데이터 보다 작다 면, 이 데 이 터 는 앞으로 이동 해 야 한 다 는 것 을 설명 한다.
              우선 이 데 이 터 를 sorted 의 0 번 째 위치 에 백업 하여 보초병 으로 삼 습 니 다.
              그리고 이 데 이 터 를 앞 에 있 는 데 이 터 를 뒤로 옮 깁 니 다.
              그리고 앞으로 검색 해서 삽입 위 치 를 찾 으 세 요.
              삽입 위 치 를 찾 은 후 0 위 치 를 말 하 는 그 데 이 터 는 대응 하 는 위 치 를 삽입 합 니 다.
O (n * n), 대기 기록 서열 이 정상 적 인 순서 일 때 시간 복잡 도 는 O (n) 로 높 아 집 니 다.
힐 정렬 (증분 정렬 diminishing increment sort 축소): 먼저 전체 대기 기록 서열 을 여러 개의 키 서열 로 나 누 어 각각 정렬 을 직접 삽입 하고 전체 서열 의 기록 이 기본적으로 질서 가 있 을 때 전체 기록 에 대해 직접 정렬 을 삽입 합 니 다.
정렬 Java 코드 삽입:

public class InsertionSort {

//       ：      ，       

     public void straightInsertionSort(double [] sorted){

         int sortedLen= sorted.length;

         for(int j=2;j<sortedLen;j++){

              if(sorted[j]<sorted[j-1]){

                   sorted[0]= sorted[j];//                           

                   sorted[j]=sorted[j-1];//        。

                   int insertPos=0;

                   for(int k=j-2;k>=0;k--){

                       if(sorted[k]>sorted[0]){

                            sorted[k+1]=sorted[k];

                       }else{

                            insertPos=k+1;

                            break;

                       }

                   }                 

                   sorted[insertPos]=sorted[0];

              }            

         }       

     }   

     public void shellInertionSort(double [] sorted, int inc){

         int sortedLen= sorted.length;

         for(int j=inc+1;j<sortedLen;j++ ){

              if(sorted[j]<sorted[j-inc]){

                   sorted[0]= sorted[j];//          

                  

                   int insertPos=j;               

                   for(int k=j-inc;k>=0;k-=inc){                    

                       if(sorted[k]>sorted[0]){

                            sorted[k+inc]=sorted[k];                          

                            //                 ，  ：

                            if(k-inc<=0){

                                 insertPos = k;

                            }

                       }else{

                            insertPos=k+inc;

                            break;

                       }

                   }                 

                   sorted[insertPos]=sorted[0];                  

              }

         }

     }

     public void shellInsertionSort(double [] sorted){

         int[] incs={7,5,3,1};

         int num= incs.length;

        

         int inc=0;

         for(int j=0;j<num;j++){

              inc= incs[j];         

              shellInertionSort(sorted,inc);           

         }       

     }   

     public static void main(String[] args) {

         Random random= new Random(6);

        

         int arraysize= 21;

         double [] sorted=new double[arraysize];

         System.out.print("Before Sort:");        

         for(int j=1;j<arraysize;j++){

              sorted[j]= (int)(random.nextDouble()* 100);

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

                  

         InsertionSort sorter=new InsertionSort();    

//       sorter.straightInsertionSort(sorted);

         sorter.shellInsertionSort(sorted);

        

         System.out.print("After Sort:");

         for(int j=1;j<sorted.length;j++){

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

     }

}

5) 교환 정렬:
거품 정렬 포함 빠 른 정렬.
거품 정렬 법: 이 알고리즘 은 일부 정렬 된 데 이 터 를 정렬 하 는 정렬 알고리즘 입 니 다.만약 당신 의 데이터 목록 에서 한두 개의 데이터 만 무질서 하 다 면, 이 알고리즘 을 사용 하 는 것 이 가장 빠 른 정렬 알고리즘 입 니 다.만약 당신 의 데이터 목록 의 데이터 가 무 작위 로 배열 되 어 있다 면, 이 방법 은 가장 느 린 알고리즘 이 될 것 입 니 다.따라서 이런 알고리즘 을 사용 하기 전에 신중 해 야 한다.이 알고리즘 의 핵심 사상 은 데이터 목록 을 스 캔 하여 어 지 러 운 순서 가 나타 나 는 두 개의 인접 한 항목 을 찾 는 것 이다.이 두 항목 을 찾 은 후에 항목 의 위 치 를 교환 한 후에 계속 스 캔 합 니 다.모든 항목 이 순서대로 배 열 될 때 까지 위의 조작 을 반복 합 니 다.
빠 른 정렬: 한 번 의 정렬 을 통 해 정렬 대기 기록 을 독립 된 두 부분 으로 나 눌 수 있 습 니 다. 그 중에서 일부 기록 의 키 워드 는 모두 다른 부분 에 기 록 된 키워드 보다 작 으 면 이 두 부분 기록 을 계속 정렬 하여 전체 서열 의 질 서 를 달성 할 수 있 습 니 다.구체 적 인 방법 은 두 개의 포인터 low, high 를 사용 하여 초기 값 을 각각 서열 의 머리 와 서열 의 끝 으로 설정 하고 pivotkey 를 첫 번 째 기록 으로 설정 하 는 것 입 니 다. 먼저 high 부터 pivotkey 보다 작은 기록 과 pivotkey 가 있 는 위 치 를 검색 하여 교환 한 다음 에 low 시작 에서 뒤로 pivotkey 보다 큰 기록 과 이때 pivotkey 가 있 는 위 치 를 검색 하여 교환 합 니 다.low = high 를 알 때 까지 반복 합 니 다.
교환 정렬 자바 코드:

public class ExchangeSort {

     public void BubbleExchangeSort(double [] sorted){

         int sortedLen= sorted.length;

         for(int j=sortedLen;j>0;j--){

              int end= j;

              for(int k=1;k<end-1;k++){

                   double tempB= sorted[k];

                   sorted[k]= sorted[k]<sorted[k+1]?

sorted[k]:sorted[k+1];

                   if(Math.abs(sorted[k]-tempB)>10e-6){

                       sorted[k+1]=tempB;

                   }

              }            

         }

     }   

     public void QuickExchangeSortBackTrack(double [] sorted,

int low,int high){

         if(low<high){

              int pivot= findPivot(sorted,low,high);

              QuickExchangeSortBackTrack(sorted,low,pivot-1);

              QuickExchangeSortBackTrack(sorted,pivot+1,high);

         }

     }

     public int findPivot(double [] sorted, int low, int high){        

         sorted[0]= sorted[low];    

         while(low<high){

              while(low<high && sorted[high]>= sorted[0])--high;

              sorted[low]= sorted[high];

              while(low<high && sorted[low]<=sorted[0])++low;

              sorted[high]= sorted[low];

         }

         sorted[low]=sorted[0];

         return low;

     }

     public static void main(String[] args) {

         Random random= new Random(6);

        

         int arraysize= 21;

         double [] sorted=new double[arraysize];

         System.out.print("Before Sort:");        

         for(int j=1;j<arraysize;j++){

              sorted[j]= (int)(random.nextDouble()* 100);

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

                  

         ExchangeSort sorter=new ExchangeSort();      

//       sorter.BubbleExchangeSort(sorted);

         sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize-1);

         System.out.print("After Sort:");

         for(int j=1;j<sorted.length;j++){

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

     }

}

6) 정렬 선택:
정렬
직접 정렬 선택: i 번 째 선택 i 에서 array. Length - 1 중간 에 가장 작은 값 을 i 위치 에 놓 습 니 다.
쌓 기 정렬: 우선, 배열 안에 층 차 를 옮 겨 다 니 는 순서 로 완전 이 진 트 리 를 놓 습 니 다.마지막 비 단말기 노드 에서 앞으로 조정 하고 뿌리 노드 에 도착 할 때 까지 뿌리 노드 를 제외 한 모든 비 단말기 노드 는 쌓 인 조건 을 만족 시 켰 기 때문에 뿌리 노드 를 조정 하여 전체 나무 가 쌓 인 조건 을 만족 시 켜 야 한다. 그래서 뿌리 노드 부터 그의 아들 들 을 따라 아래로 내 려 가 야 한다.(최대 무 더 기 는 가장 큰 아들 을 따라 가 고, 가장 작은 무 더 기 는 가장 작은 아들 을 따라 간다). 메 인 프로그램 에 서 는 먼저 마지막 비 터미널 노드 부터 뿌리 까지 조정 하여 힙 을 만 든 다음 힙 의 뿌리 를 뒤로 놓는다.(즉, 매번 나무의 크기 는 변 하지만 루트 는 1 의 위치 에 있어 서 아들 들 의 index 를 계산 하기에 편리 하기 때문에 오름차 순 으로 배열 해 야 한다 면 점차적으로 큰 지붕 을 쌓 아야 한다. 뿌리 노드 가 하나씩 뒤에 놓 여 있 기 때문이다. 내림차 순 으로 배열 하면 작은 지붕 을 만들어 야 한다)
코드 중의 문제: 때로는 두 번 째 와 세 번 째 순서 가 틀 릴 때 가 있다.
정렬 Java 코드 선택:

public class SelectionSort {

     public void straitSelectionSort(double [] sorted){

         int sortedLen= sorted.length;

         for(int j=1;j<sortedLen;j++){

              int jMin= getMinIndex(sorted,j);

              exchange(sorted,j,jMin);

         }

     }

     public void exchange(double [] sorted,int i,int j){

         int sortedLen= sorted.length;

         if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0){

              double temp= sorted[i];

              sorted[i]=sorted[j];

              sorted[j]=temp;

         }

     }

     public int getMinIndex(double [] sorted, int i){

         int sortedLen= sorted.length;

        

         int minJ=1;

         double min= Double.MAX_VALUE;

         for(int j=i;j<sortedLen;j++){

              if(sorted[j]<min){

                   min= sorted[j];

                   minJ= j;

              }

         }

         return minJ;

     }

        

     public void heapAdjust(double [] sorted,int start,int end){

         if(start<end){

              double temp= sorted[start];

//                j<end     ，j<=end   ：

              for(int j=2*start;j<end;j *=2){

                   if(j+1<end && sorted[j]-sorted[j+1]>10e-6){

                       ++j;         

                   }

                   if(temp<=sorted[j]){

                       break;

                   }            

                   sorted[start]=sorted[j];

                   start=j;          

              }

              sorted[start]=temp;

         }

     }   

     public void heapSelectionSort(double [] sorted){

         int sortedLen = sorted.length;

        

         for(int i=sortedLen/2;i>0;i--){

              heapAdjust(sorted,i,sortedLen);

         }

         for(int i=sortedLen;i>1;--i){           

              exchange(sorted,1,i);           

              heapAdjust(sorted,1,i-1);           

         }       

     }

     public static void main(String [] args){

         Random random= new Random(6);

        

         int arraysize=9;

         double [] sorted=new double[arraysize];

         System.out.print("Before Sort:");        

         for(int j=1;j<arraysize;j++){

              sorted[j]= (int)(random.nextDouble()* 100);

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

                  

         SelectionSort sorter=new SelectionSort();    

//       sorter.straitSelectionSort(sorted);

         sorter.heapSelectionSort(sorted);

        

         System.out.print("After Sort:");

         for(int j=1;j<sorted.length;j++){

              System.out.print((int)sorted[j]+" ");

         }   

         System.out.println();

     }

}

7) 병합 정렬:
두 개 또는 두 개 이상 의 질서 표를 새로운 질서 표 로 조합 합 니 다. 병합 정렬 은 하나의 보조 배열 을 사용 해 야 합 니 다. 크기 는 원래 배열 과 같 고 재 귀 방법 입 니 다. 매번 목표 서열 을 두 개의 서열 로 분해 하여 각각 두 개의 하위 서열 을 정렬 한 다음 에 두 개의 정렬 된 하위 서열 merge 를 함께 합 니 다.
Java 코드 병합 정렬:

public class MergeSort { 

     private double[] bridge;//    

     public void sort(double[] obj){

         if (obj == null){

              throw new NullPointerException("

The param can not be null!");

         }

         bridge = new double[obj.length]; //        

         mergeSort(obj, 0, obj.length - 1); //     

         bridge = null;

     }

     private void mergeSort(double[] obj, int left, int right){

         if (left < right){

              int center = (left + right) / 2;

              mergeSort(obj, left, center);

              mergeSort(obj, center + 1, right);

              merge(obj, left, center, right);

         }

     }

     private void merge(double[] obj, int left,

int center, int right){

         int mid = center + 1;

         int third = left;

         int tmp = left;

         while (left <= center && mid <= right){

//                 

              if (obj[left]-obj[mid]<=10e-6){

                   bridge[third++] = obj[left++];

              } else{

                   bridge[third++] = obj[mid++];

              }

         }

 

         //             

         while (mid <= right){

              bridge[third++] = obj[mid++];

         }

         while (left <= center){

              bridge[third++] = obj[left++];

         }

         //               

         copy(obj, tmp, right);

     }

     private void copy(double[] obj, int left, int right)

     {

         while (left <= right){

              obj[left] = bridge[left];

              left++;

         }

     }

     public static void main(String[] args) {

         Random random = new Random(6);

 

         int arraysize = 10;

         double[] sorted = new double[arraysize];

         System.out.print("Before Sort:");

         for (int j = 0; j < arraysize; j++) {

              sorted[j] = (int) (random.nextDouble() * 100);

              System.out.print((int) sorted[j] + " ");

         }

         System.out.println();

 

         MergeSort sorter = new MergeSort();

         sorter.sort(sorted);

        

         System.out.print("After Sort:");

         for (int j = 0; j < sorted.length; j++) {

              System.out.print((int) sorted[j] + " ");

         }

         System.out.println();

     }

}

8) 기수 정렬:
10 개의 보조 대기 열 을 사용 하여 최대 수의 숫자 자릿수 가 x 라 고 가정 하면 모두 x 회 를 하고 한 자릿수 부터 앞으로 이동 하 며 i 위의 숫자 크기 를 근거 로 데 이 터 를 보조 대기 열 에 넣 고 해결 한 후에 회수 합 니 다.다음 부 터 는 높 은 자리 에서 시작 하 는 숫자 를 근거 로
Vector 를 보조 대기 열 로 하고 기수 로 정렬 된 자바 코드:

public class RadixSort {

     private int keyNum=-1;   

     private Vector<Vector<Double>> util;

    

     public void distribute(double [] sorted, int nth){       

         if(nth<=keyNum && nth>0){

              util=new Vector<Vector<Double>>();

              for(int j=0;j<10;j++){

                   Vector <Double> temp= new Vector <Double>();

                   util.add(temp);

              }            

              for(int j=0;j<sorted.length;j++){

                   int index= getNthDigit(sorted[j],nth);

                   util.get(index).add(sorted[j]);

              }

         }

     }   

     public int getNthDigit(double num,int nth){

         String nn= Integer.toString((int)num);

         int len= nn.length();

         if(len>=nth){

              return Character.getNumericValue(nn.charAt(len-nth)); 

         }else{

              return 0;

         }            

     }

     public void collect(double [] sorted){

         int k=0;

         for(int j=0;j<10;j++){

              int len= util.get(j).size();

              if(len>0){

                   for(int i=0;i<len;i++){

                       sorted[k++]= util.get(j).get(i);

                   }

              }

         }

         util=null;

     }

     public int getKeyNum(double [] sorted){    

         double max= Double.MIN_VALUE;

         for(int j=0;j<sorted.length;j++){

              if(sorted[j]>max){

                   max= sorted[j];

              }

         }       

         return Integer.toString((int)max).length();

     }

     public void radixSort(double [] sorted){

         if(keyNum==-1){            

              keyNum= getKeyNum(sorted);

         }

         for(int i=1;i<=keyNum;i++){

              distribute(sorted,i);

              collect(sorted);           

         }

     }

     public static void main(String[] args) {

         Random random = new Random(6);

 

         int arraysize = 21;

         double[] sorted = new double[arraysize];

         System.out.print("Before Sort:");

         for (int j = 0; j < arraysize; j++) {

              sorted[j] = (int) (random.nextDouble() * 100);

              System.out.print((int) sorted[j] + " ");

         }

         System.out.println();

 

         RadixSort sorter = new RadixSort();

         sorter.radixSort(sorted);

        

         System.out.print("After Sort:");

         for (int j = 0; j < sorted.length; j++) {

              System.out.print((int) sorted[j] + " ");

         }

         System.out.println();

     }

}

= = = = = 요약: 상기 자바 코드 에서 기본적으로 double 배열 을 사용 합 니 다. 다른 배열 을 사용 하려 면 double 배열 을 Comparable 인터페이스 배열 로 바 꾸 고 Comparable 인 터 페 이 스 를 실현 한 모든 것 을 사용 할 수 있 습 니 다.C++ 에 서 는 템 플 릿 류 로 이 문 제 를 해결 합 니 다.