快速排序(QuickSort)C语言版
快速排序的核心在于分治.
分治算法:
1. 认定只有一个元素或没有元素的数组是有序的.
2. 将数组按照一个分界值分为左右两部分. 左面所有元素值比分界值小, 右面所有元素值比分界值大或等于.
3. 将左右两部分分别再分治, 直到要分支的部分只有一个元素或没有元素, 那么整个数组就是有序的了.
作者: selfimpr
博客: http://blog.csdn.net/lgg201
邮箱: lgg860911@yahoo.com.cn
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define LENGTH 500000
/*
* 打印一个指定的数组
*/
void printArray(int array[], int length);
/*
* 将指定数组的指定部分分治, 返回分治点.
* @argument division: 分界点(下标)
* @argument left: 分治部分的左下标
* @argument right: 分治部分的右下标
*/
int part(int array[], int division, int left, int right);
/*
* 排序指定数组的指定位置元素.
*/
void sort(int array[], int left, int right);
/*
* @author: selfimpr
* @blog: http://blog.csdn.net/lgg201
* @email: lgg860911@yahoo.com.cn
*/
int main() {
int array[LENGTH];
int i;
srand( (unsigned) time(NULL) );
for(i = 0; i < LENGTH; i ++) {
array[i] = rand() % LENGTH;
}
/*
* printArray(array, LENGTH);
* printf("\n\n");
*/
clock_t start = clock();
printf("Start at %d.\n", (unsigned)start);
sort(array, 0, LENGTH - 1);
clock_t end = clock();
printf("End at %d.\n", (unsigned)end);
/*
* printArray(array, LENGTH);
*/
printf("Sorted %d numbers in %d millisecond.", LENGTH, (unsigned)end - (unsigned)start);
return 0;
}
void printArray(int array[], int length) {
int i;
for(i = 0; i < length; i ++) {
printf("%d ", array[i]);
if((i + 1) % 10 == 0) {
printf("\n");
}
}
}
/*
* 分治算法:
* 以division下标的元素值为分界点, 将数组分成左右两个部分.
* 返回分界点的下标.
* 过程:
* 1. 保留分界点元素的值.
* 2. 移动左指针, 直到一个值不小于分界值.
* 3. 判断是否已经划分了所有元素, 如果是, 跳出.
* 4. 将左指针目前的值复制到division位置, �
相关文档：
自由的歌谣
本书是自由软件丛书的一部分，也是一首自由的歌谣。
本书中阐述的GNU C库，定义了所有在ISO C标准所规定的，以及POSIX标准、其它相关标准和UNIX系统所派生的标准中定义的所有函数，为GNU操作系统所支持。
C程序设计语言提供诸如输入/输出� ......
在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在Ｃ语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结� ......
指针是Ｃ语言中广泛使用的一种数据类型。运用指针编程是Ｃ语言最主要的风格之一。利用指针变量可以表示各种数据结构；能很方便地使用数组和字符串；并能象汇编语言一样处理内存地址，从而编出精练而高效的程序。指针极大地丰富了Ｃ语言的功能。学习指针是学习Ｃ语言中最重要的一环，能否正确理解和使用指针是我们是否掌握 ......
【例10.21】用选择法对10个整数排序。
main()
{int *p,i,a[10]={3,7,9,11,0,6,7,5,4,2};
printf("The original array:\n");
for(i=0;i<10;i++)
printf("%d,",a[i]);
printf("\n");
p=a;
sort(p,10);
for(p=a,i=0;i<10;i++)
{printf("%d ",*p);p++;}
printf("\n");
}
sort(int x[],int n)
......
11.1 定义一个结构的一般形式
在实际问题中，一组数据往往具有不同的数据类型。例如，在学生登记表中，姓名应为字符型；学号可为整型或字符型；年龄应为整型；性别应为字符型；成绩可为整型或实型。 显然不能用一个数组来存放这一组数据。因为数组中各元素的类型和长度都必须一致，以便于编译系统处理� ......
