|
日历
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | | 28 | 29 | 30 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|
统计
- 随笔 - 1
- 文章 - 2
- 评论 - 0
- 引用 - 0
导航
常用链接
留言簿
随笔档案
文章档案
搜索
最新评论
|
1
2#include <stdafx.h>
3#define N 100000 //随机生成排序数的个数
4//插入排序法
5void InsertSort(int* pData,int Count)
6   {
7 int iTemp;
8 int iPos;
9 for(int i=1;i<Count;i++)
10  {
11 iTemp = pData[i];
12 iPos = i-1;
13 while((iPos>=0) && (iTemp<pData[iPos]))
14 {
15 pData[iPos+1] = pData[iPos];
16 iPos--;
17 }
18 pData[iPos+1] = iTemp;
19 }
20 }
21//快速排序法
22void run(int *pData,int left,int right)
23{
24 int middle,i,j;
25 int iTemp;
26 i=left;
27 j=right;
28 middle=pData[(left+right)/2]; //get the middle element
29 do{
30 while((pData[i]<middle)&&(i<right))
31 i++;
32 while((pData[j]>middle)&&(j>left))
33 j--;
34 if(i<=j)
35 { //exchange the elements
36 iTemp=pData[i];
37 pData[i]=pData[j];
38 pData[j]=iTemp;
39 i++;
40 j--;
41 }
42 }while(i<=j);
43 if(left<j)
44 run(pData,left,j);
45 if(right>i)
46 run(pData,i,right);}
47
48void QuickSort(int *pData,int Count)
49{
50 run(pData,0,Count-1);
51}
52void Sort(int *pData, int p, int q, int r)
53{
54 int i,k;
55 int begin1,end1,begin2,end2;
56 int* temp = (int*)malloc((r-p+1)*sizeof(int));
57 begin1= p;
58 end1 = q;
59 begin2 = q+1;
60 end2 = r;
61 k = 0;
62 while((begin1 <= end1)&&( begin2 <= end2))
63 {
64 if(pData[begin1] < pData[begin2])
65 { temp[k] = pData[begin1];
66 begin1++;
67 }
68 else
69 {
70 temp[k] = pData[begin2];
71 begin2++;
72 }
73 k++;
74 }
75 while(begin1<=end1)
76 {
77 temp[k++] = pData[begin1++];
78 }
79 while(begin2<=end2)
80 {
81 temp[k++] = pData[begin2++];
82 }
83 for (i = 0; i < (r - p + 1); i++)
84 pData[p+i] = temp[i];
85 free(temp);
86}
87void MergeSort(int *pData,int left,int right)
88{
89 int mid=0;
90 if(left<right)
91 {
92 mid = (left+right)/2;
93 MergeSort(pData, left, mid);
94 MergeSort(pData, mid+1,right);
95 Sort(pData,left,mid,right);
96 }
97}
98void Merge(int *pData,int Count)
99{
100 MergeSort(pData,0,Count-1);
101}
102int main(void)
103{
104 clock_t start;
105 int arry[N];
106 int i = 0;
107 srand(int(time(NULL)));
108 printf("随机数生成中……\n");
109 for(i = 0; i < N; i++)
110 arry[i] = rand();
111 printf("插入排序中……\n");
112 start = clock();
113 InsertSort(arry, N);
114 printf("插入排序排序 %d 个数的时间：%d\n", N, clock()-start);
115 for(i = 0; i < N; i++)
116 arry[i] = rand();
117 printf("快速排序中……\n");
118 start = clock();
119 QuickSort(arry, N);
120 printf("快速排序排序 %d 个数的时间：%d\n", N, clock()-start);
121 for(i=0;i<N;i++)
122 arry[i]=rand();
123 printf("归并排序中……\n");
124 start=clock();
125 Merge(arry,N);
126 printf("归并排序排序%d个数的时间：%d\n",N,clock()-start);
127 getchar();
128 return 0;
129
130}
最近老师布置的实验，在网上找了一些代码，自几有改了一些，运行结果正常 ，还要接着搞贪心算法，晕哦
|