三种简单排序算法及其对比

三种简单排序算法及其对比

代码：

class  ArraySort
{
    private long[] a;
    private int nElems;

    public ArraySort(int max)
    {
        a = new long[max];
        nElems=0;
    }

    public void insert(long value)
    {
        a[nElems] = value;
        nElems++;

    }

    public void display()
    {
        for(int j = 0;j < nElems; j++)
        {
            System.out.print(a[j] + " ");
        }
        System.out.println("");
    }

    //冒泡排序方法
    public void bubbleSort()
    {
        int out,in;

        for(out=nElems-1;out>1;out--)    //外层循环（out指针向数组左方移动）
        {
            for (in=0;in<out ;in++ )    //内层循环（in指针向右方移动）
            {
                if(a[in]>a[in+1])    //不是左小右大的正确顺序？
                    swap(in,in+1);    //交换它们
            }
        }
    }    //结束

    //选择排序方法
    public void selectSort()
    {
        int out, in, min;

        for(out=0; out<nElems-1; out++)    //外层循环
        {
            min=out;    //将最小值指定为out指针所指位置数值
            for(in=out+1; in<nElems; in++)    //内层循环
            {
                if(a[in]<a[min])    //当前in指针的值比min所指的最小值更小吗？
                    min=in;    //将最小值重新指定为当前in指针所指数据
            }
            swap(out, min);    //交换out和min的值
        }
    }    //结束

    //插入排序方法
    public void insertSort()
    {
        int in, out;
        long temp;
        
        for(out=1; out<nElems; out++)    //out是左边有序部分和右边无序部分的分界线
        {
            temp=a[out];    //将分界点数据保存到临时变量中
            in=out;    //从out开始依次向右移动数据
            while(in>0 && a[in-1] >= temp)    //直到移动到一个比out更小的数据时
            {
                a[in] = a[in-1];    //将数据向右移动一个位置
                --in;    //in指针左移一个位置
            }
            a[in] = temp;
        }
    }    //结束

    public void swap(int one,int two)
    {
        long temp = a[one];
        a[one]=a[two];
        a[two]=temp;
    }

    public static void main(String[] args)
    {
        int maxSize=10;
        ArraySort arr;
        arr=new ArraySort(maxSize);

        arr.insert(77);
        arr.insert(99);
        arr.insert(45);
        arr.insert(55);
        arr.insert(23);
        arr.insert(86);
        arr.insert(12);
        arr.insert(00);
        arr.insert(65);
        arr.insert(34);

        arr.display();

        arr.insertSort();
        
        arr.display();
    }
} ;

排序算法思路描述：

public void bubbleSort()，    外层for循环的计数器out从数组的最后开始，即out等于nElems-1，每经过一次循环out减一。下标大于out的数据项都已经是拍好序的了。变量out在每完成一次内部循环（计数器为in）后就左移一位，因此算法就不再处理那些已经排好序的数据了。

       内层for循环计数器in从数组的最开始算起，即in=0，每完成一次内部循环体加一，当它等于out时结束一次循环。在内层for循环体中，数组下标为in和in+1的两个数据项进行比较，如果下标为in的数据项大于下标为in+1的数据项，则交换两个数据项。

public void selectSort()， 外层循环用循环变量out，从数组开头开始（数组下标为0）向高位增长。内层循环用循环变量in，从out所指位置开始，同样是向右移位。

       在每一个in的新位置，数据项a[in]和a[min]进行比较。如果a[in]更小，则min被赋值为in的值。在内层循环的最后，min指向最小的数据项，然后交换out和min指向的数据向。

public void insertSort()， 在外层的for循环中，out变量从1开始，向右移动。它标记了未排序部分的最左端的数据。而内层的while循环中，in变量从out变量开始，向左移动（复制），直到temp变量小于in所指的数组数据项，或者它已经不能再往左移动为止。While循环的每一趟都向右移动了一个已排序的数据项。

几种排序的比较：

冒泡排序：很容易写，但是一般不用，数据量很小时还是有些应用价值的。

选择排序：虽然交换次数降到最低，但比较次数依然很大，当数据量小，且交换相对于比较更耗时的情况下，可以应用它。

插入排序：数据量小或者基本有序时，插入算法是三者中最好的选择。相对于随机数据，它一般比冒泡快一倍，比选择也略快一些。因为它移动数据比交换数据耗费要小。

最后

以上就是幸福煎饼为你收集整理的三种简单排序算法及其对比的全部内容，希望文章能够帮你解决三种简单排序算法及其对比所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。