排序算法分析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
其中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)。