美文网首页
经典排序算法(Java实现)

经典排序算法(Java实现)

作者: JacobY | 来源:发表于2017-09-19 21:37 被阅读0次

    1.算法介绍

    1.1 选择排序

    选择排序的工作原理在于每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
    代码实现如下:

    public static void selectionSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < arr.length; j++)
                if(arr[j] < arr[min])
                    min = j;
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    

    1.2 冒泡排序

    比较相邻的元素,如果第一个元素比第二个元素大的话就交换位置,对每一对相邻元素都进行这样的操作,那么最后的元素就是最大的元素。然后对前n - 1个元素进行同样的操作,直到没有相邻元素可以比较,那么排序就完成了。
    代码实现如下:

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

    1.3 插入排序

    插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。与选择排序一样,当前索引的左边的所有元素是有序的,但它们的最终位置还不确定,为了给更小的元素腾出空间,可能需要被移动。和选择排序不同的是,插入排序所需的时间取决于输入元素的初始顺序。
    代码实现如下:

    public static void insertionSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            for(int j = i; j > 0 && arr[j - 1] > arr[j]; j--){
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            } 
        }
    }
    

    1.4 希尔排序

    希尔排序是基于插入排序的排序算法,它的基本思想是先将整个待排记录序列分割成若干个子序列,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。而子序列的构成不是简单地“逐段分割”,而是将相隔某个增量的记录来组成一个子序列。如何选取增量序列是决定希尔排序性能的重要因素,但至今尚未有人求得最佳的增量序列。
    代码实现如下,增量序列为 1/2(3^k - 1):

    public static void shellSort(int[] arr){
        int N = arr.length;
        int h = 1;
        while(h < N/3)
            h = 3*h + 1;
        while(h >= 1){
            for(int i = h; i < N; i++){
                for(int j = i; j >= h && arr[j - h] > arr[j]; j -= h){
                    int temp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = temp;
                } 
            }
            h = h / 3;
        }
    }
    

    相关文章

      网友评论

          本文标题:经典排序算法(Java实现)

          本文链接:https://www.haomeiwen.com/subject/lurbwttx.html