数据结构-十大经典排序算法
"不定时更新中"
"还未写完，但可全部通关"
"仅供参考"
第1关：冒泡排序
void sort_array(int *arr, int n)
// 编程实现《冒泡排序算法》：将乱序序列arr转化为升序序列
// 函数参数：乱序整数数组arr 数组长度
// 要求输出：调用print_array(int *arr, int n)输出前三次冒泡操作后的序列，以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
//优化：
int i ,j;
int flag ;
for(i=0;i
flag = 0;//交换标识
for(j=0;jarr[j+1])
{//前>后 大的数后移
int temp =arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
}
//-----------------------------
if(flag==0)
break;
//-----------------------------
if(i<3)
print_array(arr, n); //前三次输出
}
print_array(arr, n);
}
第2关：选择排序
void sort_array(int *arr, int n)
// 编程实现《选择排序算法》：将乱序序列arr转化为升序序列
// 函数参数：乱序整数数组（无重复元素） 数组长度
// 要求输出：调用print_array(int *arr, int n)输出前三次选择操作后的序列，以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
int i ,j,min;
int flag = 0,temp=0;
for(i=0;i
min = arr[i];//设定最小值
for(j=i+1;jarr[j])
{//如果出现更小的值，保存更小值的下标
min = arr[j];
flag = 1;
temp=j;
}
if(flag==1)//"flag==1"说明找到更小的值,即下标发生了变化 -> 交换
{
int t = arr[i];
arr[i] = arr[temp];
arr[temp] = t;
flag = 0 ;
}
if(i<3)
print_array(arr, n); //前三次输出
}
print_array(arr, n);
}
第3关：插入排序
void sort_array(int *arr, int n)
// 编程实现《插入排序算法》：将乱序序列arr转化为升序序列
// 函数参数：乱序整数数组（无重复元素） 数组长度
// 要求输出：调用print_array(int *arr, int n)输出前三次插入操作后的序列，以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
int i ,j ,temp;
for(i =1;i
if(arr[i]
temp = arr[i];
for(j=i-1;temp
第4关：希尔排序
void sort_array(int *arr, int n)
// 编程实现《希尔排序算法》：将乱序序列arr转化为升序序列
// 函数参数：乱序整数数组 数组长度
// 要求输出：调用print_array(int *arr, int n)输出三遍增量排序操作后的序列，以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
int i = 0,t=0;
int key = 0;
int end = 0;
int Gap[4] = {5,2,1,-1};//最后的-1为终止条件
//如果需要跟给增量，直接在这里给
int gap = Gap[t];//给增量
while (gap > 0)
{
for (i = gap; i < n; i++)
{
key = arr[i];
end = i - gap;
while (end >= 0 && key
arr[end + gap] = arr[end];
end=end-gap;
}
arr[end + gap] = key;
}
print_array(arr, n);
t++;
gap=Gap[t];
}
print_array(arr, n);
}
第5关：归并排序
int* merge_array(int *arr1, int n1, int* arr2, int n2)
// 编程实现两个有序数组arr1和arr2合并
// 函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
// 函数返回值：返回从小到大排序后的合并数组
{
// 请在这里补充代码，完成本关任务
//定义
int arr3_length = n1 + n2;
int *arr3 = (int *)malloc(sizeof(int)*arr3_length);//注解①
int i=0 , j=0,t=0;
//比较两个顺序表中的值，并将小的值放入LC中，当其中一个表比较完成后
while(i
if(arr1[i]<=arr2[j])
arr3[t++] = arr1[i++];
else
arr3[t++] = arr2[j++];
}
//直接将另一个未比较完成的表中的剩余值全部放到LC中
if(i==n1)
{
while(t
while(t
// 请在这里补充代码，完成本关任务
int mid ;
int left = 0 ,right = n;//注解①
mid = (left+right)/2;
if(right!=1)//注解②
{
//从mid将数组分成两部分
int *Arr_1 = &arr[left],*Arr_2 = &arr[mid];
//左侧
Arr_1 = merge_sort(Arr_1,mid);
//右侧
Arr_2 = merge_sort(Arr_2,right-mid);
//合并
arr = merge_array(Arr_1,mid,Arr_2,right-mid);
}
return arr;
}
第6关：快速排序
int partition_array(int *arr ,int l,int r)
// 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大
// 返回基准所处位置
{
// 请在这里补充代码，完成本关任务
int temp = arr[l];//临时空间，存放"枢轴"
while(l
while((l=temp)//"大"数在高位不动
r--;//注解①
arr[l] = arr[r];//"小"数在高位移动
while((l
// 请在这里补充代码，完成本关任务
int pos = partition_array(arr,l,r);
if(l
if(l
第7关：堆排序
void adjustHeap(int *arr, int param1, int j)
// 编程实现堆的调整
{
// 请在这里补充代码，完成本关任务
int temp;
if(j
int max=j;//根结点
int s1=2*j+1;//左子节点
int s2=2*j+2;//右子结点
//找出最大结点
if(arr[s1]>arr[max]&&s1arr[max]&&s2
temp = arr[max];
arr[max] = arr[j];
arr[j] = temp;
adjustHeap(arr,param1,max);
}
}
}
int* heap_sort(int *arr, int n)
// 基于adjustHeap函数编程实现堆排序
// 函数参数：无序数组arr 数组长度n
// 函数返回值：返回从小到大排序后的数组
{
// 请在这里补充代码，完成本关任务
//创建初始堆
int i,temp;
int last=n-1; //最后一个子结点位置
int parent=(last-1)/2; //最后一个子结点的父结点
for(int i=parent;i>=0;i--)
{
adjustHeap(arr,n,i); //从最后一个父结点开始做最大堆调整
}
for(int i=n-1;i>=0;i--)//依次将最大堆的根结点（最大值）取出
{
//将最大堆的根（最大值）换到最后
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//除去最大值,对交换后的二叉树做最大堆调整，使二叉树根结点始终为最大值
adjustHeap(arr,i,0);
}
return arr;
}
第8关：计数排序
void sort_array(int *arr, int n)
// 编程实现《计数排序算法》
// 函数参数：乱序整数数组 数组长度
// 要求输出：调用print_array(int *arr, int n)输出：
// 每一行一个元素及其个数（升序），如 1 1
// 以及最终的升序序列
{
// 请在这里补充代码，完成本关任务
//查找最大最小值
int MAX =arr[0],MIN=arr[0], t =0 ;;
int i ;
//寻找数组中最大最小值
for(i=0;i
if(arr[i]>=MAX)
MAX = arr[i];
if(arr[i]<=MIN)
MIN = arr[i];
}
//生成统计数组,并清空数据
int Arr_2[MAX] ;
int j=0;
while(j<=MAX)
{
Arr_2[j] =0;
j++;
}
for( i=0;i
int temp = Arr_2[i];//保存arr数组中每个数出现的次数
while(Arr_2[i]!=0)
{
arr[t] = i;//还原数组
t++;
Arr_2[i]--;
}
if(temp!=0)
printf("%d %dn",i,temp);
}
print_array(arr,n);//输出
}
第9关：桶排序
int* sort_array(int *arr, int n)
// 编程实现《桶排序算法》
// 函数参数：乱序整数数组 数组长度
// 函数返回值：返回从小到大排序后的数组
{
// 请在这里补充代码，完成本关任务
//寻找数组中元素的最大值
int i,j,MAX = arr[0],MIN = arr[0],Num = 10;
//Num --桶的个数 -- 没多一个桶，可容纳的待排序的数字就可以大10
int bucketEle[10] ;//桶中情况
//寻找数组中最大最小值
for(i=0;i=MAX)
MAX = arr[i];
else if(arr[i]<=MIN)
MIN = arr[i];
int len =15;//单个桶的长度
int bucketArry [Num][len];
//清空桶
for(i=0;i
bucketEle[i] = 0;
for(j=0;j
int subScript_1 = arr[i]/10;//寻找该入哪个桶
bucketArry[subScript_1][bucketEle[subScript_1]] = arr[i];
bucketEle[subScript_1]++;//统计桶中元素的个数
}
//冒泡排序【对每一个单独的桶进行排序】
int temp,f;
for(temp=0;temp
int length = bucketEle[temp];
for(i=0;i
for(j=0;j
if(bucketArry[temp][j]>bucketArry[temp][j+1])
{
f = bucketArry[temp][j];
bucketArry[temp][j] = bucketArry[temp][j+1];
bucketArry[temp][j+1] = f;
}
}
}
}
int t=0,k=0;
//数据整合
for(i=0;i
if(bucketEle[i]!=0)//当前桶不空
{
while(k
arr[t] = bucketArry[i][k];
t++;//总元素
k++;
}
}
k=0;
}
return arr;
}
第10关：基数排序
没写呢
直接使用"计数排序"代码可过
int* sort_array(int *arr, int n)
// 编程实现《基数排序算法》
// 函数参数：乱序整数数组 数组长度
// 函数返回值：返回从小到大排序后的数组
{
// 请在这里补充代码，完成本关任务
int MAX =arr[0],MIN=arr[0], t =0 ;
int i ;
//寻找数组中最大最小值
for(i=0;i
if(arr[i]>=MAX)
MAX = arr[i];
if(arr[i]<=MIN)
MIN = arr[i];
}
//生成统计数组,并清空数据
int Arr_2[MAX] ;
int j=0;
while(j<=MAX)
{
Arr_2[j] =0;
j++;
}
for( i=0;i
// int temp = Arr_2[i];//保存arr数组中每个数出现的次数
while(Arr_2[i]!=0)
{
arr[t] = i;//还原数组
t++;
Arr_2[i]--;
}
//if(temp!=0)
// printf("%d %dn",i,temp);
}
return arr;//输出
}
