排序(2)二分排序、快速排序、归并排序

排序(2)二分排序、快速排序、归并排序排序(2)–二分排序、快速排序、归并排序

排序(2)–二分排序、快速排序、归并排序

*二分排序

/** * 二分排序中,关键字的比较次数采用折半查找,数量级为O(nlogn), * 但是元素移动次数为O(n^2),因此时间复杂度为O(n^2)。 * @author yj */
public class BinarySort { 
   
    /** * 二分法插入排序是在插入第i个元素时,对前面的0~i-1元素进行折半, * 先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半, * 直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移, * 再把第i个元素放在目标位置上。 */
    public static void binarySort(int[] source){
        int left,right,middle;//left>right说明找到了位置
        int temp;
        for(int i = 1;i<source.length;i++){
            left = 0;//初始化左指向首个元素
            right = i-1;//右指向需要插入元素的左侧
            temp = source[i];//记录需要排序的元素
            while(left<=right){
                middle = (right+left)/2;
                if(source[middle]>temp){
  
  //中间元素大于待插入元素,说明插入位置在middle左侧
                    right = middle -1;//将右指向为左半
                }else {
                    left = middle + 1;
                }
            }
            for(int j = i-1;j>=left;j--){
  
  //插入操作,将元素右移
                source[j+1]=source[j];
            }
            source[left] = temp;
            spy(source);//显示排序的过程
        }
    }
    /** * 方便观察每次排序,可以窥探数组排序的情况 * @param source */
    public static void spy(int[] source){
        for(int k = 0;k<source.length;k++){
            System.out.printf(source[k]+" ");  
        }
        System.out.println();
    }
}

快速排序:

/** * 平均时间复杂度为O(nlgn/ig2);最差为O(n^2);空间复杂度O(logn) * 是不稳定排序 * 该方法的基本思想是:1.先从数列中取出一个数作为基准数。 * 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 * 3.再对左右区间重复第二步,直到各区间只有一个数。 * @author yj */
public class QuickSort { 
   
    /** * 快速排序 * @param source * @param low * @param high */
    public static void quickSort(int[] source,int low,int high){
        int pivotpos;//记录基准位置
        if(low<high){
            pivotpos = partition(source,low,high);
            quickSort(source, low, pivotpos - 1);//左半边
            quickSort(source, pivotpos + 1, high);//右半边
        }
    }
    /** * 划分算法 * @param source * @param i * @param j * @return i 基准位置 */
    private static int partition(int[] source, int i, int j) {
        int pivot = source[i];//将第一个数据记录为基准
        while(i<j){
        while(i<j&&source[j]>=pivot){
            j--;
        }
        if(i<j)
            source[i++] = source[j];//相当于source[i] = source[j];i++
        spy(source);//打印排序情况
        while(i<j&&source[i]<=pivot){
            i++;
        }
        if(i<j)
            source[j--] = source[i];
        spy(source);//打印排序情况
        }
        source[i] = pivot;
        return i;
    }
    /** * 方便观察每次排序,可以窥探数组排序的情况 * @param source */
    public static void spy(int[] source){
        for(int k = 0;k<source.length;k++){
            System.out.printf(source[k]+" ");  
        }
        System.out.println();
    }
}

*归并排序

/** * 时间复杂度O(nlogn),空间复杂度O(n),是稳定的排序 * @author yj */
public class MergeSort { 
   
    public static void mergeSort(int[] s,int start,int end){
        if(start<end){
  
  //两路归并
            int middle = (start+end)/2;
            mergeSort(s,start,middle);
            mergeSort(s, middle+1, end);
            //将两组数据归并
            merge(s,start,middle,middle+1,end);
        }
    }
    /** * 两组数据归并 * @param s * @param start1 * @param end1 * @param start2 * @param end2 */
    public static void merge(int[] s,int start1,int end1,int start2,int end2){
        int i,j;//数组1、2的两个游标
        i = start1;
        j = start2;
        int[] temp = new int[end2-start1+1];//建立一个数组为两个之和大小,归并到这个数组
        int k =0;
        while(i<=end1&&  j<=end2){
            if(s[i]>s[j]){
                temp[k] = s[j];
                k++;
                j++;
            }else{
                temp[k] = s[i];
                k++;
                i++;
            }
        }
        //将剩余的元素加入temp中
        while(i<=end1){
            temp[k] = s[i];
            k++;
            i++;
        }
        while(j<=end2){
            temp[k] = s[j];
            k++;
            j++;
        }
        //将temp中数据转移到原数组中
        for(int element :temp){
            s[start1] = element;
            start1++;
        }
        spy(s);
    }
    /** * 方便观察每次排序,可以窥探数组排序的情况 * @param source */
    public static void spy(int[] source){
        for(int k = 0;k<source.length;k++){
            System.out.printf(source[k]+" ");  
        }
        System.out.println();
    }
}

今天的文章排序(2)二分排序、快速排序、归并排序分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/11403.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注