P1.1 选择问题，选择出第K大的数，并画出N为不同值的运行时间，K=N/2
毕业两年半，重写排序，感觉良好。代码使用冒泡排序，库函数clock计算大致运行时间。
1 // P1_1.cpp : Defines the entry point for the console application. 2 // 3 4 #include "stdafx.h" 5 #include <malloc.h> 6 #include <stdlib.h> 7 #include <time.h> 8 9 void swap(int& a,int& b); 10 11 int main(int argc, char* argv[]) 12 { 13 14 int N = 40000; 15 int k = N/2; 16 int i,j; 17 18 //动态数组 19 int *dynArr = (int *)malloc(N * sizeof(int)); 20 //生成随机数组 21 srand((unsigned) time(NULL)); 22 //printf("%d%c", rand(),' '); 23 for(i=0; i<N;i++) 24 { 25 dynArr[i] = rand()%100; 26 //printf("%d%c",dynArr[i],' '); 27 } 28 29 30 int beginTime = clock();//计时开始 31 32 //冒泡排序 33 int temp = 0; 34 for(i=0;i<N;i++) 35 for(j=0;j<N;j++) 36 { 37 if(dynArr[i]>dynArr[j]){ //左>右，交换 38 swap(dynArr[i],dynArr[j]); 39 } 40 }//第一层结束，最大数在最右 41 42 int endTime = clock();//计时结束 43 int runningTime = endTime - beginTime;//算出来的单位是毫秒 44 45 46 47 for(i=0; i<N;i++){ 48 // dynArr[i] = rand()%100; 49 //printf("%d%c",dynArr[i],' '); 50 } 51 52 char str1[] = "个数中第k大的数："; 53 char str2[] = "运行时间（毫秒）："; 54 printf(" %d%s%d ",N,str1,dynArr[k]); 55 printf(" %s%d ",str2,runningTime); 56 57 58 return 0; 59 } 60 61 void swap(int& left,int& right){ 62 int temp; 63 temp = left; 64 left = right; 65 right = temp; 66 }
更改N值，来测试不同样本值的运行时间。
假如数据是学生的一个科目的考试成绩，百分制。N表示学生的个数。
N Time(ms)
0 0
50 1
100 5
500 49
1000 101
5000 272
N(万) Time(ms)
1 281
2 1109
3 2506
4 4384
5 6764
6 9747
7 13296
8 17421
9 22078
10 27307
用这个网站绘制曲线图：
感觉就是个递增。其实这是假象...再看这两个小图：
人数是普通的递增，但是时间可不是递增，时间花费是迅速上升的。