白话经典算法系列之九 从归并排序到数列的逆序数对(微软笔试题)

白话经典算法系列之九 从归并排序到数列的逆序数对(微软笔试题)
首先来看看原题   微软2010年笔试题 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2,4,3,1}中,2和1,4和3,4和1,3和1是逆序数对,因此整个数组的逆序数对个数为4,现在给定一数组,要求统计出该数组的逆序数对个数。   计算数列的逆序数对个数最简单的方便就最从前向后依次统...

白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇
在我的博客对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解,并做成了电子书以供大家下载。下载地址为:http://download.csdn.net/detail/morewindows/4443208。 有网友提议到这本《MoreWindows白话经典算法之七大排序》电子书讲解细致用来平时学习是非常好的,但是页数有22页,不太合适做面试前的复习资料。因此在这里将这七种常用的...

白话经典算法系列之七 堆与堆排序

白话经典算法系列之七 堆与堆排序
堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。 二叉堆满足二个特性: 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。 2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。 当父结点的键值总是大于或等于任何一个子节点的键...

白话经典算法系列之六 快速排序 快速搞定

白话经典算法系列之六 快速排序 快速搞定
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。 总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快...

白话经典算法系列之五 归并排序的实现

白话经典算法系列之五 归并排序的实现
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。 [cpp] //将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n...

白话经典算法系列之四 直接选择排序及交换二个数据的正确实现

白话经典算法系列之四 直接选择排序及交换二个数据的正确实现
直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。   设数组为a[0…n-1]。 1.      初始时,数组全为无序区为a[0..n-1]。令i=0 2.      在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区...

白话经典算法系列之三 希尔排序的实现

白话经典算法系列之三 希尔排序的实现
资料来源于互联网,版权为:MoreWindows! 希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直...

白话经典算法系列之二 直接插入排序的三种实现

白话经典算法系列之二 直接插入排序的三种实现
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。简单来说就是:取出一个元素,寻找插入位置! 设数组为a[n]。 1.初始时,a[0]看成有序区,无序区为a[1..n-1]。 2.i=1循环到i=n-1,将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。排序完成。 代码如下:(由小到大排序) [cpp] void Insertso...

白话经典算法系列之一 冒泡排序的三种实现

白话经典算法系列之一 冒泡排序的三种实现
在CSDN看到的白话算法,不错,认真阅读了一边感觉有用,修改和完善了部分代码,版权为:MoreWindows,如果作者不希望本站转载,发EMAIL致10814750#qq.com,谢谢! 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。 2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个...
Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录