可通過(guò) 目錄 快速查閱對(duì)應(yīng)排序算法文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-762373.html
第1關(guān)?冒泡排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《冒泡排序算法》：將亂序序列arr轉(zhuǎn)化為升序序列
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組arr 數(shù)組長(zhǎng)度
// 要求輸出：調(diào)用print_array(int *arr, int n)輸出前三次冒泡操作后的序列，以及最終的升序序列
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(i<3)
print_array(arr,n);
}
print_array(arr,n);
/********** End **********/
}第2關(guān)?選擇排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《選擇排序算法》：將亂序序列arr轉(zhuǎn)化為升序序列
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組（無(wú)重復(fù)元素） 數(shù)組長(zhǎng)度
// 要求輸出：調(diào)用print_array(int *arr, int n)輸出前三次選擇操作后的序列，以及最終的升序序列
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int index,min;
for(int i=0;i<n-1;i++)
{
min=arr[i];
index=i;
for(int j=i+1;j<n;j++)
{
if(min>arr[j])
{
min=arr[j];
index=j;
}
}
arr[index]=arr[i];
arr[i]=min;
if(i<3)
print_array(arr,n);
}
print_array(arr,n);
/********** End **********/
}
第3關(guān)?插入排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《插入排序算法》：將亂序序列arr轉(zhuǎn)化為升序序列
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組（無(wú)重復(fù)元素） 數(shù)組長(zhǎng)度
// 要求輸出：調(diào)用print_array(int *arr, int n)輸出前三次插入操作后的序列，以及最終的升序序列
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int temp,index;
for(int i=1;i<n;i++)
{
temp=arr[i];
index=i;
for(int j=i-1;j>=0;j--)
{
if(arr[j]>temp)
{
arr[index--]=arr[j];
arr[j]=temp;
}
}
if(i<4)
print_array(arr,n);
}
print_array(arr,n);
/********** End **********/
}
第4關(guān)?希爾排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《希爾排序算法》：將亂序序列arr轉(zhuǎn)化為升序序列
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組 數(shù)組長(zhǎng)度
// 要求輸出：調(diào)用print_array(int *arr, int n)輸出三遍增量排序操作后的序列，以及最終的升序序列
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int sort_array[]={5,2,1};
int temp,index,sep;
for(int k=0;k<3;k++)
{
sep=sort_array[k];
for(int i=sep;i<n;i++)
{
temp=arr[i];
index=i;
for(int j=i-sep;j>=0;j-=sep)
{
if(arr[j]>temp)
{
arr[index]=arr[j];
index-=sep;
arr[j]=temp;
}
}
}
print_array(arr,n);
}
print_array(arr,n);
/********** End **********/
}
第5關(guān)?歸并排序
#include "sort_.h"
int cmp(const void*a,const void*b)
{
return (*(int*)a-*(int*)b);
}
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
int* merge_array(int *arr1, int n1, int* arr2, int n2)
// 編程實(shí)現(xiàn)兩個(gè)有序數(shù)組arr1和arr2合并
// 函數(shù)參數(shù)：有序數(shù)組arr1 數(shù)組arr1長(zhǎng)度 有序數(shù)組arr2 數(shù)組arr2長(zhǎng)度
// 函數(shù)返回值：返回從小到大排序后的合并數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int *arr3;
arr3=(int*)malloc(sizeof(int)*(n1+n2));
int a1=0,a2=0,a3=0;
while(a1<n1&&a2<n2)
{
if(arr1[a1]<=arr2[a2])
arr3[a3++]=arr1[a1++];
else
arr3[a3++]=arr2[a2++];
}
while(a1<n1)
arr3[a3++]=arr1[a1++];
while(a2<n2)
arr3[a3++]=arr2[a2++];
return arr3;
/********** End **********/
}
int* merge_sort(int *arr, int n)
// 基于merge_array函數(shù)編程實(shí)現(xiàn)歸并排序：自上而下的遞歸方法
// 函數(shù)參數(shù)：有序數(shù)組arr 數(shù)組arr長(zhǎng)度
// 函數(shù)返回值：返回從小到大排序后的數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int *rarr=&arr[n/2];
int lr=n-n/2;
qsort(arr,n/2,sizeof(int),cmp);
qsort(rarr,lr,sizeof(int),cmp);
merge_array(arr,n/2, rarr, lr);
/********** End **********/
}
第6關(guān)?快速排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
int partition_array(int *arr ,int l,int r)
// 編程實(shí)現(xiàn)arr[l, r]分區(qū)：選定一個(gè)基準(zhǔn)，左邊比基準(zhǔn)小，右邊比基準(zhǔn)大
// 返回基準(zhǔn)所處位置
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int temp = arr[l];
while(l<r)
{
while((l<r)&&arr[r]>=temp)
r--;
arr[l] = arr[r];
while((l<r)&&arr[l]<=temp)
l++;
arr[r] = arr[l];
}
arr[l] = temp;
return l;
/********** End **********/
}
int* quick_sort(int *arr, int l, int r)
// 基于partition_array函數(shù)編程實(shí)現(xiàn)快速排序：自上而下的遞歸方法
// 函數(shù)參數(shù)：有序數(shù)組arr 初始l=0，r=n-1
// 函數(shù)返回值：返回從小到大排序后的數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int pos = partition_array(arr,l,r);
if(l<r)
{
if(l<pos-1)
arr = quick_sort(arr,l,pos-1);
if(pos+1<r)
arr = quick_sort(arr,pos+1,r);
}
return arr;
/********** End **********/
}
第7關(guān)?堆排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void adjustHeap(int *arr, int param1, int j)
// 編程實(shí)現(xiàn)堆的調(diào)整
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int temp=0;
if(j<param1)
{
int max=j;
int s1=2*j+1;
int s2=2*j+2;
if(arr[s1]>arr[max]&&s1<param1)
max=s1;
if(arr[s2]>arr[max]&&s2<param1)
max=s2;
if(max!=j)
{
temp = arr[max];
arr[max] = arr[j];
arr[j] = temp;
adjustHeap(arr,param1,max);
}
}
/********** End **********/
}
int* heap_sort(int *arr, int n)
// 基于adjustHeap函數(shù)編程實(shí)現(xiàn)堆排序
// 函數(shù)參數(shù)：無(wú)序數(shù)組arr 數(shù)組長(zhǎng)度n
// 函數(shù)返回值：返回從小到大排序后的數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int i=0,temp=0;
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;
/********** End **********/
}
?第8關(guān)?計(jì)數(shù)排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
void sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《計(jì)數(shù)排序算法》
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組 數(shù)組長(zhǎng)度
// 要求輸出：調(diào)用print_array(int *arr, int n)輸出：
// 每一行一個(gè)元素及其個(gè)數(shù)（升序），如 1 1
// 以及最終的升序序列
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int max=arr[0];
int min=arr[0];
for(int i=0;i<n;i++)
{
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
min=arr[i];
}
int num[1000]={0};
for(int i=0;i<n;i++)
num[arr[i]]++;
int index=-1;
for(int j=min;j<=max;j++)
{
if(num[j]!=0)
printf("%d %d\n",j,num[j]);
int temp = num[j];
while(num[j]!=0)
{
arr[++index] = j;
num[j]--;
}
}
print_array(arr,n);
/********** End **********/
}
第9關(guān)?桶排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
int* sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《桶排序算法》
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組 數(shù)組長(zhǎng)度
// 函數(shù)返回值：返回從小到大排序后的數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int max=arr[0];
int min=arr[0];
for(int i=0;i<n;i++)
{
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
min=arr[i];
}
int num[100]={0};
for(int i=0;i<n;i++)
num[arr[i]]++;
int index=-1;
for(int j=min;j<=max;j++)
{
if(num[j]!=0)
int temp = num[j];
while(num[j]!=0)
{
arr[++index] = j;
num[j]--;
}
}
return arr;
/********** End **********/
}
第10關(guān)?基數(shù)排序
#include "sort_.h"
void print_array(int *arr, int n)
// 打印數(shù)組
{
if(n==0){
printf("ERROR: Array length is ZERO\n");
return;
}
printf("%d", arr[0]);
for (int i=1; i<n; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
int bucket[10]={0};
int temp[100]={0};
int* sort_array(int *arr, int n)
// 編程實(shí)現(xiàn)《基數(shù)排序算法》
// 函數(shù)參數(shù)：亂序整數(shù)數(shù)組 數(shù)組長(zhǎng)度
// 函數(shù)返回值：返回從小到大排序后的數(shù)組
{
// 請(qǐng)?jiān)谶@里補(bǔ)充代碼，完成本關(guān)任務(wù)
/********** Begin *********/
int max=arr[0];
for(int i=0;i<n;i++)
if(arr[i]>=max)
max=arr[i];
int d=1;
while(max>=10)
{
max/=10;
d++;
}
int i,j,k;
int radix = 1;
for(i=1;i<=d;i++)
{
for(j=0;j<10;j++)
bucket[j]=0;
for(j=0;j<n;j++)
{
k=(arr[j]/radix)%10;
bucket[k]++;
}
for(j = 1; j < 10; j++)
bucket[j] += bucket[j - 1] ;
for(j = n-1; j>=0; j--)
{
k = (arr[j] / radix) % 10;
temp[bucket[k] - 1] = arr[j];
bucket[k]--;
}
for(j = 0; j < n; j++)
arr[j] = temp[j];
radix = radix * 10;
}
return arr;
/********** End **********/
}
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-762373.html
到了這里，關(guān)于頭歌數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)參考---十大經(jīng)典排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
