快速排序算法c语言实验报告

快速排序算法c语言实验报告

冒泡法和选择法排序C程序实验报告

实验六：冒泡法排序

物理学416班 赵增月 F12 2011412194日期：2013年10月31日

一·实验目的 1.熟练掌握程序编写步骤；

2.学习使用冒泡法和选择法排序；

3.熟练掌握数组的定义和输入输出方法。

二·实验器材

1.电子计算机；

6.0

三·实验内容与流程

1.流程图

（1）冒泡法

(2)选择法 2.输入程序如下： （1）冒泡法 #includestdio.h void

main() { int a[10]; int i,j,t; printf(请输入10个数字：n);

for(i=0;i10;i++)scanf(%d,&a[i]); printf(n);

for(j=0;j9;j++)for(i=0;i9-j;i++) if(a[i]a[i+1]) { t=a[i]; a[i]=a[i+1];

a[i+1]=t; } printf(排序后如下：n); for(i=0;i10;i++) printf(%d,a[i]);

printf(n); }

（2）选择法 #includestdio.h void main() { int a[10]; int i,j,t,k;

printf(请输入10个数字：n); for(i=0;i10;i++)scanf(%d,&a[i]);

printf(n); for(i=0;i9;i++) {k=i;for(j=i+1;j10;j++) if

(a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t; }

printf(排序后如下：n); for(i=0;i10;i++)printf(%d,a[i]);

printf(n); }

四．输出结果 （1冒泡法）

请输入10个数字： 135****2468 排序后如下： （2）选择法 输出结果

请输入10个数字： 135****6810 排序后如下：

五．实验反思与总结

1.冒泡法和选择法是一种数组排序的方法，包含两层循环，写循环时，要注意循环变量的变化范围。

2.要熟练掌握数组的输入输出以及定义方法。

篇二：快速排序法(C语言)

#includestdio.h

#includemalloc.h

#includestdlib.h

#includetime.h

#define randx(x) (rand()%x)

typedef int KeyType;

typedef int DataType;

typedef struct

{

KeyType key;/*排序码字段*/

DataType info; /*记录的其它字段*/

}RecordNode;

typedef struct

{

int n; /*文件中的记录个数,可以视为常量*/

RecordNode *record;

}SortObject;

void creatsort(SortObject * pvector, int &l, int &r)//新建二叉排序树

{

int i; int k;

printf(您即将要创建一个序列n);

printf(n请输入该序列元素的个数n);

scanf(%d, &pvector-n);

pvector-record =

(RecordNode*)malloc((sizeof(RecordNode))*(pvector-n));

printf(n你要以什么方式创建序列？n方式1：自动创建请输入1，方式2：手动创建请输入0n);

scanf(%d, &k);

if (k)

{

srand((int)time(0));

for (i = 0; i pvector-n; i++)

{

if(pvector-n100)

pvector-record[i].key = randx(100);

else if((pvector-n1000))

pvector-record[i].key = randx(1000);

else

pvector-record[i].key = randx(pvector-n);

}

}

else

{

printf(n请输入%d个大小不一样的整数n, pvector-n);

for (i = 0; i pvector-n; i++) {scanf(%d,

&pvector-record[i].key); } } if (pvector) printf(n序列创建成功！n); else

printf(n序列创建失败！n);

l = 0, r = pvector-n-1;

}

void show(SortObject * pvector)

{

printf(n当前序列为：n);

if (!pvector)

printf(当前序列为空);

else

for (int i = 1; i = pvector-n; i++)

{

printf( %d , pvector-record[i-1].key);

if (i % 15 == 0)

printf(n);

}

printf(n);

}

void quickSort(SortObject* &pvector, int l, int r)

{

int i, j;

RecordNode temp, *data = pvector-record;

if (l = r)

return;/* 只有一个记录或无记录，则无须排序*/

j = r;

temp = data[i];

while (i != j)

i = l;

{/* 找Rl的最终位置*/

while (i j && data[j].key = )

j--;/* 向左扫描找排序码小于的记录*/ if (i j)

data[i++] = data[j];

while (i j && data[i].key = )

i++; /* 向右扫描找排序码大于的记录*/if (i j)

data[j--] = data[i];

}

data[i] = temp;/* 将 Rl存入其最终位置*/ quickSort(pvector, l

, i - 1); /* 递归处理左区间*/

quickSort(pvector, i + 1, r); /* 递归处理右区间*/

}

void interface(void)

{

printf(n&&&&&&&&&&&&&&输入序号执行相应操作&&&&&&&&&&&&&&&&&n); printf(输入1，重新建立序列！ n);

printf(---------------------------------------------------n); printf(输入2，快速排序当前序列！n); printf(---------------------------------------------------n);

printf(输入3，显示当前序列！n);

printf(---------------------------------------------------n);

printf(输入其他，退出操作！n);

printf(---------------------------------------------------n);

}

void operation(SortObject* pvector, int l, int r)

{

int k = 1, num;

while (k)

{

interface();//显示界面

scanf(%d, &num);

switch (num)

{

case 1:

free(pvector-record);//重新生成之前释放空间重新生成之前释放空间

creatsort(pvector, l, r);

break;

case 2:

{

quickSort(pvector, l, r);//执行快速排序

free(pvector);//

printf(n已经为你执行快速排序！n);

}

break;

case 3:

{

show(pvector);

}

break;

default:

printf(您未选定任何操作！请重新输入操作序号！n); k = 0;

break;

}

}

}

int main()

{

int l=0,r=0;

} SortObject * pvector = (SortObject

*)malloc(sizeof(SortObject));//分配序列指针 creatsort(pvector, l, r);

operation(pvector, l, r); getchar(); getchar(); return 0;

篇三：C语言快速排序算法

C语言快速排序算法

(一)概述

快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。

快速排序被认为是当前最优秀的内部排序方法。

(二)实现

快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为]。

分解：序列L[m .. n]被划分成两个可能为空的子序列L[m ..

pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1.. n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。

解决：通过递归调用快速排序，对子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。

合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m .. n]已排好序。

(三)性质

内部排序

快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。

比较排序

快速排序确定元素位置的方法基于元素之间关键字大小的比较。

所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。

在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。

不稳定性

快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有=，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。

原地排序

在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。

这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。

(四)时空复杂度

快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。

而在最坏情况下，即数组已经有序或大致有序的情况下，每次

划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。

快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。

但需要注意递归栈上需要花费最少logn最多n的空间。

(五)随机化算法

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2

)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n)。

(六)减少递归栈使用的优化

快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。

一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。

一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。

阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。

另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。

(七)C例程

以下是C语言权威《The C Programming Language》中的例程，在这个例程中，对于数组v的left到right号元素以递增顺序排序。

//Qsort.c by Tydus.

#include stdio.h

intarr[] = {14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};

/* swap函数：交换v[k]与v[j]的值 */

inline void swap(int v[], int k, int j)

{

int temp;

temp = v[k];

v[k] = v[j];

v[j] = temp;

}

voidqsort(int v[], int left, int right)

{

int j, last;

if (left = right) /* 若数组包含的元素个数少于两个 */

return; /* 则不执行任何操作 */

swap(v, left, (left + right)/2); /* 将划分子集的元素移动到V[0] */

last=left; /* 用last记录中比关键字小间的最右位置*/

for (j = left+1; j = right; j++) /* 划分子集 */

{

if (v[j] v[left])

{

swap(v, last++, j);

}

}

/*小小。。。。关键字大大大大*/

qsort(v, left, last-1);

qsort(v, last+1, right);

}

void main()

{

int j;

qsort(arr, 0, 19);

for(j=0; j=19; j++)

{

printf(%d , arr[j]);

}

printf(n);

}

(八)消除递归的快速排序

传统的快速排序是递归的，这就会受到递归栈深度的限制。比如在一台普通的PC上，当待排序元素达到10以上时，传统的递归

快排会导致栈溢出异常，或者一个莫名其妙的错误结果。所以，对于巨大的数据规模，将快速排序消除递归是十分必要的。而消除递归，又将带来巨大的性能提升，把系统级的消耗降到最低。

消除递归的方法，就是模拟栈操作。但是从代码可以看出，这种模拟的消耗几乎可以忽略不计。因此消除递归的快排的效率是有保障的。

（虽然下面的代码没有使用随机化，但经过测试，它是目前所有快排编写方法中，效率最高，速度最快的！）////////////////////////////////////////////////////////////////////////////////

#define MAXARRAY 10000

#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}

#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}

void quicksort(int a[],intl,int r){

staticintsl[MAXARRAY], sr[MAXARRAY], sp;

inti,j,p,t;

sp=0;

PUSH(l,r);

while(sp){

POP(l,r);

i=l;j=r;p=a[(i+j)/2];

while(i=j){

while(a[i]p)i++;

while(a[j]p)j--;

if(i=j){

t=a[i];a[i]=a[j];a[j]=t;

i++;j--;

}

}

if(lj)PUSH(l,j);

if(ir)PUSH(i,r);

}

}

//////////////////////////////////////////////////////////////////////////////////

(十二)C语言随机化快排模块化代码

#include stdio.h

#include stdlib.h

#include time.h

Location(int *a,intlow,int high)

{

intkey,temp,x;

srand((unsigned)time(0));

x=rand()%(high-low+1)+low;

key=a[x];

while(lowhigh)

{

while(xhigh&&key=a[high])high--;

temp=a[high];

a[high]=key;

a[x]=temp;

x=high;

while(lowx&&key=a[low])low++;

temp=a[low];

a[low]=key;

a[x]=temp;

x=low;

}

return low;

}

Qsort(int *a,intlow,int high)

{

intlocat,i;

if(low=high)return 0;

locat=Location(a,low,high);

Qsort(a,low,locat-1);

Qsort(a,locat+1,high);

}

(十三)快速排序的JAVA实现

;

public class QuickSort {

public static void quickSort(int[] array) {

quickSort(array, 0, - 1);

}

private static void quickSort(int[] array, int low, int high) {if (low

high) {

int p = partition(array, low, high);

quickSort(array, low, p - 1);

quickSort(array, p + 1, high);

}

}

private static int partition(int[] array, int low, int high) {int s =

array[high];

int i = low - 1;

for (int j = low; j high; j++) {

if (array[j] s) {

i++;

swap(array, i, j);

}

}

swap(array, ++i, high);

return i;

}

private static void swap(int[] array, int i, int j) {int temp;

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

/**

* @paramargs

*/ public static void main(String[] args) { int[] arr

={12,3,5,4,78,67,1,33,1,1,1};

n(ng(arr)); } }

quickSort(arr);