/*
创新互联建站是一家专注于网站建设、做网站与策划设计,东宁网站建设哪家好?创新互联建站做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:东宁等地区。东宁做网站价格咨询:18982081108
//@author Program_Yuan
//时间：2014年6月19日21:19:23
*/
/*
数据结构实验作业
实验4：排序1
要求：
1、直接插入排序；
2、折半插入排序；
3、希尔排序;
4、冒泡排序
5、简单选择排序
6、树型选择排序
7、堆排序
交作业时间：7月2日
*/
//各种排序
//以下排序均已升序为标准
//测试数据 a[] = {32,21,10,100,43,54,12,78,10,3223,34,31,54,76,2,6,2,4};
#include iostream
#include cstring
using namespace std;
void bubble_sort(int a[],int n);
void quick_sort(int a[],int n);
void simple_select_sort(int a[],int n);
void direct_insert_sort(int a[],int n);
void middle_insert_sort(int a[],int n);
void shell_sort(int a[],int n);
void heap_sort(int a[],int n);
void change_heap(int a[],int i,int n);
inline void swap(int a,int b);
int main()
{
int a[] = {32,21,10,100,43,54,12,78,10,3223,34,31,54,76,2,6,2,4};
int n = sizeof(a) / sizeof(int);
//bubble_sort(a,n);//冒泡测试
//quick_sort(a,n);//快排测试
//simple_select_sort(a,n);//简单选择排序
//direct_insert_sort(a,n);//直接插入排序
//middle_insert_sort(a,n);//折半插入排序
//shell_sort(a,n);//希尔排序
heap_sort(a,n);//堆排序
for (int i = 0; i n; i++)
{
couta[i]" ";
}
coutendl;
return 0;
}
void bubble_sort(int a[],int n)//冒泡排序
{
for (int i = 0; i n; i++)
{
for (int j = i + 1; j n; j++)
{
if (a[i] a[j])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}//冒泡排序
void quick_sort(int a[],int n)//快排
{
int key = a[0];//key为支点，即枢轴
int low,high;
low = 0;
high = n - 1;//low,high分别为两端点值
if (n 1)
{
while (low high)
{
for (; high low; high--)
{
if (a[high] key)
{
a[low] = a[high];
break;
}
}
for (; low high; low++)
{
if (a[low] key)
{
a[high] = a[low];
break;
}
}
}
}
else
{
return;
}
a[low] = key;
quick_sort(a,low);
quick_sort(a + low + 1, n - low - 1);
}//快速排序
void simple_select_sort(int a[],int n)//简单选择排序
{
int min = 0;
for (int i = 0; i n; i++)
{
for (int j = i; j n; j++)
{
if (a[min] a[j])
{
min = j;
}
}
int t = a[i];
a[i] = a[min];
a[min] = t;
min = i + 1;
}
}//简单选择排序
void direct_insert_sort(int a[],int n)//插入排序----直接插入排序
{
int j;//控制循环
for (int i = 1; i n; i++)
{
if (a[i] a[i - 1])
{
int key = a[i];
for (j = i - 1; key a[j] j = 0; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = key;
}
}
}//插入排序----直接插入排序
void middle_insert_sort(int a[],int n)//折半插入排序
{
int t = 0;
for (int g = 1; g n; g++)
{
if (a[t] a[g])
{
t = g;
}
}
int k = a[t];
a[t] = a[0];
a[0] = k;
for(int i = 2; i n; i++)
{
int low = 1;
int hight = i - 1;
int key = a[i];
int j;//控制循环
while (low = hight)
{
int mid = (low + hight) / 2;
if (a[mid] key)
{
hight = mid - 1;
}
else if (a[mid] key)
{
low = mid + 1;
}
else
{
break;
}//if
}//for
for (j = i - 1; j = hight + 1; j--)
{
a[j + 1] = a[j];
}//for
a[j + 1] = key;
}//while
}//函数
void shell_sort(int a[],int n)//希尔排序
{
int interval = n / 2; //interval是间隔 即增量
int g;
while (interval 0)
{
for (int j = interval; j n; j++)
{
int key = a[j];
for (g = j - interval; g = 0 key a[g]; g -= interval)
{
a[g + interval] = a[g];
}//移动到插入的地方
a[g + interval] = key;
}//n趟排序
interval /= 2;
}//while
}//希尔排序
void swap(int a,int b)//堆排序的辅助函数----交换两个数（为了提高效率，使用内联函数）
{
int t = a;
a = b;
b = t;
}
void change_heap(int a[],int i,int n)//调整堆
{
int n_child;
for ( ; 2 * i + 1 n; i = n_child)
{
n_child = 2 * i + 1;
if (n_child n - 1 a[n_child + 1] a[n_child])
n_child++;
if (a[n_child] a[i])
{
swap(a[n_child],a[i]);
}
else
{
break;
}
}
}//堆排序----调整堆
void heap_sort(int a[],int n)//建立堆
{
//调整从第一个非叶子结点开始
for (int i = n / 2 - 1; i = 0; i--)
{
change_heap(a,i,n);
}
for(int j = n - 1; j 0; j--)
{
swap(a[j],a[0]);
change_heap(a,0,j);
}
}//堆排序----输出最大
/*
//帮助文档 -_-||
//作业第四个
//一个最简单的冒泡排序 注释：冒泡排序是稳定的排序算法，复杂度为 n*n
void bubble_sort(int a[],int n);
//快速排序 注释：快排是对冒泡排序的改进，不是稳定排序，复杂度为log(n)
//效率很高 编码复杂 思想：首先找一个支点（枢轴，通常选取第一个元素），
//第一遍把大于支点的元素放在右边，小于支点的元素放在左边
//第二遍也是这样的思想 把左右同时看做是一个有待排序的数列 利用递归的思想
void quick_sort(int a[],int n);
//作业第五个
//选择排序----简单选择排序 注释：复杂度 n*n 不是稳定排序
void simple_select_sort(int a[],int n);
//作业第一个
//插入排序----直接插入排序 注释： 复杂度 n*n 稳定的排序算法
void direct_insert_sort(int a[],int n);
//作业第二个
//折半插入排序 注释： 复杂度 n*n
void middle_insert_sort(int a[],int n);
//作业第三个
//希尔排序 注释： 不稳定
void shell_sort(int a[],int n);
//作业第七个
//堆排序 注释： 不稳定
void heap_sort(int a[],int n);//建立堆
void change_heap(int a[],int i,int n);//调整堆
inline void swap(int a,int b);//堆排序的辅助函数 用来交换两个数据的值
//我是大好人
*/
#includestdio.h
void sort(float *a, int n)
{
int i,j,tmp;
for(i=0; in-1; i++)
for(j=0; jn-i-1; j++)
if(a[j]a[j+1])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
void main()
{
float a[5];
int i;
printf("请输入五个数(逗号隔开)：");
scanf("%f,%f,%f,%f,%f",a[0],a[1],a[2],a[3],a[4]);
sort(a,5);
printf("排序后为：");
for(i=0; i5; i++)
printf("%.2f ",a[i]);
printf("\n");
}
或者三个数的。
void sort(int *a, int *b, int *c)
{
int tmp;
if(*a*b){
tmp = *b;
*b = *a;
*a = tmp;
}
if(*a*c){
tmp = *c;
*c = *a;
*a = tmp;
}
if(*b*c){
tmp = *c;
*c = *b;
*b = tmp;
}
return;
}
扩展资料：
C语言中没有预置的sort函数。如果在C语言中，遇到有调用sort函数，就是自定义的一个函数，功能一般用于排序。
一、可以编写自己的sort函数。
如下函数为将整型数组从小到大排序。void sort(int *a, int l)//a为数组地址，l为数组长度。
{
int i, j;
int v; //排序主体
for(i = 0; i l - 1; i ++)
for(j = i+1; j l; j ++)
{
if(a[i] a[j])//如前面的比后面的大，则交换。
{
v = a[i];
a[i] = a[j];
a[j] = v;
}
}
}
对于这样的自定义sort函数，可以按照定义的规范来调用。
二、C语言有自有的qsort函数。
功 能： 使用快速排序例程进行排序。头文件：stdlib.h
原型：
void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
参数：
1、待排序数组首地址。
2、数组中待排序元素数量。
3、各元素的占用空间大小4 指向函数的指针，用于确定排序的顺序，这个函数必须要自己写比较函数，即使要排序的元素是int，float一类的C语言基础类型。
include cstdlib 或 #include stdlib.h
qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))
参数表
*base: 待排序的元素（数组，下标0起）。
num: 元素的数量。
width: 每个元素的内存空间大小（以字节为单位）。可用sizeof()测得。
int(*)compare: 指向一个比较函数。*elem1 *elem2: 指向待比较的数据。
比较函数的返回值
返回值是int类型，确定elem1与elem2的相对位置。
elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。
控制返回值可以确定升序/降序。
产生随机数的函数也是rand(),不是rank().
1、冒泡排序（最常用）
冒泡排序是最简单的排序方法：原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。（注意每一轮都是从a[0]开始比较的）
以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。
2、鸡尾酒排序
鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
3、选择排序
思路是设有10个元素a[1]-a[10]，将a[1]与a[2]-a[10]比较，若a[1]比a[2]-a[10]都小，则不进行交换。若a[2]-a[10]中有一个以上比a[1]小，则将其中最大的一个与a[1]交换，此时a[1]就存放了10个数中最小的一个。同理，第二轮拿a[2]与a[3]-a[10]比较，a[2]存放a[2]-a[10]中最小的数，以此类推。
4、插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素*
一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
首先这是一种快速排序的算法，你也应该知道，快速排序就是选择序列中的一个元素作为基准，通过循环找到这个基准最终的位置，并把所有小于这个基准的元素移到这个位置的左边，大于基本的元素移到右边，这样再对这个基准的左右两边分别递归调用自己，最终就能得到排序的结果。
再来解释一下这个例子，它选择的基准就是v[(left+right)/2]，然后将这个基准雨v[left]交换，现在假设你想从头排序到最后，则你会将left传个0，也就是他将这个基准和V[0]交换了，这个时候开始循环，因为第一个元素是基准，所以从第二个元素开始循环（也就是left+1），然后到if判断部分，如果v[i]v[left],也就是说这个时候已经至少有一个元素比基准小了，所以基准至少在v[1]或者之后了，所以他把你找到的这个比基准小的v[i]和v[++last]交换，这时候v[i]的位置已经是在基准的正确位置或者之前了，不会在基准之后的，所以这就实现了把比基准小的元素移到基准的正确位置之前，你说的【第一遍执行过程中，第8行last=left=0，那么到了11行时相当于交换v[1]和v[0+1]】这没有错，确实是在自己交换自己，但是这样并不违背前面的思路不是么？当if条件不满足的时候，last是不会增加的，但是i会一直加1，所以last和i就会不同，这只是在将比基准小的元素移到基准之前，每有一个比基准小的，last就加1，这样当你循环一遍之后的last值就是基准应该在的位置，而且这个时候，所有比基本小的元素也都在last之前了，这时候last位置的元素也是比基准小的，这没关系，因为之后还有一句swap[v,last,left]，到目前位置，基准的位置找到了，基准左边的元素都比基准小，右边都比基准大，再对基准的左右两边递归调用自己，就完成了序列的排序。
1、sort（）函数描述：对给定区间所有元素进行排序。
sort（）函数语法：sort(begin,end)，表示一个范围。
2、sort（）函数举例：
#include algorithm
#include iostream
using namespace std;
main()
{
int a[11]={2,4,8,5,7,1,10,6,9,3};//a的长度=待排数据个数+1
sort(a,a+10);//对[a,a+10)排序
for(int i=0;i10;++i) couta[i]endl;
}
