没有合适的资源?快使用搜索试试~ 我知道了~
白话经典算法之七大排序
需积分: 30 1 下载量 33 浏览量
2013-03-18
17:09:37
上传
评论 1
收藏 574KB PDF 举报
温馨提示
试读
25页
很不错,通俗易懂 适合各个阶段的程序员阅读
资源推荐
资源详情
资源评论
MoreWindows 白话经典算法之七大排序(第
2 版)
这是本人在研一上课时所整理的文档,包括冒泡排序,直接
插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆
排序这七种常用的排序方法,这些文章不仅使我在考试中取了不
错的成绩,也为后来顺利面过迅雷,腾讯,微软打下了良好的基
础,现在整理成电子书形式,希望能对大家有所帮助。第 2 版新
加入了总结篇,有助于大家的复习。
白话经典算法之七大排序目录
1.白话经典算法系列之一 冒泡排序的三种实现
2.白话经典算法系列之二 直接插入排序的三种实现
3.白话经典算法系列之三 希尔排序的实现
4.白话经典算法系列之四 直接选择排序
5.白话经典算法系列之五 归并排序的实现
6.白话经典算法系列之六 快速排序 快速搞定
7.白话经典算法系列之七 堆与堆排序
8.白话经典算法系列之总结篇
By MoreWindows (http://blog.csdn.net/MoreWindows)
该文档版权归 MoreWindows 所有(morewindows@126.com ),欢迎大家访问我的博客。
一.白话经典算法系列之一 冒泡排序的三种实现
冒泡排序是非常容易理解和实现,以从小到大排序举例:
设数组长度为N。
1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交
换。
2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就
“沉”到数组第N-1个位置。
3.N=N-1,如果N不为0就重复前面二步,否则排序完成。
按照定义很容易写出代码:
//冒泡排序1
void BubbleSort1(int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 1; j < n - i; j++)
if (a[j - 1] > a[j])
Swap(a[j - 1], a[j]);
}
下面对其进行优化,设置一个标志,如果这一趟发生了交换,则为true,否则为
false。明显如果有一趟没有发生交换,说明排序已经完成。
//冒泡排序2
void BubbleSort2(int a[], int n)
{
int j, k;
bool flag;
k = n;
flag = true;
while (flag)
{
flag = false;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = true;
}
k--;
}
}
再做进一步的优化。如果有100个数的数组,仅前面10个无序,后面90个都已排
好序且都大于前面10个数字,那么在第一趟遍历后,最后发生交换的位置必定小
于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二次只要从数
组头部遍历到这个位置就可以了。
//冒泡排序3
// By MoreWindows (http://blog.csdn.net/MoreWindows)
void BubbleSort3(int a[], int n)
{
int j, k;
int flag;
flag = n;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
冒泡排序毕竟是一种效率低下的排序方法,在数据规模很小时,可以采用。数据
规模比较大时,最好用其它排序方法。
二.白话经典算法系列之二 直接插入排序的三种实现
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关
键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成
为止。
设数组为 a[0…n-1]。
1. 初始时,a[0]自成 1 个有序区,无序区为 a[1..n-1]。令 i=1
2. 将 a[i]并入当前的有序区 a[0…i-1]中形成 a[0…i]的有序区间。
3. i++并重复第二步直到 i==n-1。排序完成。
下面给出严格按照定义书写的代码(由小到大排序):
void Insertsort1(int a[], int n)
{
int i, j, k;
for (i = 1; i < n; i++)
{
//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一个合适的位置
if (j != i - 1)
{
//将比a[i]大的数据向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//将a[i]放到正确位置上
a[k + 1] = temp;
}
}
}
这样的代码太长了,不够清晰。现在进行一下改写,将搜索和数据后移这二个步
骤合并。即每次a[i]先和前面一个数据a[i-1]比较,如果a[i] > a[i-1]说明a[0…i]也
是有序的,无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一
边向前搜索,当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。
void Insertsort2(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
if (a[i] < a[i - 1])
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写,用数据交换代
替数据后移。如果a[j]前一个数据a[j-1] > a[j],就交换a[j]和a[j-1],再j--直到a[j-1]
<= a[j]。这样也可以实现将一个新数据新并入到有序区间。
//直接插入排序
// By MoreWindows (http://blog.csdn.net/MoreWindows)
void Insertsort3(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
Swap(a[j], a[j + 1]);
}
剩余24页未读,继续阅读
资源评论
lv104788313
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功