Java 实现的各种经典的排序算法小Demo

由于有上机作业,所以就对数据结构中常用的各种排序算法都写了个Demo,有如下几个:

  • 直接插入排序
  • 折半插入排序
  • 希尔排序
  • 冒泡排序
  • 快速排序
  • 选择排序
  • 桶排序
    Demo下载地址

下面谈一谈我对这几个排序算法的理解:

插入类算法

对于直接插入排序:(按从小到大的顺序)
核心原理:
若数组中只有一个元素,那么这就已经是有序的了;若数组中元素个数为两个,我们只需要对他们进行比较一次,要么交换顺序,要么不交换顺序就可以实现数组的内容的有序化;但是当数组内的元素的个数为N个呢?又该如何?这就催化了这个直接插入排序算法,其核心就是利用了有序化数组的方式,认为再插入一个新的元素之前都是有序的,只需要从后往前进行查找(找到一个小于待插入数据的位置,记为position,然后把这个数据之后的元素全部向后迁移一个,再把待插入数据插入到position+1的位置即可。(小伙伴们可以想象一下为什么是position+1,因为position位置上的数据小于我们的待插入的数据啊,所以要插在Position的下一个位置上!)

public static void DirectoryInsert(int []array,int length){
        int p,i;
        for(p=1;p<length;p++){
            int temp=array[p];
            i=p-1;
            while(i>=0&&array[i]>temp){
                array[i+1]=array[i];
                i--;
            }
            array[i+1]=temp;
        }
    }

关于折半插入排序算法:
核心原理:
折半插入的核心原理仍然是基于有序表的插入算法,找到位置后,仍然采用插入的方式进行数据添加。但是较之于直接插入有很大的提升,那就是在查找插入位置上的优化,速度上稍微有了一定的提升,虽然在乱序的数据上有良好的效果,但是时间复杂度仍然很大O(n^2)。是稳定的算法。
下面是代码的实现:

private static void Half(int[] array, int length) {
        //p stands for the times of the sort
        int left,right,mid,p;
        for(p=1;p<length;p++){
            int temp=array[p];
            left=0;right=p-1;
            while(left<=right){
                mid=(left+right)/2;
                if(array[mid]>temp){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            for(int i=p-1;i>=left;i--){
                array[i+1]=array[i];
            }
            array[left]=temp;
        }
    }

对于希尔排序:
核心原理:
希尔排序核心仍然是基于插入方式的,以逐步减小“步长”,采用“分治”的思想对每一个子序列进行排序。最终实现对整个序列的排序。
特点:希尔排序是不稳定的排序算法,会导致数据原始相对位置的改变。如果以步长为2计算,其时间复杂度可达到O(n^2),若数据足够长,步长也足够大那么时间复杂度将接近与O(n),但是一般认为其为O(n^1.3)。
代码实现:

private static void Shell(int[] array, int length) {
        // TODO Auto-generated method stub
        int d=length/2;
        while(d>=1){
            for(int k=0;k<d;k++){
                //to every sub,carry the direcly insert 
                for(int i=k+d;i<length;i+=d){
                    int temp=array[i];
                    int j=i-d;
                    while(j>=k&&array[j]>temp){
                        array[j+d]=array[j];
                        j-=d;
                    }
                    array[j+d]=temp;
                }
            }
            d=d/2;
        }
    }

交换类排序算法


对于冒泡排序:
核心原理:
冒泡排序是我们接触比较早的一个排序算法,其原理就是对数据两两进行比较大小,并对符合要求的数据进行交换。循环n-1次,便可以对n 个数据实现排序。
特点:
时间复杂度O(n^2),由于数据发生交换时并没有发生原始位置的变化,所以冒泡排序算法是稳定的排序算法。
代码实现:

private static void Bubble(int[] array, int length) {
        // TODO Auto-generated method stub
        for(int i=0;i<length;i++){
            //expeclally the end case is "length-i"
            for(int j=1;j<length-i;j++){
                if(array[j-1]>array[j]){
                    int temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                }
            }
        }
    }

对于冒泡排序,这里还有一个改进版的冒泡,是针对于特殊情况下的排序的处理,比如一个已经有序的序列如果再进行正常的冒泡的话,就会浪费时间,所以,如果一个序列已经是有序的,那么就应该跳出这个序列的冒泡,从而在一定程度上减少了时间的浪费。
代码实现:

private static void BubbleBetter(int[] array, int length) {
        // TODO Auto-generated method stub
        boolean flag=false;
        for(int i=0;i<length;i++){
            //expeclally the end case is "length-i"
            for(int j=1;j<length-i;j++){
                flag=false;
                if(array[j-1]>array[j]){
                    int temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                    flag=true;
                }
            }
            if(flag){
                return;
            }
        }
    }

快速排序算法:
核心原理:
快速排序的原理是找到轴值pivot(这里有两种方式,从代码中可以清晰地看到,但最终结果都是一样的,那就是找到这个分割点,再递归的进行排序。
特征:
时间复杂度为O(nlogn,已2为底);
代码如下:

private static void Fast(int[] array, int left, int right) {
        // TODO Auto-generated method stub
        if (left < right) {
            int p = Partition1(array, left, right);
            Fast(array, left, p - 1);
            Fast(array, p + 1, right);
        }
//      if (left < right) {
//          int p = Partition2(array, left, right);
//          Fast(array, left, p - 1);
//          Fast(array, p + 1, right);
//      }
    }

    private static int Partition1(int[] array, int left, int right) {
        int pivot = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }

    private static int Partition2(int[] array, int start, int end) {
        int pivot = array[start];
        int left = start, right = end;
        while (left <= right) {
            while (left <= right && array[left] <= pivot) {
                left++;
            }
            while (left <= right && array[right] >= pivot) {
                right--;
            }
            if (left < right) {
                Swap(array[right], array[left]);
                left++;
                right--;
            }
        }
        Swap(array[start], array[right]);
        return right;

    }

选择类排序算法


对于选择排序:
核心原理:
两轮循环,第一轮是选择的次数的记录,第二轮是目标查找。所谓目标查找,就是找到一个符合要求的值,记录其位置,然后在第一轮的循环中进行判断,将符合条件者进行交换,如此可实现排序的功能。
特征:
时间复杂度O(n^2),交换n-1次,比较了n^2次。是不稳定的排序算法。
代码:

private static void Select(int[] array, int length) {
        // TODO Auto-generated method stub
        for(int i=1;i<length;i++){
            int k=i-1;
            for(int j=i;j<length;j++){
                if(array[j]<array[k]){
                    k=j;
                }
            }
            if(k!=i-1){
                int temp=array[i-1];
                array[i-1]=array[k];
                array[k]=temp;
            }
        }
    }

归并类排序算法


对于归并排序:
核心原理:
若一个序列只有一个元素,则它是有序的,归并排序不执行任何操作。否则归并排序将执行下面的递归步骤:
1)先把序列划分为长度基本相等的子序列
2)对每个子序列归并并排序
3)把排好序的子序列合并为最终的结果。
特征:
时间复杂度O(nlogn),是不依赖于数据原始顺序的不稳定的排序算法。
代码如下:

private static void MergeFunction(int[] array,int start, int end) {
        // TODO Auto-generated method stub
        if(start<end){
            int mid=(start+end)/2;
            MergeFunction(array, start, mid);
            MergeFunction(array, mid+1, end);
            Merge(array,start,mid,end);
        }
    }

    private static void Merge(int[] array, int start, int mid, int end) {
        // TODO Auto-generated method stub
        int len1=mid-start+1,len2=end-mid;
        int i,j,k;
        //声明数组,分别保存子串信息
        int[] left=new int[len1];
        int[] right=new int[len2];
        for(i=0;i<len1;i++){//执行数据复制
            left[i]=array[i+start];
        }
        for(i=0;i<len2;i++){//执行数据复制
            right[i]=array[i+mid+1];
        }
        i=0;j=0;
        //执行合并操作
        for(k=start;k<end;k++){
            if(i==len1||j==len2){
                break;
            }
            if(left[i]<right[j]){
                array[k]=left[i++];
            }else{
                array[k]=right[j++];
            }
        }

        //若array[start,mid]还有待归并数据,则放到array后面
        while(i<len1){
            array[k++]=left[i++];
        }

        //对array[mid+1,end]见得数据执行同样的操作
        while(j<len2){
            array[k++]=left[j++];
        }
        //释放内存操作
        left=null;
        right=null;

    }

总结:
排序算法多种多样,在不同的情况下选择合适的排序算法能让你事半功倍。

上一篇:JAVA常见算法题(二十)


下一篇:【iOS开发】分享一个被误认为是 bug 的东西