자바 버 전 10 대 정렬 고전 알고리즘:전체 코드

10 대 정렬 알고리즘 비교

마지막 열의 안정성 에 대해 저 는 조금 설명 하 겠 습 니 다.예 를 들 어 서열:1,2,4,2,6 정렬,서열 에 두 개의 2 가 존재 합 니 다.만약 에 우리 가 이 두 개의 2 표 시 를(그들 둘 이 다 르 게)하고 정렬 한 후에 앞의 2 가 앞 에 있 으 면 이런 정렬 은 안정 적 이 고 불안정 하 다 고 합 니 다.
거품 정렬
간단하게 설명:원 리 는 알고리즘 이름 처럼 물 속 의 기포 처럼 매번 에 가장 크 거나 가장 작은 것 을 맨 뒤에 놓 습 니 다.그러면 모두 n-1 번 이 필요 하면 정렬 을 완성 할 수 있 습 니 다.이것 이 바로 1 층 순환 입 니 다.두 번 째 순환 은 고정 되 지 않 은 숫자(배열 왼쪽 의 숫자 로 이해 합 니 다.각 층 의 순환 은 가장 크 거나 가장 작은 수 를 맨 오른쪽 으로 올 려 고정 시 키 기 때문에 다음 에는 이 수 를 옮 겨 다 니 지 않 습 니 다).두 층 의 순환 이 끝 난 후에 모든 수 는 순 서 를 매 깁 니 다.2 층 순환 으로 인해 거품 정렬 알고리즘 의 시간 복잡 도 는 O(n 2 n^{2}n2)로 매우 높 은 시간 복잡 도 입 니 다.저 는 아래 코드 를 최적화 시 켰 고 표지 위 치 를 추 가 했 습 니 다.만약 에 지난번 순환 이 교환 되 지 않 았 다 면 질서 가 있 었 고 계속 하지 않 았 다 는 것 을 설명 합 니 다.반대로 다음 라운드 가 계속 진행 되 었 습 니 다.

전체 코드:

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: BubbleSort
 * @Description:     
 * @author:       
 * @date: 2021-06-24 10:31
 */
public class BubbleSort {
    //    
    public static void bubbleSort(int[] arr, boolean ascending) { //exchange               
        boolean flag = true; //      ，            ，   ，        ，    ，        
        for (int i = 1; i < arr.length && flag; i++) { //    ，     ，   n-1 ，      ，  flag=false                 
            /*System.out.print(" "+i+"   ：");
            for (int i1 : arr) {
                System.out.print(i1+" ");
            }
            System.out.println();*/
            flag = false; //     
            for (int j = 0; j < arr.length - i; j++) {
                if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //        
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
        }
    }
    //     --        
    public static void bubbleSort(int[] arr) {
        bubbleSort(arr, true);
    }
}

테스트 코드:
오름차 순 정렬(작은 것 부터 큰 것 까지)

package com.keafmd.Sequence;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
 * Keafmd
 *
 * @ClassName: Sort
 * @Description:       
 * @author:       
 * @date: 2021-06-16 21:27
 */
public class Sort {
    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;
        //      
        System.out.println("      :");
        temparr = nums.clone();
        BubbleSort.bubbleSort(temparr);
        //    
        //BubbleSort.bubbleSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
    }
}

실행 결과:
테스트 거품 정렬:-66-13-1 4 9 12 25 26 34 47 58 99 162 10093
내림차 순 정렬(큰 것 부터 작은 것 까지)

//      
System.out.println("      :");
temparr = nums.clone();
BubbleSort.bubbleSort(temparr,false);
for (int i = 0; i < temparr.length; i++) {
    System.out.print(temparr[i] + " ");
}
System.out.println();

실행 결과:
테스트 거품 정렬:10093 162 99 58 47 34 26 25 12 9 1-1-13-66
다음 몇 가지 알고리즘 의 테스트 는 바로 다음 클래스 이름과 방법 명(상응하는 정렬 알고리즘 으로 바 꾸 기)을 바 꾸 었 고,내림차 순 을 원한 다 면 그룹 뒤에 false 를 전달 하면 된다.나 는 일일이 복사 하지 않 을 것 이다.나 는 맨 아래 에 모든 알고리즘 을 포함 한 테스트 류 를 제시 하고 필요 한 것 은 스스로 취하 면 된다.
빠 른 정렬
간단 한 설명:빠 른 순 서 는 매번 에 하나의 기점(첫 번 째 요소)을 찾 은 다음 에 두 보초병 이다.하 나 는 맨 앞에서 뒤로 가 고 하 나 는 마지막 면 에서 앞으로 가 는 것 이다.만약 에 뒤에 있 는 보초병 이 기점 보다 큰 숫자 를 찾 아 멈 추 면 앞 에 있 는 보초병 이 기점 보다 큰 숫자 를 찾 아 멈 춘 다음 에 두 보초병 이 찾 은 수 를 교환 하 는 것 이다.마지막 보초병 두 명 을 찾 지 못 하면 만 나 서 끝난다.마지막 에 기점 과 보초병 이 만 나 는 곳 의 요 소 를 교환 한 다음 에 하나의 서열 을 기점 보다 작은 부분 과 기점 보다 큰 부분 으로 나 눈 다음 에 왼쪽 부분 과 오른쪽 부분 으로 나 누 면 마지막 결 과 는 질서 가 있다.

전체 코드:

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: QuickSort
 * @Description:     
 * @author:       
 * @date: 2021-06-24 10:32
 */
public class QuickSort {
    //    
    public static void quickSort(int[] arr) {
        quickSort(arr, true);
    }
    public static void quickSort(int[] arr, boolean ascending) {
        if (ascending) {
            quickSort(arr, 0, arr.length - 1, true);
        } else {
            quickSort(arr, 0, arr.length - 1, false);
        }
    }
    public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
        if (ascending)
            quickSort(arr, begin, end);
        else
            quickSortDescending(arr, begin, end);
    }
    //      --   
    public static void quickSort(int[] arr, int begin, int end) {
        if (begin > end) { //    
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { //     （i  ，j  ）    
            while (arr[j] >= base && i < j) { //  j    base  
                j--;
            }
            while (arr[i] <= base && i < j) { //  i    base  
                i++;
            }
            if (i < j) { //         
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //       i j         
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1); //        
        quickSort(arr, i + 1, end); //        
    }
    //     
    public static void quickSortDescending(int[] arr, int begin, int end) {
        if (begin > end) { //    
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { //     （i  ，j  ）    
            while (arr[j] <= base && i < j) { //  j    base  
                j--;
            }
            while (arr[i] >= base && i < j) { //  i    base  
                i++;
            }
            if (i < j) { //         
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //       i j         
        arr[begin] = arr[i];
        arr[i] = base;
        quickSortDescending(arr, begin, i - 1); //        
        quickSortDescending(arr, i + 1, end); //        
    }
}

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!