啪啪拉拉噼里啪啦

初学者天堂资料汇集

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  16 随笔 :: 73 文章 :: 16 评论 :: 0 Trackbacks

2005年4月1日 #

参考文献
 1.C++Primer(第三版) Stanley B.Lippman, Josee Lajoie (中国电力出版社)
 2.C++语言程序设计(第二版) 郑莉 董渊 (清华大学出版社)
 3.C++Primer Plus  Stephen Prata  (人民邮电出版社)
 4.C语言程序设计 谭浩强  清华大学出版社           

C++是从C语言演变过来的,完全可以脱离C而从新学习C++

#include<iostream.h>
void main()
{
  cout<<"welcome to C++ world !!"<<endl;
}

知识点1: *.h 文件被称为头文件.(标准的C++头文件没有后缀) 如iostream.h
            2.*.C 习惯称之为C程序文本文件.(在UNIX系统下则称之为C++文件) C++程序文件的后缀在不同产品中则不同 如 *.CPP  *.CXX...类似的头文件在C++的不同实现中也不相同.
            3.#include 预处理器指示符
            4.#include<> 和#include "   " 区别
               #include<>是标准或者工程文件.  #include" " 表示当前目录下寻找.

#ifdef   bookstore
#define      bookstore
#endif
检查bookstore是否在前面被定义了..
#include<iostream.h>

v1(int x,int y)
{   cout<<"V1"<<endl;
    cout<<"{"<<endl;
 cout<<"x= "<<x<<endl;
 cout<<"y= "<<y<<endl;
 cout<<"}"<<endl;
}

v2(int x,int y)
{   cout<<"V2"<<endl;
    cout<<"{"<<endl;
 cout<<"x= "<<x<<endl;
 cout<<"y= "<<y<<endl;
 cout<<"}"<<endl;
}
void main()
{   int bug;
    #ifdef  bug
 cout<<"welcome to our  C++ world!!"<<endl;
 v1(2,5);
 v2(3,5);
#endif
           

posted @ 2005-04-28 12:26 噼里啪啦的世界 阅读(831) | 评论 (0)编辑 收藏

只要有地区发展不平衡,就难以最终杜绝地区歧视。“穷”绝对不是一件好事,更不是美好道德的源泉,相反,它只是刺激普遍人性中的普遍弱点:嫌贫爱富。

深圳龙岗警方是政府所属的执法部门,今年3月份,竟在辖区内悬挂横幅“凡举报河南籍团伙敲诈勒索犯罪、破获案件的奖励500元”,地区歧视赫然在目,令人难以置信。

4月15日,两位河南籍人士远在郑州向龙岗警方提起司法诉讼,惊动舆论,有朋友认为此举做秀,意在吸引眼球。我的看法是,即使做秀,此类官司也值得打,打得赢要打,打不赢也要打。只有人人形成“秋菊性格”,强势部门才能在百姓面前低头,两者之间才有可能形成正常关系———“法律面前人人平等”。社会公正不是长官恩赐的,也不是小民乞求的,而是一个一个“秋菊”起而抗议,一场一场官司“打”出来的。平民缠讼,尤其是缠强势部门之讼,在过去要被讥讽为泼妇刁民、世风日下,在现代恰恰是公民意识觉醒的标志。

但是,具体到地区歧视这一观念,即使官司打赢了,河南人就能在全国改变他们被歧视的命运吗?我的看法不乐观。原因在于,地区性歧视在人类社会生活中普遍存在,并不植根于知识分子容易想到的文化“基因”或“国民性”问题,而是植根于人性的普遍弱点,这一弱点的起伏消长,是与社会发展不平衡联系在一起的。

我出生在上海,这个城市有一个公开秘密,也是这个城市的不文明标记:全城歧视苏北人。上个世纪50年代,有两个强力因素对苏北人有利,似乎能抵消这一地区歧视:接管这个城市的南下干部不少人操苏北口音,来自苏北红区;从1949年到1976年的国家总理周恩来,操一口淮阴口音,爱看江淮戏,苏北得不能再苏北,全国民众家喻户晓。事实证明,强力因素无济于事,政治归政治,歧视归歧视,生活的“污泥浊水”照样奔流。上海的市民生活并不隐讳这一现象,但与主流意识形态的阶级论不合,官方出版物始终不能正视。倒是两个外国人,一个来自美国,一个来自德国,对这一现象发生研究兴趣,以此为题撰写社会学博士论文,在学界颇得好评,其中一位德国学者我还认识。

我插队在河南,求学在西安。到西安后,发现一个城市奇观:半城皆乡音,满目河南人。不久即发现,河南人再多,在西安还是被歧视,原因很简单:他们大多是灾荒年景的流民,以及流民的后代。

这时我才想起在河南的经历,被歧视者内部,还有更细一层的地区歧视,豫西人看不起豫东人。原因也相通:豫东自然条件恶劣,一旦发生灾荒,豫东灾民顺陇海线向西流动,先经过豫西,后到达西安。而在上海,被歧视的苏北人内部也有类似现象:扬州一带的苏北人看不起盐城一代的苏北人,甚至认为苏北人在上海的不良形象是被后者败坏的。原因惊人地相似:一旦发生灾荒,盐城阜宁一带的灾民顺运河南下,先经过扬州,再渡江到上海。

盐、阜相比扬州,不仅在地理上更“北方”,社会经济发展更落后,流民进上海后能够找到的职业更低贱,由此被认为更“侉”,更粗野。发现地区歧视在中国普遍存在,一度使我心绪难平;再看到被歧视者内部居然继续划分地区歧视,则使我沮丧无言。

后来到哈佛大学短期访问,发现地区歧视在美国白人内部也存在。查尔斯河北畔的剑桥市,隐隐看不起河对岸波士顿地区的爱尔兰人社区。我因为贪图房租便宜,恰好住进了那个社区,却因为听力不好,实在听不出一河之隔的英语有什么口音差异。我曾请一个爱尔兰裔的美国教授林琪以放大的口型,夸张的口气,演示她的祖籍口音,才勉强听出一点差别。令我惊讶的是,那个地区受人尊崇的肯尼迪总统,并不是出身在查尔斯河的北岸,而是遭人歧视的南岸,恰好就在爱尔兰社区。他去世后,按美国规矩为前总统建立的肯尼迪图书馆就建在我住处不远的海边,脚一抬就到,我曾无数次在那里留连。

可惜总统归总统,歧视归歧视,这就和周恩来的政治魅力无助于缓解上海对苏北人的歧视差不多。林琪告诉我,这一歧视缘起19世纪中叶那场著名的马铃薯灾荒,爱尔兰人大批来北美新英格兰地区乞讨求生,地位低下,招人嫌弃。20世纪90年代爱尔兰总理访美,还特意要求在哈佛广场的空地上塑造一组饥民哀号求救的铜像,以纪念那个可怕年月。林琪还告诉我,随着爱尔兰社区社会经济发展,这一歧视正在淡化,相比她记事的童年时代,现在已经好多了,几乎可以忽略不计,以致我要求她演示爱尔兰口音时,她没有丝毫不快,而是以开玩笑的心态在讲解一个历史故事,以及地区歧视发生的根本原因了。

只要有地区发展不平衡,就难以最终杜绝地区歧视。这是一个令人很不愉快的现实,之所以不愉快,是因为它最终与一个“穷”字相连接。“穷”绝对不是一件好事,更不是美好道德的源泉,相反,它只是刺激普遍人性中的普遍弱点:嫌贫爱富。普遍人性普遍存在,地不分东、西,人不分黄、白,只要有地区发展不平衡,就会有河南人问题,苏北人问题,乃至爱尔兰人问题。而爱尔兰人故事告诉我们的是:地区歧视当然不可取,更不能放纵这一观念蔓延到执法、司法行为,但只有从根本上消除地区发展的失衡,才能最终消解这一丑恶观念。在这个意义上,我赞成“发展才是硬道理”,只是这个发展不能仅限于经济,应该包括文化,文化发展中最重要的一环不是改造“国民性”,而是实施实实在在的教育机会平等;还应该包括政治发展,政治发展中最重要一环是司法公正,在最终克服地区发展不平衡之前,首先要做到也可以做到的,是“法律面前人人平等”。

作者:上海大学文学院教授朱学勤黄华

posted @ 2005-04-24 22:06 噼里啪啦的世界 阅读(1075) | 评论 (0)编辑 收藏

import java.io.*;
public class application01
{
 
 public static void main(String[] args)
 {   char c=' ' ;
    String s="";
  System.out.println("Enter a character Please ");
  try
  { 
   BufferedReader in= new BufferedReader(new InputStreamReader(System.in));
   s=in.readLine();
  // c=(char)System.in.read();
  } catch(IOException e){};
  System.out.println("you''ve a  "+s);
  
 }
 
}


  in= new BufferedReader(new InputStreamReader(System.in));
   s=in.readLi BufferedReader ne();
posted @ 2005-04-17 07:31 噼里啪啦的世界 阅读(944) | 评论 (0)编辑 收藏

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
public class myjava01 extends Applet implements ActionListener
{
 Label  p1;
 TextField input,output;
 public void init()
 {
  p1=new Label("请输入您的名字");
        input=new TextField(10);
     output=new TextField(50);
  add(p1);
  add(input);
  add(output);
  input.addActionListener(this);
 }
 public void actionPerformed(ActionEvent e)
 {
       output.setText(input.getText()+",welcome to our world");
     }
}



本程序知识点:
程序需要加载三个包
import java.awt.event.*;
import java.awt.*;
import java.applet.*;
凡是java.applet程序的 必须加载java.applet.* 包
凡是使用图形界面的    必须加载Java.awt包
凡是使用图形界面事件处理的 必须加载java.awt.event.*包

程序定义的一个类,必须始Applet的子类 例如
public class Applet01 extends  Applet  implements Actionlistener
implements Actionlistener 还是一个动作事件的Action的监听者。

init()是建立一个对象
并用ADD() 加载到图形界面中。。
input.addActionListener(this) 注册到监听者 否则程序不能响应回车键
定义了一个acctionPerformed()方法。。。

posted @ 2005-04-17 06:45 噼里啪啦的世界 阅读(737) | 评论 (1)编辑 收藏

jsp:include              页面请求时候 引入一个文件
jsp:usebean             寻找一个或实例化一个javabean
jsp:getProperty       输出JVAVBEAN的属性
jsp:forward            把请求转为一个新的页面
jsp:plugin                根据浏览器类型为java插件设置object 或Embed
jsp:setProperty       设置JAVABEAN的属性
posted @ 2005-04-12 23:30 噼里啪啦的世界 阅读(582) | 评论 (0)编辑 收藏

常用的类
BufferedReader
BufferedWriter
FileReader
FileWirter
String
Integer

常用的包
java.lang
java.awt
java.io
java.util
java.sql
常用的接口
Remote
List
Map
Doucment
Nodelist
posted @ 2005-04-12 23:23 噼里啪啦的世界 阅读(988) | 评论 (0)编辑 收藏

标准建模语言UML,
提供了 例图,静态图(类图,对象图,包图),行为图,交互图(顺序图,合作图) 实现图

posted @ 2005-04-12 23:17 噼里啪啦的世界 阅读(590) | 评论 (1)编辑 收藏

JAVA DATA OBJECT... java对象持久化的新规范。
存取某种数据仓库中对象标准API  JDO提供透明的对象存储。。。
JDBC是面向关系的数据库JDO更通用。
posted @ 2005-04-12 23:14 噼里啪啦的世界 阅读(724) | 评论 (0)编辑 收藏

Struts 是基于JAVASERVELET/JSP技术的 web开发的开放源代码的framwork。。。
是基于MVC( MODEL-VIEW-CONTROLLER) 设计模式的应用架构
1。包含一个controller servlet 能够把用户的请求发送到一个对应的Action对象
2。包含了自用的tag库。提供controller servlet 提供联机帮户 帮助开发人员创建交互式表单
3。提供一些列使用对象。如 xml处理等。 java reflection APIS自动处理javabean

posted @ 2005-04-12 23:10 噼里啪啦的世界 阅读(586) | 评论 (0)编辑 收藏

快速排序(QuickSort)

1、算法思想
     快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

(1) 分治法的基本思想
     分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

(2)快速排序的基本思想
     设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
①分解:
   
 在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
  注意:
     划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
     R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
                  其中low≤pivotpos≤high。
②求解:
    
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合:
   
 因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。

2、快速排序算法QuickSort
  void QuickSort(SeqList R,int low,int high)
   { //对R[low..high]快速排序
     int pivotpos; //划分后的基准记录的位置
     if(low<high){//仅当区间长度大于1时才须排序
        pivotpos=Partition(R,low,high); //对R[low..high]做划分
        QuickSort(R,low,pivotpos-1); //对左区间递归排序
        QuickSort(R,pivotpos+1,high); //对右区间递归排序
      }
    } //QuickSort

  注意:
     为排序整个文件,只须调用QuickSort(R,1,n)即可完成对R[l..n]的
posted @ 2005-04-01 07:18 噼里啪啦的世界 阅读(652) | 评论 (0)编辑 收藏

交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
     应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

冒泡排序

1、排序方法

     将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(1)初始
     R[1..n]为无序区。

(2)第一趟扫描
     从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key<R[j].key,则交换R[j+1]和R[j]的内容。
     第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。

(3)第二趟扫描

     扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
     最后,经过n-1 趟扫描可得到有序区R[1..n]
  注意:
     第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。

2、冒泡排序过程示例
     对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示

3、排序算法
(1)分析
     因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。
     若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。

(2)具体算法

  void BubbleSort(SeqList R)
   { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
     int i,j;
     Boolean exchange; //交换标志
     for(i=1;i<n;i++){ //最多做n-1趟排序
       exchange=FALSE; //本趟排序开始前,交换标志应为假
       for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描
        if(R[j+1].key<R[j].key){//交换记录
          R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元
          R[j+1]=R[j];
          R[j]=R[0];
          exchange=TRUE; //发生了交换,故将交换标志置为真
         }
       if(!exchange) //本趟排序未发生交换,提前终止算法
             return;
     } //endfor(外循环)
    } //BubbleSort
posted @ 2005-04-01 07:17 噼里啪啦的世界 阅读(286) | 评论 (0)编辑 收藏

 希尔排序(Shell Sort)是插入排序的一种。因D.L.Shell于1959年提出而得名。

希尔排序基本思想

  基本思想:
     先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
     该方法实质上是一种分组插入方法。

给定实例的shell排序的排序过程

     假设待排序文件有10个记录,其关键字分别是:
        49,38,65,97,76,13,27,49,55,04。
     增量序列的取值依次为:
        5,3,1
     排序过程如【动画模拟演示】。

Shell排序的算法实现

1. 不设监视哨的算法描述

  void ShellPass(SeqList R,int d)
   {//希尔排序中的一趟排序,d为当前增量
     for(i=d+1;i<=n;i++) //将R[d+1..n]分别插入各组当前的有序区
       if(R[i].key<R[i-d].key){
         R[0]=R[i];j=i-d; //R[0]只是暂存单元,不是哨兵
         do {//查找R[i]的插入位置
            R[j+d];=R[j]; //后移记录
            j=j-d; //查找前一记录
         }while(j>0&&R[0].key<R[j].key);
         R[j+d]=R[0]; //插入R[i]到正确的位置上
       } //endif
   } //ShellPass

  void  ShellSort(SeqList R)
   {
    int increment=n; //增量初值,不妨设n>0
    do {
          increment=increment/3+1; //求下一增量
          ShellPass(R,increment); //一趟增量为increment的Shell插入排序
       }while(increment>1)
    } //ShellSort
  注意:
     当增量d=1时,ShellPass和InsertSort基本一致,只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0",以防下标越界。

2.设监视哨的shell排序算法
     具体算法【参考书目[12] 】

算法分析

1.增量序列的选择

     Shell排序的执行时间依赖于增量序列。
     好的增量序列的共同特征:
  ① 最后一个增量必须为1;
  ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
     有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。

2.Shell排序的时间性能优于直接插入排序
     希尔排序的时间性能优于直接插入排序的原因:
  ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
  ②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
  ③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
     因此,希尔排序在效率上较直接插人排序有较大的改进。

3.稳定性
     希尔排序是不稳定的。参见上述实例,该例中两个相同关键字49在排序前后的相对次序发生了变化。
posted @ 2005-04-01 07:16 噼里啪啦的世界 阅读(168) | 评论 (0)编辑 收藏

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
     本节介绍两种插入排序方法:直接插入排序和希尔排序。

直接插入排序基本思想

1、基本思想

     假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。

2、第i-1趟直接插入排序:
     通常将一个记录R[i](i=2,3,…,n-1)插入到当前的有序区,使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
     排序过程的某一中间时刻,R被划分成两个子区间R[1..i-1](已排好序的有序区)和R[i..n](当前未排序的部分,可称无序区)。
     直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量法。
     插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理,此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置,须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

一趟直接插入排序方法

1.简单方法

     首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置,腾出k位置上的空间插入R[i]。
  注意:
     若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字,则R[i]就是插入原位置。

2.改进的方法
  一种查找比较操作和记录移动操作交替地进行的方法。
具体做法:
     将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1,i-2,…,1)的关键字进行比较:
     ① 若R[j]的关键字大于R[i]的关键字,则将R[j]后移一个位置;
      ②若R[j]的关键字小于或等于R[i]的关键字,则查找过程结束,j+1即为R[i]的插入位置。
     关键字比R[i]的关键字大的记录均已后移,所以j+1的位置已经腾空,只要将R[i]直接插入此位置即可完成一趟直接插入排序。

直接插入排序算法

1.算法描述

  void lnsertSort(SeqList R)
   { //对顺序表R中的记录R[1..n]按递增序进行插入排序
    int i,j;
    for(i=2;i<=n;i++) //依次插入R[2],…,R[n]
      if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys,则R[i]
                              //应在原有位置上
        R[0]=R[i];j=i-1; //R[0]是哨兵,且是R[i]的副本
        do{ //从右向左在有序区R[1..i-1]中查找R[i]的插入位置
         R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
         j-- ;
         }while(R[0].key<R[j].key); //当R[i].key≥R[j].key时终止
        R[j+1]=R[0]; //R[i]插入到正确的位置上
       }//endif
   }//InsertSort

posted @ 2005-04-01 07:15 噼里啪啦的世界 阅读(321) | 评论 (0)编辑 收藏

1.选择排序
   选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
     常用的选择排序方法有直接选择排序和堆排序。

直接选择排序(Straight Selection Sort)

1、直接选择排序的基本思想

     n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
 ①初始状态:无序区为R[1..n],有序区为空。
 ②第1趟排序
     在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  ……
 ③第i趟排序
  第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
     这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

2、直接选择排序的过程
  对初始关键字为49、38、65、97、76、13、27和49的文件进行直接选择排序的过程【参见动画演示

3、算法描述
  直接选择排序的具体算法如下:
 void SelectSort(SeqList R)
 {
   int i,j,k;
   for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)
     k=i;
     for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]
       if(R[j].key<R[k].key)
         k=j; //k记下目前找到的最小关键字所在的位置
       if(k!=i){ //交换R[i]和R[k]
         R[0]=R[i];R[i]=R[k];R[k]=R[0]; //R[0]作暂存单元
        } //endif
     } //endfor
  } //SeleetSort

4、算法分析
(1)关键字比较次数
     无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:
     n(n-1)/2=0(n2)

(2)记录的移动次数
     当初始文件为正序时,移动次数为0
     文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
     直接选择排序的平均时间复杂度为O(n2)。

(3)直接选择排序是一个就地排序

(4)稳定性分析
     直接选择排序是不稳定的

2.冒泡排序
3.字符转换
posted @ 2005-04-01 07:15 噼里啪啦的世界 阅读(692) | 评论 (2)编辑 收藏

1 什么叫作用域?什么叫局部变量?什么叫全局变量?、
作用域是一个标识符在程序正文中有效的的区域。
局部变量具有块作用域的变量
全局变量具有文件作用域的变量

变量有那几种存储类型

auto  采用堆栈方式分配内存空间,属于暂时性存储,其存储空间可以被若干变量多次覆盖使用
register 存储类型  存放在寄存器中
extern  所有程序和函数段都可引用
static  在内存中固定地址存放 整个程序运行期间都有效。。
posted @ 2005-04-01 07:08 噼里啪啦的世界 阅读(120) | 评论 (0)编辑 收藏