算法分析实验3蛮力法排序 下载本文

实验三 蛮力法排序(四号黑体)

【一】实验目的(小四黑体)

1.采用蛮力法实现序列排序; 2.分析各种方法的优缺点。

【二】实验内容(小四黑体)

1.采用蛮力排序算法对序列排序; 2.编程实现选择排序与冒泡排序; 3.分析比较2种算法的时间复杂度;

4.试着改进冒泡排序,使算法在序列达到有序状态时停止运行。

【三】实验步骤(代码、结果)(小四黑体)

#include #include #include

void SelectionSort(int a[],int n) {

int i,j,t,temp;

for(i=0; i<=n-2; i++) {

t=i;

for(j=i+1; j<=n-1; j++) {

if(a[j]

t=j; } }

temp=a[i]; a[i]=a[t]; a[t]=temp; } }

void BubbleSort(int a[],int n) {

int i,j,temp;

for(i=0; i<=n-2; i++) {

for(j=0; j<=n-2-i; j++)

{

if(a[j+1]

temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }

void BubbleSort1(int a[],int n) {

int falg=1; int i,temp; while(falg) {

falg=0;

for(i=0;i

if(a[i+1]

temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; falg=1; } } n--; } }

void print(int a[],int n) {

int i;

for(i=0; i

printf(\ } }

int main() {

printf(\学号:Z09315221 姓名:谭召\\n\ int a[10]= {10,20,15,17,13,9,5,4,2,7}; //int a[10]= {1,2,3,4,5,6,7,8,9,1}; SelectionSort(a,10);

BubbleSort(a,10); BubbleSort1(a,10); print(a,10); return 0; }

【四】实验结果分析(小四黑体)

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。冒泡排序方法是最简单的排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。选择排序和冒泡排序的时间复杂度都是O(n^2),但是选择排序不稳定,而冒泡排序稳定。