可爱的皮卡丘 (#^.^#)

文章目录

• 一、归并排序
  • 1.归并排序概念
  • 2.例题讲解
• 二、堆排序
  • 1.堆排序概念
  • 2.堆排序的算法步骤
  • 3.例题详解

一、归并排序

1.归并排序概念

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

其分并过程

合并解读：

2.例题讲解

代码过程

#includevoid Merge(int a[], int start, int mid, int end,int c[])//将任意两个有序数组合并排序 {int k = 0,i = start,j = mid + 1;while (i <= mid && j <= end) {if (a[i] < a[j]){c[k++] = a[i++]; }else{c[k++] = a[j++]; }}if (i == mid + 1) {while(j <= end)c[k++] = a[j++];}if (j == end + 1) {while (i <= mid)c[k++] = a[i++];}for (j = 0, i = start ; j = end)return;int mid = ( start + end ) / 2;//取中间的值，Merge_Sort(a, start, mid,c);Merge_Sort(a, mid + 1, end,c);Merge(a, start, mid, end,c);} int main(){int a[] = {7,0,5,4,1,3,2,6};int c[100];Merge_Sort(a, 0,8,c);for(int i=0;i<8;++i){printf("%d ",a[i]);}return 0;}

结果演示：

二、堆排序

1.堆排序的概念

堆排序（Heapsort）是指利用堆积树这种数据结构所设计的一种排序算法。堆的两个的性质：

（1）堆中某个结点的值总是小于等于或大于等于其父结点的值；

（2）堆总是一棵完全二叉树.

在堆排序中将其分为两类：

（1）大顶堆：每个节点的值都大于或等于其子节点的值；

（2）小顶堆：每个节点的值都小于或等于其子节点的值。

用简单的公式表示为：

（1）大顶堆：a[i]>= a[2i+1] && a[i]>=a[2i+2]

（2）小顶堆：a[i]<= a[2i+1] && a[i]<=a[2i+2]

堆排序的平均时间复杂度为 Ο(nlogn)。

2.堆排序的算法步骤

先创建一个堆 H[0……n-1]，再将堆首最大值（堆顶）和堆尾互换，此时的堆尾为最大值，然后将剩余的n-1个元素，再重新构造成一堆，重复上述操作，最后课得到一个有序序列。

3.例题详解

对数组a[ ]={8,9,2,1,0,3,16, 4, 7,10,13,12,15,5,14}进行排序,使其成为递增序列。

#include void swap(int *a, int *b) {    int temp = *b;    *b = *a;    *a = temp;}void MAX(int a[], int start, int end) {int child,parents;for(parents=start,child=2*parents+1;child<=end;parents=child,child=2*parents+1){  if (child + 1 <= end && a[child] < a[child + 1])      child++; if (a[parents] = 0; i--)MAX(a, i, n - 1);    for (i = n- 1; i > 0; i--) { swap(&a[0], &a[i]); MAX(a, 0, i - 1);    }}int main() {    int a[] = {8,9,2,1,0,3,16, 4, 7,10,13,12,15,5,14};    int N = (int) sizeof(a) / sizeof(*a);    heap_sort(a, N);    int i;    for (i = 0; i < N; i++) printf("%d ", a[i]);    printf("\n");    return 0;}