- 浏览: 842454 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (530)
- Java编程 (64)
- C/C++/D (6)
- .Net/C# (9)
- Ruby (12)
- JavaScript (77)
- XML (1)
- JSON (1)
- Ajax (17)
- ExtJs (81)
- YUI (1)
- JQuery (7)
- DWR (1)
- HTML (7)
- CSS (7)
- Database (6)
- PowerDesigner (23)
- DB2 (2)
- Oracle (57)
- MS SQL Server (8)
- MySQL (6)
- JSP/Servlet/JSTL/TagLib (3)
- Spring (1)
- Hibernate (0)
- iText (0)
- Struts (0)
- Struts2 (0)
- iReport (0)
- FreeMarker (0)
- HttpClient (1)
- POI (6)
- FckEditor (15)
- Eclipse / MyEclipse (10)
- IntelliJ IDEA (0)
- NetBeans (0)
- Tomcat (11)
- WebLogic (1)
- Jboss (3)
- jetty (4)
- IIS (2)
- CVS/VSS (1)
- FTP (1)
- Windows/DOS (6)
- Linux/Unix (0)
- 软件建模 UML (0)
- Design Pattern & Thinking In Programming (10)
- 数据结构与算法 (12)
- 软件项目管理 (9)
- 行业应用解决方案 (3)
- 电脑软件与故障解决 (13)
- 编程语言 (1)
- 十万个为什么 (3)
- JBPM (2)
- sysbase (2)
- JDBC (8)
- Ant (2)
- Case-计算机辅助软件工程 (1)
- WebService (4)
- 浏览器 (1)
最新评论
-
gaoqiangjava:
同一楼,还请大手帮解决
JAVA读取word文件 -
hyl523:
// 判断数组中的第一个值是否未定义,如果未定义,便定义为空对 ...
javascript面向对象之二 命名空间 -
ping12132200:
ping12132200 写道我抱着个错不是因为:body标签 ...
extjs在IE报对象不支持此属性或方法 -
ping12132200:
我抱着个错不是因为:body标签内的第一个元素不能为文本tex ...
extjs在IE报对象不支持此属性或方法 -
fireinjava:
呀,不错,转走了,谢谢啦~
利用OpenOffice将word转换成PDF
一、简单排序算法
由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。
1.冒泡法:
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次
其他:
第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次
上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换,
显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意,我们给出O方法的定义:
若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没
学好数学呀,对于编程数学是非常重要的!!!)
现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的
有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),
复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因,我们通常都是通过循环次数来对比算法。
2.交换法:
交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次
其他:
第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次
从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以
只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。
3.选择法:
现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)
这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中
选择最小的与第二个交换,这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp; //一个存储值。
int iPos; //一个存储下标。
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp) //选择排序法就是用第一个元素与最小的元素交换。
{
iTemp = pData[j];
iPos = j; //下标的交换赋值。
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数:6次
交换次数:2次
其他:
第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数:6次
交换次数:3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n
所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。
4.插入法:
插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数:6次
交换次数:3次
其他:
第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数:4次
交换次数:2次
上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,
因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单
排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似
选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些,所以我们浪费了时间。
最终,我个人认为,在简单排序算法中,选择法是最好的。
二、高级排序算法:
高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后
把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使
用这个过程(最容易的方法——递归)。
1.快速排序:
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)
//当左边部分有值(left<j),递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i),递归右半边
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况
1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。
2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。
第一层递归,循环n次,第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变
成交换法(由于使用了递归,情况更糟),但是糟糕的情况只会持续一个流程,到下一个流程的时候就很可能已经避开了该中间的最大和最小值,因为数组下标变化了,于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大??呵呵,你完全不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。
如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢
于快速排序(因为要重组堆)。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/Yidon/archive/2007/10/30/1855520.aspx
//选择排序法SelectionSort(int arr[],int n)
template <typename T>
void SelectionSort(T arr[],int n)
{
int smallIndex; //表中最小元素的下标
int pass,j; //用来扫描子表的下标
T temp; //用来交换表元素的临时变量
//pass的范围是0~n-2
for (pass=0;pass<n-1;pass++)
{
//从下标pass开始扫描子表
smallIndex=pass;
//j遍历整个子表arr[pass+1]到arr[n-1]
for(j=pass+1;j<n;j++)
//如果找到更小的元素,则将该位置赋值给smallIndex
if(arr[j]<arr[smallIndex])
smallIndex=j;
//如果smallIndex和pass不在相同的位置
//则将子表中的最小项与arr[pass]交换
if(smallIndex!=pass)
{
temp=arr[pass];
arr[pass]=arr[smallIndex];
arr[smallIndex]=temp;
}
}
}
/************************************************************************
双端选择排序算法:是上面选择排序算法的变种,可以定位每个子表中最小和最大元素
并把它们分别放在子表的开头和结尾.
************************************************************************/
//双端选择排序算法函数deSelSort()的实现
template <typename T>
void deSelSort(T arr[],int n)
{
int smallIndex,largeIndex; //表中最小及最大元素的下标
int leftPass=0,rightPass=n-1,i,j; //用来从表左边及右边扫描子表的下标
T temp; //用于交换元素的临时变量
while (leftPass<=rightPass)
{
//从左边及右边开始扫描子表
smallIndex=leftPass;
largeIndex=rightPass;
//j和i遍历整个子表arr[LeftPass]~arr[rightPass]
for (i=leftPass+1;i<rightPass;i++)
//如果找到更小的元素,则将该位置赋值给smallIndex
if (arr[i]<arr[smallIndex])
smallIndex=i;
//如果smallIndex和leftPass不在相同的位置
//则将子表中的最小项与arr[pass]交换
if (smallIndex!=leftPass)
{
temp=arr[leftPass];
arr[leftPass]=arr[smallIndex];
arr[smallIndex]=temp;
}
for (j=rightPass-1;j>leftPass;j--)
if(arr[j]>arr[largeIndex])
largeIndex=j;
if(largeIndex!=rightPass)
{
temp=arr[rightPass];
arr[rightPass]=arr[largeIndex];
arr[largeIndex]=temp;
}
//从两头收缩子表
leftPass++;
rightPass--;
}
}
//自编冒泡法排序算法函数bubbleSort()的实现
template <typename T>
int bubbleSort(T arr[],int n)
{
bool exchanged=false; //是否发生交换
int i,j; //用于遍历子表的下标
T temp; //用于交换元素的临时变量
//开始遍历过程,以下标j构成子表,共有n-1个子表
for (j=n-1;j>=0;j--) //j从后往前收缩n-1~0,以构成子表0~n-1,0~n-2,0~n-3..0~1
{
exchanged=false;
for (i=0;i<j;i++) //遍历子表范围0~j
{
if (arr[i]>arr[i+1])
{
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
exchanged=true;
}
}
if (!exchanged) return n-j-1;//如果在一次遍历中没有发生交换,则表示已经
//排序好,中断遍历过程
}
return n-1-j;
}
//冒泡法排序一般算法函数bubbleSortEx()的实现
template <typename T>
int bubbleSortEx(T arr[],int n)
{
int i,pass; //用于遍历子表的下标
T temp; //用于交换元素的临时变量
//开始遍历过程,以下标j构成子表,共有n-1个子表
for (pass=0;pass<n;pass++) //pass从后往后扩大0~n-1,以构成子表0~n-1,0~n-2,0~n-3..0~1
{
for (i=0;i<n-pass;i++) //遍历子表范围0~n-pass
{
if (arr[i]>arr[i+1])
{
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}
return pass;
}
本文转自:http://hi.baidu.com/zhaoyh%5Fch2000/blog/item/479fd93790e6afd7a3cc2b8f.html
发表评论
-
数据结构自学网站
2010-12-13 00:37 982http://student.zjzk.cn/course_w ... -
算法的时间复杂度(计算实例)
2010-07-04 14:54 1035定义:如果一个问题 ... -
大O表示法是什么?
2010-07-04 14:48 1194目录 一,算法的目标 二,算法的执行时间 ... -
自动状态机实现经典过河问题
2010-07-03 15:12 1721一、实验题目 使用有限自动机编程解决如下问题 ... -
常用的排序算法(包括冒泡排序,选择排序,插入排序,希尔排序,快速排序)
2010-01-13 23:29 1558排序算法在程序中会用到很多,这里介绍几种常见的排序方法以及比较 ... -
几个简单常用的排序算法(面试会遇到)
2010-01-13 23:29 14981:quicksort 下面这个示意图很生动的演示出来快速排序 ... -
常用排序算法 c源码
2010-01-13 23:27 1076一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的 ... -
常用的排序算法
2010-01-13 23:26 10171选择排序 先在整个序列中选出关键字值最小的元素,如果它不是 ... -
例举四种常用排序算法
2010-01-13 23:25 860●插入排序(Insertion Sort)的基本思想是:每次将 ... -
几种常用的排序算法
2010-01-13 23:24 765C#几种常用的排序算法 ... -
B树、B-树、B+树、B*树
2010-01-09 20:30 1843B树 即二叉搜索树: ...
相关推荐
【C++常用排序算法】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。C++作为一种强大的编程语言,提供了多种实现排序的方法。本文将详细介绍C++中常用的几种排序算法及其实现。 1. **冒泡排序** 冒泡...
以下是对C++中几种常用排序算法的详细说明: 1. **选择排序(Selection Sort)**: 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始...
C++常用排序算法学习笔记 本文档主要介绍了五种常用的排序算法,分别是sort、random_shuffle、merge、reverse四种算法。这些算法在实际开发中非常重要,需要开发者熟练掌握。 5.3.1 sort sort是C++中最常用的排序...
根据给定文件的信息,本文将深入探讨C++中几种常用的排序算法,并对其性能进行分析。 ### 一、基本概念 在计算机科学中,排序是一种重要的数据处理技术,它能够有效地组织数据并提高数据检索的效率。C++作为一种...
选择排序,插入排序,快速排序,冒泡排序,堆排序,希尔排序等各排序算法的源码实现/算法思想/及时间复杂度比较
在编程领域,排序算法是计算机科学中的基础但至关重要的部分,尤其在C++这样的系统级编程语言中。本文将深入探讨C++实现的几种常见排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序以及堆排序。 1. **...
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
这里我们将深入探讨七种常用的排序算法,并通过C++语言实现它们。这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之...
### 关于C++冒泡排序算法的深度解析 在计算机科学与编程领域,排序算法是基础且关键的一部分,其中冒泡排序(Bubble Sort)作为最简单直观的排序算法之一,常被用作教学示例,尤其适合初学者理解排序算法的基本原理...
快速排序在平均情况下的时间复杂度为O(n log n),是实际应用中最常用的排序算法之一。 5. 归并排序(Merge Sort) 归并排序也是基于分而治之的思想,将大数组分成两个小数组,分别排序后再合并成一个有序的大数组。...
在编程领域,排序算法是计算机科学中的核心概念,它们用于对数据进行有序排列。这里我们主要探讨五种常见的排序算法,这些算法的源码你可以在提供的压缩包文件中找到:MergeSort(归并排序)、RadixSort(基数排序)...
快速排序是C++中最常用的排序算法之一,由英国计算机科学家C.A.R. Hoare提出。它使用分治策略,选择一个基准元素,将数组分为两部分,一部分的所有元素都小于基准,另一部分的元素都大于基准,然后递归地对这两部分...
《C C++常用算法手册-带详细目录书签.pdf》是一本专为C++程序员设计的算法学习资源,旨在帮助读者深入理解并掌握常见的编程算法。这本书包含了丰富的算法实例和详细的解析,使得学习过程更为直观易懂。标签“C++”...
【排序算法的C++面向对象实现】 在计算机科学中,排序是处理数据的重要步骤,它旨在将一组无序的数据转化为有序的数据序列。根据处理方式,排序可以分为内部排序和外部排序。内部排序是指整个排序过程都在内存中...
排序算法总结,包括冒泡、插入、选择、快速四种
在编程领域,排序算法是数据结构与算法学习中的核心部分,尤其在C++这样的强类型语言中,理解和熟练掌握各种排序算法对提升编程能力至关重要。本文将深入探讨五种常用的排序算法:快速排序、归并排序、选择排序、...
《C C++常用算法手册》是一本专注于C和C++编程语言中常见算法的实用指南。结合C++ STL(Standard Template Library,标准模板库)的使用,这本书为开发者提供了丰富的算法实现和应用示例,旨在提升程序员在解决复杂...