算法分析实验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)，但是选择排序不稳定，而冒泡排序稳定。