数据结构实验报告——排序

关于排序的几个简单函数

数据结构实验报告

排序

姓名：13-计算机-舞

学号：0000000000

专业：计算机科学与技术

班级：计算机13-2班

日期：2014年6月6日星期五

一、实验目的和要求

通过编程实现直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序。要求输入一些无序数，执行程序后使他们变成有序数并在窗口输出。

二、实验环境

1、windows 7

2、c-free 5.0

三、实验内容

用五种排序算法对输入的数进行排序，并在屏幕中输出。

四、实验过程

1、直接插入排序：即将所需要排序的数据分成两部分，其中一部分为已排好序部分，另一部分为未排序部分。然后从未排序部分中选出一元素插入到一排序部分中，要求插入后已排序部分任然有序。在编写该程序时，我将要排序的数据储存在一个数组中，并将第一个数划分为已经排序部分然

关于排序的几个简单函数

后从下一个数开始不断和前边的最后一个数比较，知道找到插入位置。

2、希尔排序：希尔排序是建立在直接插入排序的基础之上的，他是通过将数据分成几组，在组内实现插入排序，使整个数据基本有序，最后再对整个数据实现插入排序。这里同样将数据储存在数组中，分组的步长每次取之前步长的一半。需要注意的是，移动元素时，下标不再是减1，而是减去步长。

3、冒泡排序：通过不断比较相邻的两个元素，发现倒序即交换，最终实现排序。在这个程序中，我从后面开始向前比较。每依次循环可以最终确定一个元素在其最终位置上，所以每次循环之后，元素间的两两比较次数减1.

4、快速排序：选定一个元素作为中间元素，将整个数据分为比中间元素小的一组和比中间元素大的一组，并且小的在中间元素前，大的在中间元素后。再分好的两组内再次重复上诉过程使所有元素排好序。

5、直接选择排序：将待排序数据存入数组中，扫描一遍数组，将其中最小的元素找出并放在第一位，再扫描一遍剩下的元素，找到最小的放在第二位。如此不断重复知道扫描了n-1次。由于不要再开新空间，所以找到最小元素时用交换的方式使其放在第一位。比如第一遍扫描，假设第一个为最小元素，再扫描过程中，如果发现比它小的数，则把第

关于排序的几个简单函数

一个元素和该位置的元素交换。其他情况类似。

五、测试及结果：

1、直接插入排序：

2、希尔排序：

关于排序的几个简单函数

3、冒泡排序：

4、快速排序：

关于排序的几个简单函数

5、直接选择排序：

关于排序的几个简单函数

六、个人感想：

这次写的这些排序算法的小程序都不是很大，更注重的是对其中思想的理解和认识，以及通过实际编程来达到掌握这些常用算法的目的。

当然，在这次试验中也遇到一点小问题。比如程序执行后的结果显示出来的都是一个数，后来发现是数组下标弄错的原因。还有在实现a[i]<= =>a[j]时也要特别注意次序，顺序出错是得不到最终结果的。这也让我感觉到编程需要严谨的思维和周密的考虑，否则以后编出的程序肯定是有很多bug的。

七、附录（源代码）

1、直接插入排序：

#include <iostream>

using namespace std;

int main()

{

int b[100]; void insert_sort(int a[100],int x); cout<<"输入元素个数："<<endl; int number; cin>>number; for(int i=1;i<=number;i++) cin>>b[i]; insert_sort(b,number);

关于排序的几个简单函数

} return 0;

void insert_sort(int a[100],int x)

{

}

2、希尔排序：

#include <iostream>

using namespace std;

int main() int temp,j; for(int i=2;i<=x;i++){ j=i-1; temp=a[i]; } while(a[j]>temp&&j>0){ } a[j+1]=temp; a[j+1]=a[j]; j--;

关于排序的几个简单函数

}

void shell_sort(int a[100],int x)

{

int buchang,temp,i,j; buchang=x/2; while(buchang>=1){ for(i=buchang+1;i<=x;i++){ temp=a[i]; j=i-buchang; while(a[j]>temp&&j>0){ a[j+buchang]=a[j]; j=j-buchang; int source[100]; void shell_sort(int a[100],int x); cout<<"输入元素个数："<<endl; int number; cin>>number; for(int i=1;i<=number;i++) cin>>source[i]; shell_sort(source,number); for(int i=1;i<=number;i++) cout<<source[i]<<" "; return 0;

关于排序的几个简单函数

}

a[j+buchang]=temp; } } buchang=buchang/2;

3、冒泡排序：

#include <iostream>

using namespace std;

int main()

{

int source[1000]; void bubble_sort(int a[1000],int x); int number; cin>>number; for(int i=1;i<=number;i++) cin>>source[i]; bubble_sort(source,number); for(int i=1;i<=number;i++) cout<<source[i]<<" "; return 0;

关于排序的几个简单函数

void bubble_sort(int a[1000],int x)

{

}

4、快速排序：

#include <iostream>

using namespace std;

int main()

{

int source[1000]; void huafen(int b[1000],int x1,int x2,int &cutpoint); int temp; for(int i=1;i<x;i++){ } for(int j=x;j>1;j--){ } if(a[j]<a[j-1]){ } temp=a[j-1]; a[j-1]=a[j]; a[j]=temp;

关于排序的几个简单函数

} int number; cin>>number; for(int i=1;i<=number;i++) cin>>source[i]; quick_sort(source,1,number); for(int i=1;i<=number;i++) cout<<source[i]<<" "; return 0;

void huafen(int b[1000],int x1,int x2,int &cutpoint)

{

int temp; temp=b[x1]; int i,j; i=x1; j=x2; while(i!=j){ while(i<j&&b[j]>temp) j--; if(i<j) { } b[i]=b[j]; i++;

关于排序的几个简单函数

} } if(i<j){ } b[j]=b[i]; j--; b[i]=temp; cutpoint=i;

void quick_sort(int a[1000],int x1,int x2)

{

}

5、直接选择排序：

#include <iostream>

using namespace std; int i; if(x1<x2){ } huafen(a,x1,x2,i); quick_sort(a,x1,i-1); quick_sort(a,i+1,x2);

关于排序的几个简单函数

int main()

{

}

void buble_sort(int a[1000],int x)

{

int temp; for(int i=1;i<=x-1;i++){//假设第i个位最小 for(int j=i+1;j<=x;j++){//扫描 i个后面所有的数 if(a[j]<a[i]){//如果遇到比第i个小，则和它交换，否int source[1000]; void buble_sort(int a[1000],int x); int number; cin>>number; cout<<"输入"<<number<<"个整数："<<endl; for(int i=1;i<=number;i++) cin>>source[i]; buble_sort(source,number); for(int i=1;i<=number;i++) cout<<source[i]<<" "; return 0; 则继续 ，直到扫完全部的数

temp=a[i]; a[i]=a[j]; a[j]=temp;

关于排序的几个简单函数

} } } }

本文来源：https://www.bwwdw.com/article/1s41.html