/*
功能：用以下几种方法实现c语言中的常用排序
*/
#include "stdio.h"
void select_Sort1(int a[],int n);
void select_Sort2(int a[],int n);
void bubble_Sort(int a[],int n);
void insert_Sort(int a[],int n);
void quick_Sort(int a[],int low,int high);
int findpos(int a[],int low,int high);
int main()
{
int a[10];
int i;
printf("please enter ten int number:\n");
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
//select_Sort2(a,10);
//bubble_Sort(a,10);
//insert_Sort(a,10);
quick_Sort(a,0,9);
printf("after sorted:\n");
for(i=0;i<10;i++)
{
printf("%5d",a[i]);
}
return 0;
}
//第一种方法：选择排序法
//用一种较为容易理解的方法实现选择排序
void select_Sort1(int a[],int n)
{
int i,j,k;
//外部循环从小到大，依次找出各位置上的值（最后一个位置上的值除外，因为在循环的过程中各个位置上的值逐渐确定下来，最后一个值自然就确定了）
for(i=0;i<n-1;i++)
{
//内部循环从外部循环指针的下一个位置开始，将后续位置上取到的值逐渐与外部循环所对应的指针上的值进行比较
for(j=i+1;j<n;j++)
{
if(a[j]<a[i])
{
// 找到比该位置上的值小的值就进行一次交换
k=a[i];
a[i]=a[j];
a[j]=k;
}
}
}
}
//以下方法实现起来效率更高，之所以效率高是因为找到一个比外循环指针所对应值更小的值时没有马上交换而是把位置先记录下来，内循环结束后再交换
void select_Sort2(int a[],int n)
{
int i,j,k,t;
//外部循环从小到大，依次找出各位置上的值（最后一个位置上的值除外，因为在循环的过程中各个位置上的值逐渐确定下来，最后一个值自然就确定了）
for(i=0;i<n-1;i++)
{
//内部循环从外部循环指针的下一个位置开始，将后续位置上取到的值逐渐与外部循环所对应的指针上的值进行比较
k=i;//k的作用是记录内部指针一趟比较下来，哪个位置所对应的值比外指针所对应的值小，将该位置存放到k中，默认情况下k的值是外指针对应位置
for(j=i+1;j<n;j++)
{
if(a[j]<a[k])
k=j;//k=j 记录下最小值的位置
}
//进行交换，t是临时变量
t=a[i];
a[i]=a[k];
a[k]=t;
}
}
//第二种方法：冒泡排序法
void bubble_Sort(int a[],int n)
{
int i,j,t;
//外层循环控制圈数，对n个数排序，需要n-1圈
//外层循环指针对应将要放数的位置，每次结束外层循环都将排好了一个数
for(i=n-1;i>0;i--)
{
//内层循环对相邻的俩个数进行比较，大者冒泡到后边，j<i使得内层循环不必再对已经排好的数进行访问
for(j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
//第三种方法：插入法排序
void insert_Sort(int a[],int n)
{
int i,j,t;
//外层循环的作用是从0位置开始逐渐从数组中将n个数拿出来，与已经排好的数进行比较，插入到适当的位置
for(i=0;i<n;i++)
{
//对已有的数（这些数已经排好）逐一与外层循环拿出的数进行比较
//之所以j=i-1是因为i代表进行插入排序的数的位置，j就表示了排好序以后该有序数列最后一个数的位置
for(j=i-1;j>=0;j--)
{
if(a[j+1]<a[j])
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
}
//第四种方法：快速排序
//快速排序的原理是选择一个数作为分界点，将小于他的数放到他的左边，大于他的数放到他的右边，然后分别对左右俩边的数进行同样方法的处理，得出结果
void quick_Sort(int a[],int low,int high)
{
int pos;
if(low<high)
{
//确定一个位置pos，pos左边的数都比pos位置上的数小，pos右边的数都比pos位置上的数大
pos=findpos(a,low,high);
quick_Sort(a,low,pos-1);
quick_Sort(a,pos+1,high);
}
}
//该方法的作用是返回一个位置值，使得该位置左边的数都比该位置上的数小，该位置右边的数都比该位置上的数大
int findpos(int a[],int low,int high)
{
//假定数组中的数为49,38,65,13,50之后便于进行说明
//从数组中选择一个数作为分界点，该数为49
int val=a[low];
while(low<high)
{
//指针从high开始，将其值（即50）与val进行比较，若大于val，就移动high指针向前，再次比较，若小于val的值就将该值覆盖low指针位置处的值
while(low<high && a[high]>val)
high--;
a[low]=a[high];
//程序执行到这里后数列的排列顺序为13,38,65,13,50，此时low和high指针的位置并没有互换
//指针从low开始，将其值（即13）与val进行比较，若小于val，就移动low指针向后，再次比较，若大于val的值就将该值覆盖high指针位置处的值
while(low<high && a[low]<val)
low++;
a[high]=a[low];
//程序执行到这里后数列的排列顺序为13,38,65,65,50，此时满足low小于high，进行下一次的循环
}
a[low]=val;//移动完毕low和high必定相等，此时的数列排列顺序为13,38,49,65,50，low=high=3 于是使得49左边的数都比49小，49右边的数都比49大
return low;
}
//功能：归并排序，将俩个有序顺序表合并为一个有序顺序表。
#include <stdio.h>
void mergesort(int a[],int n1,int b[],int n2);
int main()
{
int a[5]={0,2,4,6,8},b[5]={1,3,5,7,9};
//合并俩表为一个有序表
printf("mergesort\n");
mergesort(a,5,b,5);
return 0;
}
//合并俩个表为一个有序表 ，归并排序
void mergesort(int a[],int n1,int b[],int n2)
{
int i,j,k;
int c[10];
i=j=k=0;
//按照俩表数据元素从小到大的顺序放到第三个数组中
while(i<n1 && j<n2)
{
if(a[i]<b[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
j++;
k++;
}
}
/*上一次循环执行完毕，一个表中的数据元素已经全部放到了第三个数组中，但还有一个表中
存在没有放到第三个数组中的元素，以下俩个循环只会执行其中的一个*/
while(i<n1)
{
c[k]=a[i];
i++;
k++;
}
while(j<n2)
{
c[k]=b[j];
j++;
k++;
}
for(k=0;k<n1+n2;k++)
{
printf("%d\t",c[k]);
}
}
