排序算法

介绍

排序是将一组程序，依指定的顺序进行排列的过程。

分类


分别实现

冒泡排序

冒泡排序(Bubble Sorting)的基本思想是：通过对需要排序的序列从前往后(从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移到后部。

优化：
因为排序的过程，各元素不断接近自己的位置，如果一轮比较下来没有进行过交换，就说明序列有序，因此在排序过程设置一个标志flag判断元素是否进行过交换。

代码实现：

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int arr[]= {3,9,-1,20,10};    //实例
        int tmp;
        boolean flag=false;
        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]) {
                    flag=true;
                    tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
            if(flag==false) {
                break;
            }else{
                flag=false;
            }
        }

        System.out.println(Arrays.toString(arr));
    }

}

选择排序

选择排序也属于内部排序，是从欲排序的数据中，按指定的规则选出某一元素，再依照规定交换位置后达到排序的目的。

思想：选择排序(select sorting)的基本思想是：第一次从arr[0]到arr[n-1]中选最小值，与arr[0]交换，第二次从arr[1]到arr[n-1]中选取最小值，与arr[1]交换，以此类推，共进行n-1轮，得到一个按排序码从小到大的有序排列。

代码实现：

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {3,9,-1,20,10};    //实例

        for(int i=0;i<=arr.length-1;i++) {
            int min=arr[i];
            int minIndex=i;
            for(int j=i+1;j<=arr.length-1;j++) {
                if(arr[j]<arr[i]) {
                    min=arr[j];
                    minIndex=j;
                }
            }
            if(min!=arr[i]) {
                arr[minIndex]=arr[i];
                arr[i]=min;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

插入排序属于内部排序法。是对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

思想:把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只含有一个元素，无序表中包含有 n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

代码实现：

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {3,-1,9,87,21,46};
        insertSort(arr);
        System.out.print(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {

        for(int i=1;i<arr.length;i++) {
            int insertVal=arr[i];
            int insertIndex=i-1;

            while(insertIndex>=0&&insertVal<arr[insertIndex]) {
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }

            arr[insertIndex+1]=insertVal;
        }

    }

}

希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进后的一个更高效的版本，也称为缩小增量排序。

基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰好被分成一组，算法便终止。

代码实现

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        //shellSort2(arr);
        System.out.print(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr){     //采用交换法
        int tmp=0;
        int count=0;

        for(int gap=arr.length/2;gap>0;gap/=2) {
            for(int i=gap;i<arr.length;i++) {
                //遍历各组所有的元素（共gap组，每组有个元素），步长gap
                for(int j=i-gap;j>=0;j-=gap) {                //注意循环条件
                    //如果当前元素大于加上步长后的元素，说明交换
                    if(arr[j]>arr[j+gap]) {
                        tmp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=tmp;
                    }
                }
            }
        }
    }

    //对交换的希尔排序进行优化---->移位法
    public static void shellSort2(int[] arr) {

        //增量gap,并逐步的缩小增量
        for(int gap=arr.length/2;gap>0;gap/=2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for(int i=gap;i<arr.length;i++) {
                int j=i;
                int tmp=arr[j];
                if(arr[j]<arr[j-gap]) {
                    while(j-gap>=0&&tmp<arr[j-gap]) {
                        //移动
                        arr[j]=arr[j-gap];
                        j-=gap;
                    }
                    //当退出while后，就给tep找到插入的位置
                    arr[j]=tmp;
                }
            }
        }
    }
}

快速排序

快速排序是(QuickSort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分。其中一部分的所有数据都比另外一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {-9,78,0,23,-567,70};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr,int left,int right) {
        int l=left;
        int r=right;
        //设置pivot 中轴值
        int pivot=arr[(left+right)/2];
        int temp=0;  //交换时用

        //while循环，使比pivot小的值放左边，比pivot值大的放右边
        while(l<r) {
            //再pivot的左边一直找，找到大于等于pivot的值，才退出
            while(arr[l]<pivot) {
                l+=1;
            }
            //在pivot右边找到小于pivot的值，才退出
            while(arr[r]>pivot) {
                r-=1;
            }

            //如果l>=r说明pivot左右两边的值以全部是右边大于左边
            if(l>=r) {
                break;
            }

            //交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;

            //如果交换完后，发现arr[l]==pivot值，相等 r--，前移
            if(arr[1]==pivot) {
                r-=1;
            }

            //如果交换完后，发现这个arr[r]==pivot值，相等 l++,后移
            if(arr[r]==pivot) {
                l+=1;
            }
        }        
            //如果l==r，必须l++.r--,否则会出现栈溢出
            if(l==r) {
                l+=1;
                r-=1;
            }    
            //向左递归
            if(left<r) {
                quickSort(arr,left,r);
            }

            //向右递归
            if(right>l) {
                quickSort(arr,l,right);
        }
    }
}

思路分析图

归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分置(divide-and-conquer)策略(分治法将问题分(divide)一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各个答案“修补在一起”，即分而治之)。

代码实现

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {8,4,5,7,1,3,6,2};
        int temp[]=new int[arr.length];     //归并需要的额外空间
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("归并排序后="+Arrays.toString(arr));
    }


    //分+合的方法
    public static void mergeSort(int[] arr,int left,int right,int[] temp) {
        if(left<right) {
            int mid=(left+right)/2;     //中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    //合并的方法
    public static void merge(int[] arr,int left,int mid,int right,int[] temp) {

        int i=left;//初始化i，左边有序序列的初始索引
        int j=mid+1;//初始化j，右边有序序列的初始索引
        int t=0;    //指向temp数组的当前序列

        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完为止
        while(i<=mid&&j<=right) {
            //如果左边的有序序列的当前元素，小于右边有序序列的当前元素
            //即将左边的当前元素填充到temp数组
            //然后i++，temp索引t++
            if(arr[i]<=arr[j]) {
                temp[t]=arr[i];
                t++;
                i++;
            }else {
                temp[t]=arr[j];
                t++;
                j++;
            }
        }

        //(二)
        //将有剩余数据的一边依次填充到temp
        while(i<=mid) {
            temp[t]=arr[i];
            t++;
            i++;
        }
        while(j<=right) {
            temp[t]=arr[j];
            t++;
            j++;
        }

        //(三)
        //将temp数组的元素拷贝到arr，注意的是不是每次都拷贝所有的元素
        t=0;
        int tempLeft=left;      
        //第一次合并tempLeft=0,right=1;第二次tempLeft=2，right=3//tL=0，ri=3
        //最后一次 tempLeft=0 right=7
        while(tempLeft<=right) {
            arr[tempLeft]=temp[t];
            t++;
            tempLeft++;
        }
    }
}

基数排序(适用于非负数排序)

1)基数排序(桶排序)属于“分配式排序”(distribution sort),又称“桶子法”(buck sort)或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配到某些"桶"中，达到排序效果。
2)基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法。
3)基数排序(Radix Sort)是桶排序的发展。
4)基数排序是1887年赫尔曼.赫勒里发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基本思想
①将所有待比较数值统一位同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行依次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成了一个有序序列。
②图文，以数组{53,3,542,748,14,214}为例。

代码实现

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {53,3,542,748,14,214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //基数排序方法
    public static void radixSort(int[] arr) {

        //1.得到数组中最大的数的位数
        int max=arr[0];   //假设第一个数就是最大数
        for(int i=1;i<arr.length;i++) {
            if(arr[i]>max) {
                max=arr[i];
            }
        }

        //得到最大位数是多少
        int maxLength=(max+"").length();               //计算某数的位数的一个方法，转为string类型，.length()。

        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //说明
        //1.二维数组包含10个一维数组
        //2.为防止在放入数的时候，数据溢出，将每个一位数组大小定义为arr.length，所以基数算法是以空间换时间的一种算法

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

        //定义一个一维数组记录各个桶放入的数据个数
        int[] bucketElementCount=new int[10];

        for(int i=0,n=1;i<maxLength;i++,n*=10) {
            //(针对每个元素的对应位进行排序处理)，个位→十位→百位→...
            for(int j=0;j<arr.length;j++) {
                //取出对应元素的对应位的值
                int digitOfElement=arr[j]/n%10;
                //放入到对应的桶里
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }

            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index=0;
            //遍历每一个桶，并将桶中的数据放到原数组
            for(int k=0;k<bucketElementCount.length;k++) {
                //如果桶不为空，则放入原数组
                if(bucketElementCount[k]!=0) {
                    //循环第k个桶，将数据依次放入
                    for(int l=0;l<bucketElementCount[k];l++) {
                        //
                        arr[index++]=bucket[k][l];
                    }
                }
                //第i+1轮处理过后，需要将每个bucketElementCounts[k]=0
                bucketElementCount[k]=0;
                }
            System.out.println("第"+(i+1)+"轮，对位数的排序处理 arr="+Arrays.toString(arr));