排序(二)时间复杂度为O(nlogn)的排序算法

时间:4个月前   阅读:54

时间复杂度为O(nlogn)的排序算法(合并排序、快速排序),比时间复杂度O(n²)的排序算法更适合大规模数据排序。

合并排序

合并排序的焦点头脑

接纳“分治头脑”,将要排序的数组从中心分成前后两个部门,然后对前后两个部门划分举行排序,再将排序好的两部门合并在一起,这样数组就有序了。

分治是一种解决问题的头脑,递归是一种编程技巧,使用递归的技巧就是,先找到递归公式和终止条件,然后将递归公式翻译成递归代码。

合并排序的递推公式和终止条件:

//递归公式
merge_sort(p...r) = mege(merge_sort(p...q),merge_sort(q+1,r));

//终止条件
p >= r,不再继续剖析

合并排序代码

public class MergeSort {

    public static void main(String[] args) {
        int[] a = {4, 3, 2, 1, 6, 5};
        mergeSort(a,0,a.length - 1);
        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void mergeSort(int[] a, int p, int r) {
        //终止条件
        if (p >= r) return;

        int q = (r - p) / 2 + p;
        //递归公式
        mergeSort(a, 0, q);
        mergeSort(a, q + 1, r);

        //到这里递归竣事,可以假设[0,q],[q + 1,r]已经排好序了
        merge(a, p, q, r);

    }

    private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int k = 0;
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        //判断哪个子数字中有数据,判断依据必须是 <=
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }

        //将剩余数据拷贝到暂且数组temp中
        while (start <= end) {
            temp[k++] = a[start++];
        }

        //将temp数组中数据[0,r-p],拷贝至a数组中原来位置
        //可以直接使用数组复制函数
        for (int n = 0; n <= r - p; n++) {
            a[p + n] = temp[n];
        }
    }
}

优化

可以行使哨兵节点对merge方式举行优化,将数组分配两部门,并将Integer.MAX_VALUE添加到每个数组的最后一位,就可以一次性将两个数组中数据所有对照完,不会剩余数据

//优化merge代码
private static void mergeBySentry(int[] a, int p, int q, int r) {
    int[] leftArr = new int[q - p + 2];
    int[] rightArr = new int[r - q + 1];

    for (int i = 0; i <= q - p; i++) {
        leftArr[i] = a[p + i];
    }
    leftArr[q - p + 1] = Integer.MAX_VALUE;

    for (int i = 0; i < r - q; i++) {
        rightArr[i] = a[q + i + 1];
    }
    rightArr[r - q] = Integer.MAX_VALUE;


    int i = 0;
    int j = 0;
    int k = p;
    while (k <= r) {
        if (leftArr[i] <= rightArr[j]) {
            a[k++] = leftArr[i++];
        } else {
            a[k++] = rightArr[j++];
        }
    }
}

稳固性

合并排序是稳固的排序算法,是否稳固取决于合并merge方式,当两个数组有相同数据合并时,可以先将左边的数据先存入temp中,这样就可以保证稳固性

时间复杂度

最好情形、最坏情形,照样平均情形,时间复杂度都是 O(nlogn)。推导历程待弥补...

空间复杂度

合并排序不是原地排序算法。

递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最主要的一点,那就是,只管每次合并操作都需要申请分外的内存空间,但在合并完成之后,暂且开拓的内存空间就被释放掉了。在随便时刻,CPU 只会有一个函数在执行,也就只会有一个暂且的内存空间在使用。暂且内存空间最大也不会跨越 n 个数据的巨细,以是空间复杂度是 O(n)

快速排序

快速排序焦点头脑

对数组p到r举行排序,从数组中从中取出一个数据作为pivot(分区点),将小于pivot的放在左边,大于pivot的放在右边,之后行使分治、递归头脑,再对左右双方的数据举行排序,直到区间缩小为1,说明数据有序了

递归公式和终止条件

//递归公式
quick_sort(p...r) = quick_sort(p...q) + quick_sort(q + 1 ... r)  
    
//终止条件
p >= r

快速排序代码

public static void quickSort(int[] a, int n){
    quickSortInternally(a,0,n - 1);
}

private static void quickSortInternally(int[] a,int p, int r){
    if (p >= r) return;

    int q = partition(a, p, r);
    quickSortInternally(a,p,q - 1);
    quickSortInternally(a,q + 1,r);
}

//p:起始位置,r:终止位置
private static int partition(int[] a, int p, int r) {
    //取出中心点
    int pivot = a[r];

    //i、j为双指针,i始终指向大于中心点的第一个元素,j不停遍历数组,最终指向最后一个元素即中心点
    int i = p;
    //对照从p最先,到r-1竣事
    for(int j = p; j < r; ++j) {
        //若是小于中心点
        if (a[j] < pivot) {
            if (i == j) {
                //若是i和j相等,说明之前没有大于中心点的元素,i和j都加1
                // j在举行下一轮循环的时刻会自动加1,以是在这里只加i
                ++i;
            } else {
                //若是不相等,说明i已经指向第一个大于中心点的元素
                // 需要将小于中心的的a[j]与a[i]交流位置,然后都加1
                int tmp = a[i];
                a[i++] = a[j];
                a[j] = tmp;
            }
        }
    }

    //循环竣事,i指向大于中心点a[r]的第一个元素
    //将a[i]与a[r]交流位置
    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    System.out.println("i=" + i);
    //返回交流后中心点坐标位置
    return i;
}

性能剖析

快速排序是原地、不稳固的排序算法,时间复杂度在大部门情形下的时间复杂度都可以做到 O(nlogn),只有在极端情形下,才会退化到 O(n²)

原地:空间复杂度为O(1),不需要占用分外存储空间

不稳固:由于分区的历程涉及交流操作,若是数组中有两个相同的元素,好比序列 6,8,7,6,3,5,9,4,在经由第一次分区操作之后,两个 6 的相对先后顺序就会改变。以是,快速排序并不是一个稳固的排序算法

时间复杂度:待弥补

思索

O(n) 时间复杂度内求无序数组中的第 K 大元素。好比,4, 2, 5, 12, 3 这样一组数据,第 3 大元素就是 4。

思绪:

  • 选择数组A[0,n-1]的最后一个元素A[n-1]作为中心点pivot

  • 对数组A[0,n-1]原地分区,分为[0,p-1],[p],[p+1,n-1],此时[0,p-1]这个分区中虽然可能无序,然则所有是比中心点小的元素,以是[p]为这群数中的第p+1大元素(下标为p,以是共有p+1个元素,应该是p+1大)

  • 对照p+1和K,若是p+1 = K,说明A[p]就是求解元素,若是K > p+1,说明求解元素出现在A[p+1,n-1]中,则根据上面方式递归对A[p+1,n-1]举行分去查找,同理,若是K < p+1,则对A[0,p-1]举行分区查找

时间复杂度:O(n)。第一次分区查找,我们需要对巨细为 n 的数组执行分区操作,需要遍历 n 个元素。第二次分区查找,我们只需要对巨细为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。依次类推,分区遍历元素的个数划分为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。若是我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1。这是一个等比数列求和,最后的和即是 2n-1。以是,上述解决思绪的时间复杂度就为 O(n)。

笨方式:每次取数组中的最小值,将其移动到数组的最前面,然后在剩下的数组中继续找最小值,以此类推,执行 K 次,也可以找到第K大元素。但这种方式的时间复杂度为O(K*n),在K值对照小时,时间复杂度为O(n),当K为n/2或n时,时间复杂度就为O(n²)了

思索2

现在你有 10 个接口接见日志文件,每个日志文件巨细约 300MB,每个文件里的日志都是根据时间戳从小到大排序的。你希望将这 10 个较小的日志文件,合并为 1 个日志文件,合并之后的日志仍然根据时间戳从小到大排列。若是处置上述排序义务的机械内存只有 1GB,你有什么好的解决思绪,能“快速”地将这 10 个日志文件合并吗

,

皇冠体育APP

:www.huangguan.us是一个开放皇冠代理APP下载、皇冠会员APP下载、皇冠线路APP下载、皇冠登录APP下载的平台,皇冠体育APP上最新登录线路、新2皇冠网址更新最快,皇冠体育APP开放皇冠会员注册、皇冠代理开户等业务。

上一篇:大发888游戏官网:通讯行业讲述:运营商力推5G硬件终端 电信5G承载网装备集采落地

下一篇:环球国际客服:柠檬/咖啡/坦克 长城汽车公布三大手艺品牌