排序算法分析2--归并排序和快速排序

    xiaoxiao2022-06-26  93

    排序算法分析2--归并排序和快速排序

    0.综述1.归并排序(MergeSort)原理2.归并排序代码实现3.归并排序算法分析4.快速排序(QuickSort)算法原理5.快排代码6.快排分析

    0.综述

    在前面一节中,我们分析了三种时间复杂度为O(n²)的排序算法–冒泡排序、插入排序、选择排序,由于这三种算法的时间复杂度较高,因而适用于 小规模数据的排序。而今天分析的两种排序算法适用于大规模数据的排序,因为它们的时间复杂度都是O(nlogn)。它们分别是归并排序和快速排序。

    1.归并排序(MergeSort)原理

    归并排序利用了分而治之的思想,对于一个未排序的数组,归并排序将它从数组中间分为前后两个部分,然后分别对这两个部分进行排序,再将这两个有序的序列合并起来,最终使整个数组是有序的。

    例如对于包含4,3,2,1,8,76,5这8个元素的序列,我们可以先将其分成4,3,2,1和8,76,5这两组序列,再将它们分为4,3/2,1/8,7/6,5这四组,然后在组内分别排序,得到3,4/1,2/7,8/5,6,然后将它们两两合并,得到1,2,3,4/5,6,7,8,在将这两个合并,最终就得到有序数组:1,2,3,4,5,6,7,8。

    整个示意图如下: 分治算法一般用递归来解决,归并排序也是如此。对于递归程序,首先应该弄清楚它的递归边界,也就是终止条件,然后就是它的递归方程。由上面对归并排序的原理分析不难得出,归并排序的递归公式就是:

    q = (p+r)/2 merge_sort(p,r)=(merge_sort(p,q),merge_sort(q+1,r)

    归并排序的递归边界应该就是:

    p>=r //p>=r时不再继续分解

    其中merge_sort(p,r)表示给下标p到下标r直接的元素排序。这样就可以转换成分别给p->q和q+1->r两个区间内的元素进行排序的子问题,其中q是p和r之间中间的元素下标,也就是q=(p+r)/2。

    2.归并排序代码实现

    void merge(int*a,p,q,r) { int *tmp = (int*)malloc((r - p + 1) * sizeof(int)); if(!tmp) perror("malloc failed.") int i, j, k; for (i = p, j = q + 1, k = 0; i <= q && j <= r;) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } if (i == q + 1) { for (; j <= r;) tmp[k++] = a[j++]; } else { for (; i <= q;) tmp[k++] = a[i++]; } memcpy(a + p, tmp, (r - p + 1) * sizeof(int)); free(tmp); } void merge_sort(int *a, int p, int r) { int q; if (p >= r) return; q = (p + r) / 2; merge_sort(a, p, q); merge_sort(a, q + 1, r); merge(a, p, q, r); }

    其中merge函数完成的功能是将已经有序的两个序列,也就p->q以及q->r两个序列之间的元素合并到一个序列中。

    3.归并排序算法分析

    在归并排序算法中,我们可以设定merge函数中对于值相同的两个元素位置不改变,所以归并排序算法是一个稳定的排序算法。归并排序算法的时间复杂度为O(nlogn)。由于归并排序算法的执行过程中,在合并有序数组的时候需要申请额外的内存空间,所以它不是原地排序算法并且它的空间复杂度为O(n)。

    4.快速排序(QuickSort)算法原理

    快速排序一般被简称为快排,它也用了分治的思想。快排的核心思想是若要对乱序数组中的下标p到r之间的元素排序,我们可以选择p到r之间任意的一个元素作为pivot分区点,将p->r这个序列分为两个部分,我们遍历p->r之间的元素,然后将小于pivot的放在pivot左边,将大于pivot的放在pivot右边,将pivot放在中间。 快排的递推公式如下:

    quick_sort(p,r) = quick_sort(p,q-1)+quick_sort(q+1,r)

    递推终止条件就是:

    p>=r

    5.快排代码

    void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int get_q(int *a, int p, int r) { int i, j; i = j = p; for (; j < r; ++j) { if (a[j] < a[r]) { if(i != j) { swap(a + i, a + j); } ++i; } } swap(a + i, a + r); return i; } void quick_sort(int *a, int p, int r) { int q; if (p >= r) return; q = get_q(a, p, r); quick_sort(a, p, q-1); quick_sort(a, q+1, r); }

    6.快排分析

    快排是一个不稳定的排序算法,但是它是原地的排序算法。快排的时间复杂度为O(nlogn)。

    最新回复(0)