排序算法及java实现

/**
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        bubbleSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void bubbleSort(int[] list, int count) {
        for (int i = list.length-1; i >0 ; i--) {
            boolean flag=true;
            for (int j = 0; j < i; j++) {
                if (list[j]>list[j+1]){
                    flag=false;
                    int temp=list[j];
                    list[j]=list[j+1];
                    list[j+1]=temp;
                }
            }
            if (flag){
                return;
            }
        }
    }
}

/**
 *插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 *插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
//        int[] result=insertionSort(list,count);
        insertionSort(list);
//        System.out.println("排序后： "+ Arrays.toString(result));
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static int[] insertionSort(int[] list, int count) {
        int[] result= Arrays.copyOf(list, list.length);
        for (int i = 1; i < list.length; i++) {
            int j=i;
            while (j > 0 && list[i]<result[j-1]) {
                result[j]=result[j-1];
                j--;
            }
            result[j]=list[i];
        }
        return  result;
    }
    public static void insertionSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int j=i;
            while(j>0 && arr[j] < arr[j - 1]){
                arr[j] = arr[j]+arr[j-1];
                arr[j-1] = arr[j]-arr[j-1];
                arr[j] = arr[j]-arr[j-1];
                j--;
            }
        }
    }
}

/**
 * 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        selectSort(list);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void selectioonSort(int[] list, int count) {
        for (int i = 0; i < list.length-1; i++) {
            int min=i;
            for (int j = i + 1; j < list.length; j++) {
                if(list[min]>list[j]){
                    min=j;
                }
            }
            if (min!=i){
                int temp=list[i];
                list[i]=list[min];
                list[min]=temp;
            }
        }
    }
    public static void selectSort(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;
                }
            }
            if (min != i) {
                arr[min]=arr[min]+arr[i];
                arr[i]=arr[min]-arr[i];
                arr[min]=arr[min]-arr[i];
            }
        }
    }
}

/**
 * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
 * 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
 * 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
 * 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
 * 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        shellSort2(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void shellSort(int[] list, int count) {
        for (int D = count/2; D >0 ; D/=2) {
            for (int P = D; P < count; P++) {
                int temp=list[P];
                int i;
                for (i = P; i >= D && list[i-D] > temp; i-=D) {
                    list[i]=list[i-D];
                }
                list[i]=temp;
            }
        }
    }
    private static void shellSort2(int[] arr, int count) {
        for (int D = count/2; D >0 ; D/=2) {
            for(int i=D;i<arr.length;i++){
                int j=i;
                while(j>=D && arr[j] < arr[j - D]){
                    arr[j] = arr[j]+arr[j-D];
                    arr[j-D] = arr[j]-arr[j-D];
                    arr[j] = arr[j]-arr[j-D];
                    j-=D;
                }
            }
        }
    }

/**
 * 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
 * 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
 * 自下而上的迭代；
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        int[] result=sort(list);
        System.out.println("排序后： "+ Arrays.toString(result));
    }
    private static int[] sort(int[] list){
        int middle = (int) Math.floor(list.length / 2);
        if(list.length<2){
            return list;
        }
        int[] left=Arrays.copyOfRange(list,0,middle);
        int[] right=Arrays.copyOfRange(list,middle,list.length);
        return merge(sort(left),sort(right));
    }
    private static int[] merge(int[] left, int[] right) {
        int[] result=new int[left.length+right.length];
        int i=0;
        while (left.length>0 && right.length>0){
            if (left[0]> right[0]){
                result[i]=right[0];
                right=Arrays.copyOfRange(right,1,right.length);
            }else {
                result[i]=left[0];
                left=Arrays.copyOfRange(left,1,left.length);
            }
            i++;
        }
        while (left.length>0){
            result[i++]=left[0];
            left=Arrays.copyOfRange(left,1,left.length);
        }
        while (right.length>0){
            result[i++]=right[0];
            right=Arrays.copyOfRange(right,1,right.length);
        }
        return result;
    }

/**
 * 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用
 * 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
 * 该方法的基本思想是：
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        quickSort(list,0,count-1);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void quickSort(int[] list, int low,int high) {
        if(low>=high){
            return;
        }
        int piovt=list[low];
        int left=low;
        int right=high;
        while (left<right){
            while (left<right&&list[right]>=piovt){
                right--;
            }
            if (left<right){
                list[left]=list[right];
            }
            while (left<right&&list[left]<piovt){
                left++;
            }
            if (left<right){
                list[right]=list[left];
            }
            if (left>=right){
                list[left]=piovt;
            }
        }
        quickSort(list,low,right-1);
        quickSort(list,right+1,high);
    }

/**
 * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
 * 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
 * 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
 * 堆排序的平均时间复杂度为 Ο(nlogn)。
 */
public class Heapsort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        heapSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void heapSort(int[] list, int count) {
        for (int k = count-1; k > 1; k--) {
            for (int i = 0; i <=k; i++) {
                int left=2*i+1;
                int right=2*i+2;
                if(left<k && list[left]<list[i]){
                    int temp=list[i];
                    list[i]=list[left];
                    list[left]=temp;
                }
                if(right<k && list[right]<list[i]){
                    int temp=list[i];
                    list[i]=list[right];
                    list[right]=temp;
                }
                if (right<k && list[right]<list[left]){
                    int temp=list[left];
                    list[left]=list[right];
                    list[right]=temp;
                }
            }
            int min=list[0];
            list[0]=list[k];
            list[k]=min;
        }
    }

/**
 * 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] list= {81,94,11,96,12,35,17,95,28,58,41,75,15};
        System.out.println("排序前： "+ Arrays.toString(list));
        int count=13;
        radixSort(list,count);
        System.out.println("排序后： "+ Arrays.toString(list));
    }
    private static void radixSort(int[] list, int count) {
//        int[] result=Arrays.copyOf(list,list.length);
        LinkedList<Integer>[] linkedLists = new LinkedList[10];
        for (int i = 0; i < linkedLists.length; i++) {
            linkedLists[i] = new LinkedList<>();
        }
        int max=getMax(list);
        for (int i = 1; i <=max; i++) {
            for (int j = 0; j < list.length; j++) {
                linkedLists[getIndex(list[j],i)].offer(list[j]);
            }
            int index=0;
            for (int j = 0; j < linkedLists.length; j++) {
                while (!linkedLists[j].isEmpty()){
                    list[index++]=linkedLists[j].poll();
                }
            }
        }
//        return result;
    }
    private static int getMax(int[] list) {
        int max=list[0];
        for (int i = 0; i < list.length; i++) {
            if (list[i]>max){
                max=list[i];
            }
        }
        return (max + "").length();
    }
    private static int getIndex(int num, int r) {
        int ret = 0;
        for (int i = 1; i <= r; i++) {
            ret = num % 10;
            num /= 10;
        }
        return ret;
    }