상용 정렬 알고리즘 및 JAVA 코드 구현

클래스 정렬 선택
1 간단하게 정렬 선택

	//      ：  ：O(n^2)   O:(n^2)    O(n^2)
	//           ，             
    public static void selectSort(int[] arr){

        for(int i = 0;i<arr.length-1;i++){
            //       
            int min = i;    //         i
            int temp = arr[min];
            for(int j = i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            //         ，min         ，       arr[i]      
            //       arr[i]      i       ：
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

2 더미 정렬

	//      T(n)：  ：O(nlogn)   O(nlogn)   O(nlogn)
	//             ，              maxHeapify(),         maxHeapify()   heapSort(),      

    public static void HeapSort(int[] arr){
        //   arr       
        int len = arr.length;
        int k = (len-2)/2;
        //                         
        for(int i = k;i>=0;i--){
            MaxHeapify(arr, i,len);
        }
        //                (      )         (        )      
        //      ，                  
        for(int j = 0;j<len;j++){   //   j       

            //                 
            int temp = arr[len-1-j];
            //    
            arr[len-1-j] = arr[0];
            arr[0] = temp;
            MaxHeapify(arr,0,len-j-1);
        }
    }

	/**
     *               ，                                                    
     *              
     * @param arr     
     * @param k      
     * @param len     
     */
    public static void MaxHeapify(int[] arr, int k, int len){

        int temp = arr[k];

        for(int i = 2*k+1;i<len;i=2*k+1){

            //            
            if(i<len-1 && arr[i]<arr[i+1]){
                i = i+1;
            }
            //             
            if(arr[i]<temp){
                break;
            }
            //            
            arr[k] = arr[i];
            arr[i] = temp;

            //                           
            k = i;
        }
    }

교환 클래스 정렬
1 거품 정렬

	//      ：  O(n)   O(n^2)   O(n^2)
    public static void bubbleSort(int[] arr){
        //       
        if(arr == null || arr.length ==0){
            return;
        }
        //         length-1 
        for(int i = 0;i<arr.length-1;i++){
            for(int j = 1; j<arr.length-i ;j++){
                if(arr[j-1]>arr[j]){
                    //            
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

2 빠 른 정렬

	//      :   O(nlogn)   O(nlogn)   O(n^2)
	//     ：  ：             ，            ，           ，          
    public static void quickSort(int[] arr, int low, int high){
        if(low<high){
            int pivot = findPivot(arr, low, high);
            quickSort(arr, low, pivot-1);
            quickSort(arr, pivot+1, high);
        }
    }
    public static int findPivot(int[] arr, int i, int j){
        int temp = arr[i];
        while (i<j){
            //     
            while (i<j && arr[j]>=temp){
                j--;
            }
            if(i<j && arr[j]<temp){
                arr[i] = arr[j];
                i++;
            }
            //     
            while (i<j && arr[i]<=temp){
                i++;
            }
            if(i<j && arr[i] >temp){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[j] = temp;
        return i;
    }

클래스 삽입 정렬
1 직접 정렬 삽입

	//      ：  O(n)   O(n^2)   O(n^2)
    public static void insertSort(int[] arr){

        if(arr == null || arr.length == 0){
            return;
        }

        for(int i = 1; i< arr.length ;i++){
            int temp = arr[i];
            //                   
            int j = i-1;
            while (j>=0 && arr[j]>temp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        
    }

2 힐 정렬(증분 정렬 축소)

	//          O(n)   O(nlogn)    O(n^s )  1
    public static void shellSort(int[] arr){

        if(arr == null || arr.length == 0){
            return;
        }
        int len = arr.length;
        for(int d = len/2 ; d>0;d = d/2){
            for(int i = d;i<len;i++){
                int temp  = arr[i];
                int j = i-d;
                while (j>=0 && arr[j]>arr[j+d]){
                    arr[j+d] = arr[j];
                    j = j-d;
                }
                arr[j+d] = temp;
            }
        }

    }

다른 형식 정렬
1.병합 정렬

	//      :   /  /   O(nlogn)
 
    public static void mergeSort(int[] arr, int l, int h, int[] temp){

        if(l<h){
            int mid = (l+h)/2;
            mergeSort(arr, l, mid, temp);
            mergeSort(arr,mid+1, h,temp);
            merge(arr, l,mid,h,temp);
        }
    }

    public static void merge(int[] arr, int l, int mid, int h, int[] temp){

        int i = l;
        int j = mid+1;
        int t = 0;

        while (i<=mid && j<= h){
            if(arr[i]<arr[j]){
                temp[t++]= arr[i++];
            }else {
                temp[t++]= arr[j++];
            }
        }

        while (i<=mid){
            temp[t++] = arr[i++];
        }
        while (j<=h){
            temp[t++] = arr[j++];
        }

        t = 0;
        while (l<=h){
            arr[l++] = temp[t++];
        }

    }

2 기수 정렬

/**
 *     
 *    
 *       
 *                                                   
 *                                            
 *     
 */
public class RadixSort {

    public static void main(String[] args) {

        int[] arr = {53, 3, 542, 748, 14, 214};
        RadixSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void RadixSort(int[] arr){

        int[][] bucket = new int[10][arr.length]; //      
        int[] elementCount = new int[10]; //                

        //          
        int max = arr[0];
        for(int i = 1; i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        int maxLength = (max+"").length();

        //     
        for(int n = 0;n<maxLength;n++){
            //     
            // i = 0 ->     i = 1   
            for(int i = 0;i<arr.length;i++){
                int l = arr[i]/((int)Math.pow(10, n+1)) % 10;
                //    
                bucket[l][elementCount[l]] = arr[i];
                elementCount[l]++;
            }
            int index = 0;
            //       
            for(int j = 0; j<bucket.length ;j++){
                if(elementCount[j] != 0){
                    for(int k = 0; k<elementCount[j];k++){
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                elementCount[j] = 0;
            }
        }

    }
}