快速排序实验报告

快速排序实验报告

一、课程名称：算法设计与分析

二、指导老师：张锦雄

三、项目名称：快速排序

四、实验类型：验证

五、主要实验内容及要求：

要求按快速排序原理实现非减序排序；

待排数据可键盘输入，也可读文本文件输入；

键盘输入时待排数据个数由输入确定，文件输入时数据格式如下所示；

排序时不能移动数据；

要求显示排序结果。

输入数据的文本文件格式：第1行为数据个数，第2行开始每行一个数据。

如：data.txt

14

19.4

30.43

26.88

7.62 有14行

┋

12.7

21.9

所需主要仪器及现有套数：带usb接口微机。

六、编译工具：Microsoft Visual Studio 2010

七、程序源码：

1.#include

2.#include

ing namespace std;

4.

5.int partition(double a[],int b[],int p,int r)

6.{

7.int i=p,j=r+1;

8.double x=a[b[p]];

9.while(true)

10.{

11.while(a[b[++i]]

12.while(a[b[--j]]>x);

13.if(i>=j)break;

14.swap(b[i],b[j]);

15.}

16.swap(b[p],b[j]);

17.return j;

18.}

19.void quikesort(double a[],int b[],int p,int r)

20.{

21.if(p

22.{

23.int q=partition(a,b,p,r);

24.quikesort(a,b,p,q-1);

25.quikesort(a,b,q+1,r);

26.}

27.}

28.void input()

29.{

30.int s;

31.cout<<"请输入数据个数"<

32.cin>>s;

33.double *a=new double[s];

34.int *b=new int[s];

35.for(int e=0;e

36.b[e]=e;

37.cout<<"请输入数据"<

38.for(int f=0;f

39.cin>>a[f];

40.quikesort(a,b,0,s-1);

41.cout<<"排序前数据为："<

42.for(int g=0;g

43.cout<

44.cout<<" "<

45.cout<<"排序后数据为："<

46.for(int k=0;k

47.cout<

48.}

49.void textinput()

50.{

51.ifstream fin("abc.txt",ios::in);

52.if(fin.fail())

53.cout<<"打开文件失败，没有这个文件！"<

54.char line[100];

55.fin.getline(line,sizeof(line));

56.int y=atoi(line);

57.double *a=new double[y];

58.int *b=new int[y];

59.for(int e=0;e

60.{

61.if(!fin.eof())

62.{

63.fin.getline(line,sizeof(line));

64.a[e]=atof(line);

65.b[e]=e;

66.}

67.}

68.quikesort(a,b,0,y-1);

69.cout<<"排序前数据为："<

70.for(int g=0;g

71.cout<

72.cout<<" "<

73.cout<<"排序后数据为："<

74.for(int k=0;k

75.cout<

76.}

77.

78.int main()

79.{

80.

81.char ch;

82.while(true)

83.{

84.cout<<"Choose Input or FileInput(I:input,F:file):";

85.cin.clear();

86.cin.sync();

87.cin.get(ch);

88.if(ch == 'i')

89.{

90.input();

91.}

92.else if(ch == 'f')

93.{

94.textinput();

95.}

96.else if(ch == 'q')

97.{

98.cout<<"Program is over!"<

99.break;

100.}

101.else

102.{

103.cout<<"the command is error"<

105.}

106.}