之前写过C语言快速排序的算法,今天在《数据结构》(C语言版)清华大学出版社的快排,感觉比之前的更快,于是贴出来。
在我的机子上,排序100w的数据,只要0.3秒!其中我用python写了一个小脚本来生成100w个的随机数。附件为测试数据,本程序在GCC下编译通过。
#include "stdio.h"
#include "time.h"
int shu[1000000];
int i,j,k,len;
void quick_sort(int left,int right);
void read_file();
void write_file();
int partitions(int,int);
int main()
{
clock_t start, finish;
double duration;
read_file();
start = clock();
quick_sort(0,k);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf ("take %.6f second to sort %d datas \n",duration,k);
write_file();
for (i=0;i<100;i++)
printf("%d\n",shu[i]);
return 0;
}
void read_file()
{
FILE * fp;
char *filename = "100w.txt";
fp = fopen(filename,"r");
k=0;
while (fscanf(fp,"%d\n",&shu[k])!=EOF)
k++;
fclose(fp);
}
void write_file()
{
FILE * fp;
char *filename = "sorted_100w.txt";
fp = fopen(filename,"w");
i = 0;
while (i<k)
{
fprintf(fp,"%d\n",shu[i]);
i++;
}
}
int partition(int left,int right)
{
int key = shu[left];
while (left < right)
{
while (left < right && shu[right] >= key)
right--;
shu[left] = shu[right];
while (left < right && shu[left] <= key)
left++;
shu[right] = shu[left];
}
shu[left] = key;
return left;
}
void quick_sort(int left,int right)
{
int mid ;
if (left < right)
{
mid = partition(left,right);
quick_sort(left,mid-1);
quick_sort(mid+1,right);
}
}
分享到:
相关推荐
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
void quicksort(int a[], int p, int r) { if(p){ int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } }
自己写的基于C语言的快速排序。。。 很好用啊 我们一直用他。。
在VS 2008中,用C语言写的快速排序算法。不用多余的数组,直接对原数组进行排序(in place)。同时在递归调用中,对于【数组组就是数组首地址】的理解会更加通透。
C语言实现的Quicksort(快速排序), 最基本的版本, 可以自动生成随机数后进行排序并显示结果, 适合初学者学习.
swap 函数用于交换数组中两个...quickSort 函数是快速排序的核心函数,通过递归地调用分区函数对数组进行排序。 在 main 函数中,首先输出原始数组,然后调用 quickSort 函数对数组进行排序,最后输出排序后的数组。
算法导论版的快速排序的完整实现。C语言版。免积分送给需要的朋友。
然后定义了quickSort函数来实现快速排序算法。在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解...
快速排序(Quicksort)是一种常用的排序算法,它基于分治法,将一个大问题划分为两个子问题进行解决。以下是一个简单的用C语言实现的快速排序的例子: ```c #include // 交换两个元素的值 void swap(int *a, int ...
快速排序c语言 上述代码中,`swap`函数用于交换两个元素的位置。`partition`函数用于将数组划分为较小元素和较大元素两个部分,并确定基准元素的正确位置。`quickSort`函数则是使用递归的方式对划分后的数组进行...
用c++写的一个快速排序程序的实现,程序简洁,可以直接用在C语言上
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
快速排序算法C语言实现,快排序算法QuickSort.cpp
用c语言实现的快排算法 附有简单的实例
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
C语言版快速排序
快速排序快速排序(Quicksort)是对冒泡排序的一种改进。适用很广,高效的排序方法。
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此...