排序算法

排序算法

-------1. 插入排序

 

-----------直接插入排序

 

-----------希尔插入排序

 

-------2. 交换排序

 

-----------冒泡排序

 

-----------快速排序

 

-------3. 选择排序

 

-----------直接选择排序

 

-----------堆排序

 

-------4. 归并排序

 

-------5. 基数数排序

 

一般企业会让你说出几种排序算法，而且要求你用一种排序算法给一个数组排序，查看你的变成和代码编写的熟练程度。

 

下面我将给大家介绍四种常见而且常考的排序算法：

 

1. 直接插入排序

 

------算法思想：------------------------

 

       2.要处理的数据A和前面的数据依次比较(从前向后)，如果该数据比前面数据小，

         * 将该点作为插入点，备份数据A，

         * 将插入点之后处理数据A之前的数据整体向后移动覆盖A的位置，

         * 然后将备份数据插入到插入点的位置

       3.取下一个待处理数据，执行步骤2

       4.循环步骤3直到，需要处理的数据为0

 

------代码实现：------------------------

 

     public void straightInsertionSort(double[] sorted){

        //获取待排序数组的长度

        int sortedLen = sorted.length;

        //从第二个数据开始处理，下标为1

        for(int i=1;i<sortedLen;i++){

            //j表示待处理数据前面的数据的下标，j的首位置为0

            for(int j=0;j<=i-1;j++){

                //如果发现处理数据比前面的数据小，则将，此时的 j 作为插入点

                // i 为处理元素位置

                //如果想要从大到小排序只需要将if语句中的<变成>即可

                if(sorted[i]<sorted[j]){

                    //备份处理元素

                    double back = sorted[i];

                    //将插入点之后的元素依次向后移动覆盖处理元素位置

                    for(int k=i;k>j;k--){

                        sorted[k]=sorted[k-1];

                    }

                    //将处理元素插入到插入点位置

                    sorted[j]=back;

                    //第一趟排序完成退出内层循环

                    break;

                }

            }

        }

    }

 

 

－－2. 冒泡排序

 

冒泡排序对部分以排序的数据进行排序操作，速度可以很快，但是对于一点顺序都没有的数据，排序效率将会非常差。

 

------算法思想：--------------------

        冒泡排序即可以从前向后扫描也可以从后向前扫描，这里以从后向前

     扫描为例。

         从后向前扫描数据清单，将出现乱序的相邻的两个数据交换位置，继续向前扫描。

     这样如果是从大到小的冒泡排序排序，扫描一遍之后，最大的数据将出现在数据清单的首位，

     再扫描一遍第二大的数据将出现在第二号位置，一直重复扫描操作，直到全部数据有序

 

------代码实现：------------------------

 

    public void bubbleSort(double[] sorted){

        //获取数据的长度

        int sortedLen=sorted.length;

        // i 代表扫描次数

        for(int i=1;i<=sortedLen;i++){

            //定义一个有序标志

             boolean flag=true;

            

            //从后向前扫描，所以 j 的其实位置为sortedLen-1

            //每扫描一次将出现一个最大元素排在前面并有序，所一下一次扫描的长度将减少一个

            //即扫描的结束位置的下标为 i-1

            for(int j=sortedLen-1;j>i-1;j--){

                //如果发现后面元素比相邻的前面的元素大，就交换位置

                if(sorted[j]>sorted[j-1]){

                    sorted[j] = sorted[j]+sorted[j-1];

                    sorted[j-1] = sorted[j]-sorted[j-1];

                    sorted[j] = sorted[j] - sorted[j-1];

                    //如果有数据交换说明，排序数据不是有序的

                    flag= false;

                }

            }

            //如果标志没有改变，说明排序数据是有序的，无需排序了，直接退出

            if(flag){

                return;

            }

        }

    }

 

－－3. 快速排序：

 

------算法思想-------------

 

    快速排序也为交换排序的一种，它的算法思想是

    1. 在排序数据中选择一个值指定为pivotKey，将大于pivotKey的数据方到右边，

      将小于pivotKey的数据放到左边，

    2. 取pivotKey左边的数据递归执行1，取pivotKey右边的数据递归执行1

 

------代码实现：------------------------

 

    public void quickSort(double[] sorted,int low,int high){

        //low和high相等说明，此时待排序数据为一个元素，无需排序

        if(low<high){

            //每调用一次getMiddle()方法就进行一次快速排序

            //中间值middle为pivotKey所在的位置的下标，他的左边为

            //小于它的数，右边为大于他的数

            int middle = getMiddle(sorted,low,high);

            //对左边的数进行相同规则的递归算法

            quickSort(sorted,low,middle-1);

            //对右边的数进行相同规则的递归算法

            quickSort(sorted,middle+1,high);

        }

    }

    

    /**

     * 作一趟快速排序让左边的数都小于指定值pivotKey，右边的数都大于指定值

     * low指示待排序数据的起使下标，high指示待排序数据的的结束下标

     * @param sorted

     * @param low

     * @param high

     * @return

     */

    private int getMiddle(double[] sorted, int low, int high) {

        //将排序数据的第一个值作为中心值

        double pivotKey=sorted[low];

        //首先判断low<high说明可以进行排序操作

        while(low<high){

            //如果low小于high且高值大于中心值，说明不需要交换，high--

            //如果一路顺利的执行下去，low并将等于high跳出循环，如果发现有一个值

            //小于中心值，将跳出循环，将高值赋值到中心值的位置，

            //当前high指向位置将成为无用信息

            while(low<high && sorted[high]>=pivotKey){

                high--;

            }

            sorted[low]=sorted[high];

            //低值发现，自己比中心值大，将赋值到高值无用信息的位置上

            //然而此时当前low指向的位置上的数据将成为无用信息

            while(low<high && sorted[low]<=pivotKey){

                low++;

            }

            sorted[high]=sorted[low];

            

            //循环以上步骤，直到low等于high

        }

        //low等于high时，跳出循环，此时low和high共同指向的位置为，中心值的位置

        sorted[low]=pivotKey;

        return low;

    }

 

 

－－选择排序：

 

-------算法思想：-----------

 

第 i 次选取 i 到array.length-1中间最小的值放在 i 的位置

 

------代码实现：------------------------

 

     public void straightSelectSort(double[] sorted){

        int sortedLen=sorted.length;

        // i 为比较的次数, 长度为sortedLen的数据需要比较sortedLen-1次

        for(int i=0;i<sortedLen-1;i++){

            //记录最小值的位置

            int pointer = 0;

            //临时变量用于和其他数据比较寻找最小值

            double temp = sorted[i];

            //第 i 次比较时，i 处的元素要和 i 之后的所有元素比较，所以j的初值为i+1

            for(int j=i+1;j<sortedLen;j++){

                if(temp>sorted[j]){

                    temp=sorted[j];

                    pointer=j;

                }

            }

            //交换数据

            sorted[pointer]=sorted[i];

            sorted[i] = temp;

        }

    }

 

 

以上四种算法是我们必须掌握的，大多数企业特别的喜欢考，希望大家好好学习，也不要浪费了我这么长时间的辛苦总结，希望大家都能找到一份称心的工作！