Java의 다양한 정렬 알고리즘 및 구현

먼저 8가지 정렬의 관계를 살펴보겠습니다.

다음 그림은 다양한 정렬을 비교한 것입니다. 정렬:

1, 직접 삽입 정렬

(1) 기본 아이디어: In 정렬할 열 그룹 번호에서 이전 (n-1) [n>=2] 번호가 이미

순서로 되어 있다고 가정하면 이제 이전 순서 번호에 n번째 번호를 삽입해야 합니다. , n

숫자도 순서대로 정렬되도록 합니다. 모든 것이 정상화될 때까지 이 주기를 반복합니다.

삽입 알고리즘에서는 배열 끝에 최소 개수가 있으면 마지막

위치에서 첫 번째 위치로 삽입 알고리즘이 이동합니다.

(2) 예

package cglib;

 

public class StringNumber {
    
      public static void insertSort(int[] a) {  
            if (a == null || a.length < 2) {  
                return;  
            }  
            int length=a.length; //数组长度  
            int j;               //当前值的位置  
            int i;               //指向j前的位置  
            int key;             //当前要进行插入排序的值  
            //从数组的第二个位置开始遍历值  
            for(j=1;j<length;j++){  
                key=a[j];  
                i=j-1;
                System.out.println(" 将i="+i);
                //a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移  
                while(i>=0 && a[i]>key){
                    System.out.println("进 i="+i);
                    a[i+1]=a[i]; //将a[i]值后移  
                    i--;         //i前移  
                    System.out.println(" i="+i);
                }//跳出循环(找到要插入的中间位置或已遍历到0下标)
                System.out.println(" 退出while");
                System.out.println(" i="+i);
                a[i+1]=key;    //将当前值插入  
            }  
        }  
        
      
        public static void main(String[] args) {  
            int[] array = { 3, -1, 0, -8, 2, 1 };  
            ArrayUtils.printArray(array);  
            insertSort(array);  
            ArrayUtils.printArray(array);  
        }
}

class ArrayUtils {  
    
    public static void printArray(int[] array) {  
        System.out.print("{");  
        for (int i = 0; i < array.length; i++) {  
            System.out.print(array[i]);  
            if (i < array.length - 1) {  
                System.out.print(", ");  
            }  
        }  
        System.out.println("}");  
    }  
}

출력:

{3, -1, 0, -8, 2, 1}
 将i=0
进 i=0
 i=-1
 退出while
 i=-1
 将i=1
进 i=1
 i=0
 退出while
 i=0
 将i=2
进 i=2
 i=1
进 i=1
 i=0
进 i=0
 i=-1
 退出while
 i=-1
 将i=3
进 i=3
 i=2
 退出while
 i=2
 将i=4
进 i=4
 i=3
进 i=3
 i=2
 退出while
 i=2
{-8, -1, 0, 1, 2, 3}

힐 정렬(최소 증분 정렬)

기본 알고리즘:

먼저 정렬할 요소의 전체 시퀀스를 여러 하위 시퀀스로 나눕니다(특정 "증분"으로 구분) (요소의 "양"으로 구성됨)을 각각 직접 삽입하고 정렬한 다음, 전체 시퀀스의 요소가 기본적으로 순서대로(증분량이 충분히 작은 경우) 증분을 감소시킨 다음 정렬합니다. 모든 요소에 대해 수행됩니다. 직접 삽입 정렬은 요소가 기본적으로 정렬되어 있을 때(최상의 경우에 가까움) 매우 효율적이기 때문에 Hill 정렬은 처음 두 방법보다 시간 효율성이 더 높습니다. 단계 크기의 선택은 Hill 정렬의 중요한 부분입니다. 최종 단계 크기가 1인 한 모든 단계 크기 순서가 작동합니다.

알고리즘은 먼저 특정 단계 크기로 정렬한 다음 계속해서 특정 단계 크기로 정렬합니다. 최종 알고리즘은 단계 크기 1로 정렬합니다. 단계 크기가 1이면 알고리즘이 삽입 정렬로 변경되어 데이터가 정렬됩니다. Donald Shell은 처음에 frac{n}{2}의 단계 크기를 선택하고 단계 크기가 1에 도달할 때까지 단계 크기를 절반으로 줄이도록 제안했습니다. 이 접근 방식은 수학{O}(n^2)과 유사한 알고리즘(삽입 정렬)보다 나을 수 있지만 평균 시간과 최악의 시간을 줄일 여지는 여전히 남아 있습니다.

언덕 정렬 예: n=10 58 27 32 93 65 87 58 46 9 65의 배열, 단계 크기 n/2.

첫 번째 정렬 단계는 10/2 = 5

58 27 32 93 65 87 58 46 9 65
1A 1B
2A 2B
3A 3B
4A 4B
5A 5B

먼저 정렬할 요소 순서를 그룹화합니다. 단계 크기는 5(1A,1B), (2A,2B), (3A,3B) 등입니다. 그룹화 표시로 대문자는 그룹의 어떤 요소인지를 나타내고, 같은 숫자가 붙은 숫자는 같은 그룹에 속한다는 것을 나타내므로 (58,87), (27,58) 5개의 그룹으로 나뉜다 , (32,46), (93,9), (65,65)를 입력하고 각 그룹에 대해 직접 삽입 정렬을 수행하면 5개 그룹이 (58,87), (27,58), (32)가 됩니다. ,46), (9,93), (65, 65), 그룹 정렬은 각 그룹 내에서만 다음과 같은 테이블이 되며, 아래와 같습니다.

두 번째 정렬 단계는 5/2 = 2

58 27 32 9 65 87 58 46 93 65

1A 1B

2A 2B

3A 3B

                                        .....

세 번째 정렬 단계는 2/2 = 1

32 9 58 7 58 46 65 65 93 87

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

네 번째 정렬 단계는 순서가 지정된 요소 시퀀스를 얻기 위한 1/2 = 0입니다.

9 27 32 46 58 58 65 65 87 93

希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

增量序列的选择：Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征(查到的资料都这么讲)：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

package cglib;

 

public class StringNumber {
    
    public static void main(String[] args) {

        int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};

        System.out.print("排序前：");

        for(int o: arr) {

            System.out.print(o+" ");

        }

        System.out.println();

        shellSort(arr);

        System.out.print("排序后：");

        for(int o: arr) {

            System.out.print(o+" ");

        }

        System.out.println();

    }

    private static void shellSort(int[] arr) {

        int j;

        int len = arr.length;

        for(int val=len>>1; val>0; val>>=1) {

            //下面是对本次的所有分组做直接插入排序

            for(int i=val; i<len; i++) {
                System.out.println("for:i="+i);
                System.out.println("for:arr[i]="+arr[i]);
                System.out.println("for:val="+val);
                int temp = arr[i];

                /*

                 * 为什么每次都用temp比较呢？

                 * 因为直接插入就是找到temp的合适位置。

                 * 为什么temp<arr[j-val]这个条件可以放在for内呢？

                 * 因为原来的组内数据已经有序，找到位置就停止便是。

                 *

                 */

                for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
                    System.out.println("er:j="+j);
                    System.out.println("er:arr[j]="+arr[j]);
                    System.out.println("er:j-val="+(j-val));
                    System.out.println("er:arr[j-val]="+arr[j-val]);
                    /*

                     * 为什么是arr[j-val]不是arr[j]呢？

                     * 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val]

                     */

                    arr[j] = arr[j-val];
                    System.out.println("赋值er:arr[j]="+arr[j]);
                }

                /*

                 * 注意不是arr[i] = temp

                 * 直接插入排序也是这样的。

                 * 为什么呢？

                 * 因为j是位置，i是待插入元素

                 */

                arr[j] = temp;

            }

        }

    }
 
}

输出：

排序前：44 33 99 10 30 20 59 78 23 48
for:i=5
for:arr[i]=20
for:val=5
er:j=5
er:arr[j]=20
er:j-val=0
er:arr[j-val]=44
赋值er:arr[j]=44
for:i=6
for:arr[i]=59
for:val=5
for:i=7
for:arr[i]=78
for:val=5
er:j=7
er:arr[j]=78
er:j-val=2
er:arr[j-val]=99
赋值er:arr[j]=99
for:i=8
for:arr[i]=23
for:val=5
for:i=9
for:arr[i]=48
for:val=5
for:i=2
for:arr[i]=78
for:val=2
for:i=3
for:arr[i]=10
for:val=2
er:j=3
er:arr[j]=10
er:j-val=1
er:arr[j-val]=33
赋值er:arr[j]=33
for:i=4
for:arr[i]=30
for:val=2
er:j=4
er:arr[j]=30
er:j-val=2
er:arr[j-val]=78
赋值er:arr[j]=78
for:i=5
for:arr[i]=44
for:val=2
for:i=6
for:arr[i]=59
for:val=2
er:j=6
er:arr[j]=59
er:j-val=4
er:arr[j-val]=78
赋值er:arr[j]=78
for:i=7
for:arr[i]=99
for:val=2
for:i=8
for:arr[i]=23
for:val=2
er:j=8
er:arr[j]=23
er:j-val=6
er:arr[j-val]=78
赋值er:arr[j]=78
er:j=6
er:arr[j]=78
er:j-val=4
er:arr[j-val]=59
赋值er:arr[j]=59
er:j=4
er:arr[j]=59
er:j-val=2
er:arr[j-val]=30
赋值er:arr[j]=30
for:i=9
for:arr[i]=48
for:val=2
er:j=9
er:arr[j]=48
er:j-val=7
er:arr[j-val]=99
赋值er:arr[j]=99
for:i=1
for:arr[i]=10
for:val=1
er:j=1
er:arr[j]=10
er:j-val=0
er:arr[j-val]=20
赋值er:arr[j]=20
for:i=2
for:arr[i]=23
for:val=1
for:i=3
for:arr[i]=33
for:val=1
for:i=4
for:arr[i]=30
for:val=1
er:j=4
er:arr[j]=30
er:j-val=3
er:arr[j-val]=33
赋值er:arr[j]=33
for:i=5
for:arr[i]=44
for:val=1
for:i=6
for:arr[i]=59
for:val=1
for:i=7
for:arr[i]=48
for:val=1
er:j=7
er:arr[j]=48
er:j-val=6
er:arr[j-val]=59
赋值er:arr[j]=59
for:i=8
for:arr[i]=78
for:val=1
for:i=9
for:arr[i]=99
for:val=1
排序后：10 20 23 30 33 44 48 59 78 99

选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

package cglib;

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class StringNumber {
    
    public static void main(String[] args){  
        Random random = new Random();  
        int[] array = new int[2000];  
          
          
            for (int j = 0; j < 2000; j++) {  
                array[j] = random.nextInt(100000);  
            }  
        
        System.out.println(Arrays.toString(array));  
        selectSortTest(array);  
        System.out.println(Arrays.toString(array));       
    }  
    
     public static void selectSortTest(int a[]) {  
             
            Date dateStart = new Date();  
            selectSort(a);  
            Date dateEnd = new Date();  
            System.out.println("选择排序耗费时间："  
                    + (dateEnd.getTime() - dateStart.getTime()));  
              
           
        }  
    
    
      
    public static void selectSort(int a[]){  
        int n = a.length;  
        for(int k=0; k<n-1; k++) {  
            int min = k;  
            for(int i=k+1; i<n; i++) {//找出最小值  
                if(a[i] < a[min]) {  
                    min = i;  
                }  
            }  
            if(k != min) {  
                int temp = a[k];  
                a[k] = a[min];  
                a[min] = temp;  
            }  
        }  
    }  
}