算法导论中的四种基本排序

算法导论中常见的四种排序

                                                        by方阳

版权声明:本文为博主原创文章,转载请指明转载地址

http://www.cnblogs.com/fydeblog/p/7067382.html

1. 前言

好久没写博客了,今天来一篇最近开始看的算法导论,这篇博客主要介绍插入排序,归并排序,堆排序和快速排序的原理,性能分析以及程序实现!废话不多说,let's go!

2. 原理解析

2.1 插入排序

参考下面的图片,再想想我们平时玩扑克牌,它的基本思路就清晰多了,假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。

2.2 归并排序

参考下面的图片(从pdf上截的,有点歪),可以看出是将原数组进行分解,然后排序,在进行合并,归并排序分治(Divide and conquer)策略的一个很好的例子,将复杂的问题分成许多小问题,分开解决,然后合并。

2.3 堆排序

堆排序涉及到的知识比较多,它主要分为三部分:MAX-HESPIFY,BUILD-MAX-HEAP 和 HEAPSORT

MAX-HESPIFY:维持最大堆的性质。

BUILD-MAX-HEAP:将无序的数据数组构造成一个最大堆。

HEAPSORT:对一个数组进行原址排序。

这里面涉及蛮多知识的,下面分别介绍一下!

最大堆的定义:在最大堆中,最大堆特性是指除了根以外的每个结点i,有A[PARENT(i)] >= A[i]。这样,堆的最大元素就存放在根结点中。

那下面的图片来说,就是序号1为根结点(也叫父结点),要大于序号2和3的元素(2,3也叫子类结点,左子结点和右子结点),其他结点类似按照这个来推

原址排序的定义:在排序输入数组时,只有常数个元素被存放到数组以外的空间中去。就是说不需要花数组那样大的空间来缓存数据,大部分排序都在数组内部进行!

MAX-HESPIFY(过程见下图,详细看代码)

BUILD-MAX-HEAP(过程见下图,详细看代码)

HEAPSORT(过程见下图,详细看代码)

2.4 快速排序

快速排序使用分治策略来把一个数组分为两个子数组。

步骤为:

  1. 从数组中挑出一個元素,称为 "基准"(pivot),
  2. 重新排序数组,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称之为分割(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数组和大于基准值元素的子数组排序。

 如下图所示

3.性能分析

3.1 运行时间

从图可以看出,在n很大时,归并排序和堆排序(它们接近最优)运行时间上比插入排序和快速排序,n值小时,插入和快排较快。实际应用中,快排用的较多,它一般快于堆排序。

归并排序和堆排序都是以二叉树形式,它的高度是lgn,每一层都要进行n次比较,所以最后最坏结果都是nlgn,而插入排序最坏的情况是每一个都要去比较,即n的平方,快排最坏的情况是分组一边0个元素,另一边是n-1,平均情况还是类似归并排序,也是分治法的最优情况,nlgn。

3.2 存储空间

插入排序和快速排序是原址排序算法,归并排序和堆排序不是,所以插入排序和快速排序占用空间小,更节省内存。

4. 程序实现

4.1. main.cpp

 1 #include <iostream>
 2 #include "fy_sort.h"
 3 using namespace std;
 4  
 5 
 6 int main()
 7 { 
 8   fy_sort sort1; 
 9   int num;
10   int a[30],b[30],c[30],d[30];
11   cout<<"please enter the number of input elements: "<<endl;
12   cin >>  num;
13   cout << "Input the elements:\n";
14   for(int i=0;i<num;i++)
15   {
16       cin>>a[i];
17       b[i]=a[i];
18       c[i]=a[i];
19       d[i]=a[i];
20   }
21   cout << "insert_sort:\n";
22   sort1.insert_sort(a,num);//插入排序
23   cout << "merge_sort:\n";
24   sort1.merge_sort(b,0,num-1);//归并排序
25   sort1.display(b,num);
26   cout << "heap_sort:\n";
27   sort1.heap_sort(c,num);//堆排序
28   cout << "quick_sort:\n";
29   sort1.quick_sort(d,0,num-1);//快速排序
30   sort1.display(d,num);
31 
32   return 0;
33 }

4.2  fy_sort.h

 1 #pragma once
 2 
 3 #ifndef FY_SORT_H
 4 #define FY_SORT_H
 5 
 6 class fy_sort //排序类
 7 {
 8 private:
 9     
10     void swap (int& n, int& m);                 //交换函数
11     void merge(int a[],int p,int q,int r);      //归并排序函数
12     inline int left  (int i) {return 2 * i + 1;}//内联函数,用于堆排序的左手序号  
13     inline int right (int i){return 2 *(i + 1);}//内联函数,用于堆排序的右手序号  
14     void max_heapify (int a[], int i);          //最大堆排序中的核心,维护最大堆的性质,即父类节点大于子类节点
15     void build_max_heap (int a[], int n);       //建造最大堆,调用n/2次max_heapify,将无序的数组构造成最大堆
16     int Partition(int a[], int beg, int end);   //快排的核心,即分割,将大于数组最后一个元素的元素移到右边,小于的移到左边
17 
18 public:
19 
20    void display(const int a[],int k);        //显示函数
21    void insert_sort(int a[],int n);          //插入排序
22    void quick_sort(int a[],int beg, int end);//快速排序(递归调用)
23    void merge_sort(int a[],int p,int r);     //归并排序(递归调用)
24    void heap_sort(int a[],int n);            //堆排序
25    
26 };
27 
28 #endif

4.3 fy_sort.cpp

  1 #include "fy_sort.h"
  2 #include<iostream>
  3 
  4 using namespace std;
  5 
  6 int heap_size; 
  7 //显示函数
  8 void fy_sort::display(const int a[],int k) 
  9 {
 10     for(int i=0;i<k;i++)
 11        cout<<a[i]<<" ";
 12        cout<<endl;
 13 }
 14 //交换函数
 15 void fy_sort::swap (int& n, int& m)  
 16 {  
 17     int temp;  
 18     temp = n;  
 19     n = m;  
 20     m = temp;  
 21 } 
 22 
 23 void fy_sort::insert_sort(int a[],int k)//插入排序
 24 {
 25      int key;
 26      for (int i=1;i<k;i++)
 27      {
 28       key=a[i]; //先将要比较的元素暂存,后面要替换
 29       int j=i-1;
 30       //循环实现的功能找到比a[i]大的前面元素(序号小的),找到替换,无则不变
 31         while((j>-1)&&(key<a[j])) 
 32         {
 33           a[j+1]=a[j];
 34           j--;
 35         }
 36       a[j+1]=key;
 37      }
 38      display(a,k);    
 39 }
 40 
 41 void fy_sort::merge_sort(int a[],int p,int r) //归并排序
 42 {
 43     if(p<r)
 44     {
 45         int q=(p+r)/2;     //以q值为划分区间,将数组划分成两个小数组
 46         merge_sort(a,p,q); //小数组再划分,递归调用,直到剩下一个
 47         merge_sort(a,q+1,r);//小数组再划分,递归调用,直到剩下一个
 48         merge(a,p,q,r);     //将分解后的最小数组,进行排序和合并
 49     }
 50     
 51 }
 52 
 53 
 54 void fy_sort::merge(int a[],int p,int q,int r)
 55 {
 56     int n1 = q-p+1;  
 57     int n2 = r-q;  
 58     //生成两个新空间,存划分后的数组
 59     int *L = new int[n1+1];  
 60     int *R = new int[n2+1];  
 61     int i, j, k;  
 62     //将大数组的值赋给两个小数组      
 63     for (i=0; i<n1; i++){  
 64         L[i] = a[p+i];  
 65     }  
 66     for (j=0; j<n2; j++){  
 67         R[j] = a[q+j+1];  
 68     }
 69     //确定边界
 70     L[n1] = 10000000;  
 71     R[n2] = 10000000;  
 72     //按位比较,在合并成大数组  
 73     for (i=0, j=0, k=p; k<=r; k++)  
 74     {  
 75         if (L[i]<=R[j])  
 76         {  
 77             a[k] = L[i];  
 78             i++;  
 79         }else{  
 80             a[k] = R[j];  
 81             j++;  
 82         }  
 83     }  
 84     //释放空间  
 85     delete []L;  
 86     delete []R;  
 87 }
 88 
 89 void fy_sort::max_heapify (int a[], int i)  
 90 {   
 91     //左手和右手的序号
 92     int l = left(i);  
 93     int r = right(i);
 94     //largest存储父节点和子节点中最大的数
 95     int largest;  
 96     //子类左结点与父节点比较,将其中大的赋给largest
 97     if ((l < heap_size) && a[l] > a[i])  
 98         largest = l;  
 99     else  
100         largest = i;  
101    //子类左结点与largest比较,将其中大的赋给largest
102     if ((r < heap_size) && a[r] > a[largest])  
103         largest = r;  
104    //若根节点变化,会导致下面分支的最大堆性质可能变化,这里对下面进行重新分堆
105     if (largest != i)  
106     {  
107         swap (a[largest], a[i]);  
108         max_heapify (a, largest);  
109     }  
110 }  
111 
112 void fy_sort::build_max_heap (int a[], int n)  
113 {  
114     heap_size=n; 
115     //记住一点,最大堆是以由底向上分堆
116     for (int i = (n - 1) / 2; i >= 0; i--)  
117         max_heapify (a, i);  
118 }  
119 
120 void fy_sort::heap_sort (int a[], int n)  
121 {  
122     build_max_heap (a, n);
123     //实现的是原址排序,将最大堆转化成从小到大的数组
124     //原理是将最大堆的根节点换成最大堆最末尾的数,然后再进行最大堆
125     //直到只剩下一个节点,即为最小值
126     for (int i = n - 1; i >= 1; i--)  
127     {  
128         swap (a[i], a[0]);  
129         heap_size--;  
130         max_heapify (a, 0);  
131     }  
132     display(a,n);
133 } 
134 //快速排序的核心,也跟堆排序一样,是原址排序
135 int fy_sort::Partition(int a[], int beg, int end)
136 {
137     int sentinel = a[end];
138     int i = beg-1;
139     //这个循环以最后一个为基准,小于a[end]的放到左边
140     //大于a[end]放到右边
141     for(int j=beg; j<=end-1; ++j)
142     {
143         if(a[j] <= sentinel)
144         {
145             i++;
146             swap(a[i], a[j]);
147         }
148     }
149     swap(a[i+1], a[end]);
150  
151     return i+1;
152 }
153 
154 void fy_sort::quick_sort(int a[], int beg, int end)
155 {
156     if(beg < end)
157     {
158         int pivot = Partition(a, beg, end);
159         //后边这两个是对一部分划分的左右部分在进行快排
160         quick_sort(a, beg, pivot-1);
161         quick_sort(a, pivot+1, end);
162     }
163     
164 }

5.运行结果

6.结束语

建议大家去看算法导论,里面讲的非常细,就是太厚了,容易看不下去!(笑哭)挑重点看吧,下次见!

这里再分享两位网友的笔记,写得很好!

Tanky Woo:  《算法导论》学习总结—【目录】

Adoo          :   《算法导论》笔记汇总

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

算法之旅 | 选择排序法

HTML5学堂-码匠:数据快速的计算与排序,与前端页面性能有直接的关系。由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,...

3325
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1272
来自专栏数据结构与算法

cf314E. Sereja and Squares(dp)

给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。 合法序...

1557
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

3594
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1856
来自专栏鸿的学习笔记

两个字符串算法

这部分主要使用了动态规划的技术,就是如果两个最大公共子序列相等的话,必然前面的也相等

512
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3698
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

46910
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

2804
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3425

扫码关注云+社区

领取腾讯云代金券