快速排序和归并排序

1、快速排序

快速排序是冒泡排序的改进版,也是最好的一种内排序,在很多面试题中都会出现,也是作为程序员必须掌握的一种排序方法。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

1.1 原理

在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。
整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。
假设要排的数组为:A[8] ={ 5 2 8 9 2 3 4 9 },选择 key = 5, 开始时 i=0,j=7(升序排序)
1,定义i=0,j=A.lenght-1,i为第一个数的下标,j为最后一个数下标
2,从数组的最后一个数Aj从右往左找,找到第一小于key的数,记为Aj;
3,从数组的第一个数Ai 从左往右找,找到第一个大于key的数,记为Ai;
4,交换Ai 和Aj
5,重复这个过程,直到 i=j
6,调整key的位置,把A[i] 和key交换

1.2 时间复杂度

快排在最糟糕得情况下时间复杂度是O(n²),平均的复杂度是O(nlogn)

1.3 代码

public class QuickSort {
    private static int count;
    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        int[] num = {3,45,78,64,52,11,64,55,99,11,18};
        System.out.println(arrayToString(num,"未排序"));
        QuickSort(num,0,num.length-1);
        System.out.println(arrayToString(num,"排序"));
        System.out.println("数组个数:"+num.length);
        System.out.println("循环次数:"+count);
        
    }
    /**
     * 快速排序
     * @param num   排序的数组
     * @param left  数组的前针
     * @param right 数组后针
     */
    private static void QuickSort(int[] num, int left, int right) {
        //如果left等于right,即数组只有一个元素,直接返回
        if(left>=right) {
            return;
        }
        //设置最左边的元素为基准值
        int key=num[left];
        //数组中比key小的放在左边,比key大的放在右边,key值下标为i
        int i=left;
        int j=right;
        while(i<j){
            //j向左移,直到遇到比key小的值
            while(num[j]>=key && i<j){
                j--;
            }
            //i向右移,直到遇到比key大的值
            while(num[i]<=key && i<j){
                i++;
            }
            //i和j指向的元素交换
            if(i<j){
                int temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
        num[left]=num[i];
        num[i]=key;
        count++;
        QuickSort(num,left,i-1);
        QuickSort(num,i+1,right);
    }
    /**
     * 将一个int类型数组转化为字符串
     * @param arr
     * @param flag
     * @return
     */
    private static String arrayToString(int[] arr,String flag) {
        String str = "数组为("+flag+"):";
        for(int a : arr) {
            str += a + "\t";
        }
        return str;
    }
 
}

2、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

2.1 特点:

  • 时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)
  • 辅助空间复杂度为O(n)
  • 稳定
  • 顺序存储与链表存储均可

2.2 原理

分而治之(divide - conquer);每个递归过程涉及三个步骤

分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
合并: 合并两个排好序的子序列,生成排序结果.

2.3 时间复杂度

在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn),从合并过程中可以看出合并排序稳定。

2.4 代码

public class MergeSort {
    /**
     * 归并排序递归实现
     * @param a
     * @param left
     * @param right
     */
    public void mergeSort(int[] a,int left,int right){
        if(left<right){
            int middle = (left+right)/2;//分解
            mergeSort(a, left, middle);//治理
            mergeSort(a,middle+1,right);
            merge(a,left,middle,right);//合并
        }
    }
    /**
     * 合并
     * @param a
     * @param left
     * @param middle
     * @param right
     */
    private void merge(int[] a, int left, int middle, int right) {
        int [] tmpArray = new int[a.length];
        int rightStart = middle+1;
        int tmp = left;
        int third = left;
        //比较两个小数组相应下标位置的数组大小,小的先放进新数组
        while(left<=middle&&rightStart<=right){
            if(a[left]<=a[rightStart]){
                tmpArray[third++] = a [left++];
            }else{
                tmpArray[third++] = a[rightStart++];
            }
        }
        //如果左边还有数据需要拷贝,把左边数组剩下的拷贝到新数组
        while(left<=middle){
            tmpArray[third++] = a[left++];
        }
        //如果右边还有数据......
        while(rightStart<=right){
            tmpArray[third++] = a[rightStart++];
        }
        while(tmp<=right){
            a[tmp] = tmpArray[tmp++];
        }
    }
 
    public static void main(String[] args){
        MergeSort mergeSort = new MergeSort();
        int [] a = new int[]{90,3,2,67,44,-9,87,65,11,9,2,8};
        mergeSort.mergeSort(a, 0, a.length-1);
        for(int n:a){
            System.out.print(" "+n);
        }
    }
}

归并算法是分治思想的经典应用,其基本思想就是将两个有序的表合并成为一个有序表。如果a数组是有序的,b数组也是有序的,则最后合并后,c数组也是有序的

//实现将a、b两个数组合并到c数组
    public void merge(int a[], int b[], int[] c) {
        int aIndex=0, bIndex=0, cIndex=0;
        int aEnd=a.length, bEnd=b.length;
        c=new int[aEnd+bEnd];
        while (aIndex<=aEnd && bIndex<=bEnd) {
            if (a[aIndex]<b[bIndex]) {
                c[cIndex++]=a[aIndex++];
            } else {
                c[cIndex++]=b[bIndex++];
            }   
        }
        while (aIndex<=aEnd) {
            c[cIndex++]=a[aIndex++];
        }
        while (bIndex<=bEnd) {
            c[cIndex++]=b[bIndex++];
        }
    }

归并排序就是在这个合并有序数组的例子上继续扩展,先把待排序数组多次分解成两个子数组,分解到最后,每个子数组都只有一个值,这样的话每个子数组就是有序的,然后就可以调用上面的合并有序数组的例子了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 归并排序和快速排序用的都是分治的思想,用递归的编程技巧来实现.咱们先来看归并排序. 归并排序 归并排序的核心思想就...
    我是码神阅读 1,402评论 0 0
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,223评论 0 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,286评论 0 2
  • 关键词:归并排序、快速排序 0. 归并排序 思想:将两个或两个以上的有序序列合并成一个新的有序序列,这种并归的方法...
    编程半岛阅读 537评论 0 0
  • 逆序对问题 首先我们介绍一下什么是逆序对?以下内容摘自百度百科: 设 A 为一个有 n 个数字的有序集 (n>1)...
    SmallRookie阅读 514评论 0 1