Java 排序算法分析与实现

一、概述：

本文给出常见的几种排序算法的原理以及 Java 实现，包括常见的简单排序和高级排序算法，以及其他常用的算法知识。

• 简单排序：冒泡排序、选择排序、插入排序
• 高级排序：快速排序、归并排序、希尔排序
• 相关算法知识：划分、递归、二分查找

二、冒泡排序：

（1）原理：

• 1、从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
• 2、指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
• 3、依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
• 4、依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
• 5、重复上述过程，没排完一轮，比较次数就减少一次。

（2）例子：

待排序数据：7, 6, 9, 8, 5,1

第一轮排序过程：

指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1
指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1
指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1
指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1
指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9

第一轮排序结束后，最大的数字9被移到了最右边。

进行第二轮排序，过程同上，只是由于最大的9已经放在最右边了，因此不用在比较9了，少了一次比较，第二轮结束的结果为：6,7,5,1,8,9

第三轮结果：6,5,1,7,8,9

第四轮比较结果：5,1,6,7,8,9

第五轮比较结果：1,5,6,7,8,9

最终排序结果为：1,5,6,7,8,9，由上可知N个数据排序，需要进行N-1轮排序；第i轮排序需要的比较次数为N-i次。

（3）编码思路：

需要两层循环，第一层循环i表示排序的轮数，第二层循环j表示比较的次数。

（4）代码实现：

实例

package com.test.insertsort;
/**
 * 选择排序
 * @author Administrator
 *
 */
public class ChooseSort {
    private int[] array;
    private int length;
    
    public ChooseSort(int[] array){
        this.array = array;
        this.length = array.length;
    }
    
    /**
     * 打印数组中的所有元素
     */
    public void display(){
        for(int i: array){
            System.out.print(i+" ");
        }
        System.out.println(); 
    }
    
    /**
     * 选择排序算法
     */
    public void chooseSort(){
        for(int i=0; i<length-1; i++){
            int minIndex = i;
            for(int j=minIndex+1;j<length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp; 
        }
    }
    
    public static void main(String[] args){
        int[] array={100,45,36,21,17,13,7};
        ChooseSort cs = new ChooseSort(array);
        System.out.println("排序前的数据为：");
        cs.display();
        cs.chooseSort();
        System.out.println("排序后的数据为：");
        cs.display();
    }
}

（5）选择排序总结：

N个元素需要排序N-1轮；

第i轮需要比较N-i次；

N个元素排序，需要比较n（n-1）/2次；

选择排序的算法复杂度仍为O（n*n）；

相比于冒泡排序，选择排序的交换次数大大减少，因此速度要快于冒泡排序

四、插入排序

插入排序是简单排序中最快的排序算法，虽然时间复杂度仍然为O(n*n)，但是却比冒泡排序和选择排序快很多。

（1）原理：

• 1、将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；
• 2、此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大；
• 3、指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

（2）例子：

待比较数据：7, 6, 9, 8, 5,1

• 第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,_,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成_,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1
• 第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1
• 第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,_,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,_,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1
• 第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。
• 第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。

（3）编码分析：

需要两层循环，第一层循环index表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；第二层循环从leftindex=index-1开始，leftindex--向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或者leftindex<0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到leftindex处的空位处。

（4）代码实现：

实例

package com.test.insertsort;
/**
 * 插入排序算法：
 * 1、以数组的某一位作为分隔位，比如index=1，假设左面的都是有序的.
 * 
 * 2、将index位的数据拿出来，放到临时变量里，这时index位置就空出来了.
 * 
 * 3、从leftindex=index-1开始将左面的数据与当前index位的数据（即temp）进行比较，如果array[leftindex]>temp,
 * 则将array[leftindex]后移一位，即array[leftindex+1]=array[leftindex],此时leftindex就空出来了.
 * 
 * 4、再用index-2(即leftindex=leftindex-1)位的数据和temp比，重复步骤3，
 * 直到找到<=temp的数据或者比到了最左面（说明temp最小），停止比较，将temp放在当前空的位置上.
 * 
 * 5、index向后挪1，即index=index+1，temp=array[index],重复步骤2-4，直到index=array.length,排序结束，
 * 此时数组中的数据即为从小到大的顺序.
 * 
 * @author bjh
 *
 */
public class InsertSort {
    private int[] array;
    private int length;
    
    public InsertSort(int[] array){
        this.array = array;
        this.length = array.length;
    }
    
    public void display(){        
        for(int a: array){
            System.out.print(a+" ");
        }
        System.out.println();
    }
    
    /**
     * 插入排序方法
     */
    public void doInsertSort(){
        for(int index = 1; index<length; index++){//外层向右的index，即作为比较对象的数据的index
            int temp = array[index];//用作比较的数据
            int leftindex = index-1;
            while(leftindex>=0 && array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
                array[leftindex+1] = array[leftindex];
                leftindex--;
            }
            array[leftindex+1] = temp;//把temp放到空位上
        }
    }
    
    public static void main(String[] args){
        int[] array = {38,65,97,76,13,27,49};
        InsertSort is = new InsertSort(array);
        System.out.println("排序前的数据为：");
        is.display();
        is.doInsertSort();
        System.out.println("排序后的数据为：");
        is.display();
    }
}

（5）插入排序分析：

时间复杂度，由于仍然需要两层循环，插入排序的时间复杂度仍然为O(n*n)。

比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较N-1次，因此插入排序的最多比较次数为1+2+...+N-1=N*(N-1)/2。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为N*(N-1)/4。

移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。

综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。

快排、冒泡排序、选择排序、插入排序、归并排序

一、概述：

上文介绍了常见简单算法：冒泡排序、选择排序和插入排序。本文介绍高级排序算法：快速排序和归并排序。在开始介绍算法之前，首先介绍高级算法所需要的基础知识：划分、递归，并顺带介绍二分查找算法。

二、划分：

划分是快速排序的前提，即把数据分为两组，大于特定值的数据在一组，小于特定值的数据在另一组。快速排序即是由划分和递归操作来完成的。

（1）原理：

定义一个阈值，分别从最左面和最右面向中间遍历元素，左面找到一个大于阈值的数据便停止，右边找到一个小于阈值的数据便停止，如果此时左右两边都还没有走到中间，则交换左面大于阈值的数据和右面小于阈值的数据；重复上述过程，直到左面指针和右面指针相遇，此时左面数据均小于阈值，右面数据均大于阈值，划分结束。划分结束后，数据仍然是无序的，但更接近于有序。

（2）例子：

待划分数据：7, 6, 9, 8, 5,1，假设阈值为5

第一轮：左指针指向7，右指针指向1，左指针向后移，右指针向左移，发现左面第一个大于5的元素7，右面第一个小于5的元素1，交换7和1的位置，结果：1,6,9,8,5,7；

第二轮：从6开始找大于5的数字，找到6，右边从5起找小于5的数字，找到1，但此时由于6在1的右面，，即右指针<左指针，左右指针交叉，此时划分结束。原数列被划分为两部分，左侧子数列只有一个元素，即为1，其为小于阈值的子数列；右侧子数列包括5个元素，均为大于阈值5的元素。

（3）代码实现：

实例

package com.test.insertsort;
 
/**
 * 划分、递归、快排
 * @author bjh
 *
 */
public class QuickSort {
    
    /**待排序、划分数组*/
    private int[] array;
    /**数组长度*/
    private int length;
    
    public QuickSort(int[] array){
        this.array = array;
        this.length = array.length;
    }
    
    /**
     * 打印元素
     */
    public void printArray(){
        for(int i=0; i<length; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    
    
    /**
     * 划分
     * @return 划分的分界点
     */
    public int partition(int left, int right, int pivot){
        //左指针的起点，left-1是由于在后面的循环中，每循环一次左指针都要右移，
        //这样可以确保左指针从左边第一个元素开始，不然是从第二个开始
        int leftpoint = left-1;
        //右指针的起点，right+1是由于后面的循环中，每循环一次右指针都要左移，
        //这样可以确保右指针从最右边开始，不然是从倒数第二个开始
        int rightpoint = right+1;
        while(true){
            //找到左边大于pivot的数据，或者走到了最右边仍然没有找到比pivot大的数据
            while(leftpoint<right && array[++leftpoint]<pivot);
            //找到右边小于pivot的数据，或者走到了最左边仍然没有找到比pivot小的数据
            while(rightpoint>left && array[--rightpoint]>pivot);
            //左指针和右指针重叠或相交
            if(leftpoint >= rightpoint){
                break;
            }else{
                //交换左边大的和右边小的数据
                swap(leftpoint,rightpoint);
            }
        }
        //返回分界点，即右边子数组中最左边的点
        return leftpoint;
    }
    
    
    /**
     * 交换数据
     */
    public void swap(int leftpoint,int rightpoint){
        int temp = array[leftpoint];
        array[leftpoint] = array[rightpoint];
        array[rightpoint] = temp;
    }
    
    public static void main(String args[]){
        int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85};
        QuickSort qs = new QuickSort(array);
        System.out.println("划分前的数据为：");
        qs.printArray();
        int bound = qs.partition(0, array.length-1, 50);
        System.out.println("划分后的数据为：");
        qs.printArray();
        System.out.println("划分的分界点为：" + array[bound] + "，分界点的坐标为：" + bound);
    }
 
}

运行结果为：