1. 一次循環查找
#include<stdio.h>
//找到最大的元素和次大的元素
void find(int a[],int b[])
{
int max1=a[0];
int max2=-1000,t;
for(int i=0;i<6;i++)
{
if(a[i]>max2)
if(a[i]>max1)
max2=a[i];
else
{
max2=max1;
max1=a[i];
}
}
b[0]=max1;
b[1]=max2;
}
int main()
{
int b[2]={0,0};
int a[]={2,5,1,4,6,3};
find(a,b);
printf("最大值為%d",b[0]);
printf("\n");
printf("次大值為%d",b[1]);
}
2.兩次循環查找
#include<stdio.h>
//找到最大的元素和次大的元素
void find(int a[],int b[])
{
int max=a[0];
int max1=0;
for(int i=0;i<6;i++)
{
if(a[i]>max)
max=a[i];
}
for(int i=0;i<6;i++)
{
if(a[i]<max&&a[i]>max1)
max1=a[i];
}
b[0]=max;
b[1]=max1;
}
int main()
{
int b[2]={0,0};
int a[]={2,5,1,4,6,3};
find(a,b);
printf("最大值為%d",b[0]);
printf("\n");
printf("次大值為%d",b[1]);
}
3.減1排序
#include<stdio.h>
void sort(int a[],int n)
{
int p;
int k=0;
int b[n],c[n];
for(int i=0;i<n;i++)
{
b[i]=a[i];
c[i]=a[i];
}
printf("\n");
while(k<n)
{
for(int i=0;i<n;i++)
{
b[i]=b[i]-1;
if(b[i]==0)
a[k++]=c[i];
}
}
}
int main()
{
int a[]={2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
printf("排序前，數組為");
for(int i=0;i<6;i++)
printf("%d",a[i]);
sort(a,n);
printf("排序後，數組為");
for(int i=0;i<6;i++)
printf("%d",a[i]);
printf("\n");
printf("最大值為%d",a[n-1]);
printf("\n");
printf("次大值為%d",a[n-2]);
return 0;
}
4.簡單選擇排序
#include<stdio.h>
void sort(int a[],int n)
{
int t;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[j]>a[i])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
}
}
}
int main()
{
int a[]={2,5,1,4,6,3};
sort(a,6);
printf("最大值為%d",a[0]);
printf("\n");
printf("次大值為%d",a[1]);
}
5.冒泡排序
#include<stdio.h>
void sort(int a[],int n)
{
int t;
for(int i=0;i<n;i++)
for(int j=0;j<n-i-1;j++)
if(a[j+1]>a[j])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
int main()
{
int a[]={2,5,1,4,6,3};
sort(a,6);
printf("數組為");
for(int i=0;i<6;i++)
printf("%d",a[i]);
printf("\n");
printf("最大值為%d",a[0]);
printf("\n");
printf("次大值為%d",a[1]);
}
6.直接插入排序
#include<stdio.h>
void sort(int a[],int n)
{
int i,j;
for(i=2;i<n;i++)
{
a[0]=a[i];
j=i-1;
while(a[0]>a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=a[0];
}
}
int main()
{
int a[]={-100,2,5,1,4,6,3};
printf("排序前數組為");
for(int i=1;i<=6;i++)
printf("%d",a[i]);
printf("\n");
sort(a,7);
printf("排序後數組為");
for(int i=1;i<=6;i++)
printf("%d",a[i]);
printf("\n");
printf("最大值為%d",a[1]);
printf("\n");
printf("次大值為%d",a[2]);
}
7.折半插入排序
#include<stdio.h>
void sort(int r[],int length)
{
int x;
int mid;
for(int i=2;i<=length;i++)//從第2個值開始，不斷插入
{
x=r[i];//将插入值存放在x中
int low=1;
int high=i-1;//high表示上一次數組的最後一個位置的值
while(low<=high)
{
mid=(low+high)/2;
if(x<r[mid]) //比較與中間值的大小關系
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>=low;j--)//将所有的後面的值向前挪
r[j+1]=r[j];
r[low]=x;//在low處放入數之
}
}
int main()
{
int a[]={0,2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
printf("排序前數組為");
for(int i=1;i<7;i++)
printf("%d ",a[i]);
sort(a,n);
printf("\n");
printf("排序後數組為");
for(int i=1;i<7;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[n-1]);
printf("\n");
printf("次大值為%d",a[n-2]);
return 0;
}
8.快速排序
//快速排序
#include<stdio.h>
#include<malloc.h>
int part(int a[],int s,int t)
{
int *b;
int i,j;
int k=s;
int mid=a[s];
i=s;
j=t;
b=(int*)malloc((t-s+1)*sizeof(int));
for(int k=s+1;k<=t;k++)
{
if(a[k]<mid)
b[j--]=a[k];
else
b[i++]=a[k];
}
b[i]=mid;
for(int v=s;v<=t;v++)
a[v]=b[v];
free(b);
return i;
}
void sort(int a[],int s,int t)
{
int i;
if(s<t)
{
i=part(a,s,t);
sort(a,s,i-1);
sort(a,i+1,t);
}
}
int main()
{
int a[]={-100,2,5,1,4,6,3};
printf("排序前數組為");
for(int i=1;i<=6;i++)
printf("%d ",a[i]);
printf("\n");
sort(a,1,6);
printf("排序後數組為");
for(int i=1;i<=6;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[1]);
printf("\n");
printf("次大值為%d",a[2]);
}
9.歸并排序
//歸并排序
#include<stdio.h>
#include<malloc.h>
void merge(int a[],int low,int mid,int high)
{
int i=low;
int j=mid+1;
int k=0;
int *temp;
temp=(int *)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
for(int i=low,k=0;i<=high;i++)
a[i]=temp[k++];
free(temp);
}
void sort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
sort(a,low,mid);
sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
int main()
{
int a[]={-100,2,5,1,4,6,3};
printf("排序前數組為");
for(int i=1;i<=6;i++)
printf("%d ",a[i]);
printf("\n");
sort(a,1,6);
printf("排序後數組為");
for(int i=1;i<=6;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[6]);
printf("\n");
printf("次大值為%d",a[5]);
}
10.希爾排序
#include<stdio.h>
void sort(int a[],int n)
{
int i,j,gap,temp,k;
printf("%d",n);
for(gap=n/2;gap>=1;gap/=2)
{
for(i=0;i<gap;i++)
{
for(j=i+gap;j<n;j+=gap)
{
if(a[j-gap]>a[j])
{
temp=a[j];
for(k=j-gap;k>=0&&a[k]>temp;k-=gap)
a[k+gap]=a[k];
a[k+gap]=temp;
}
}
}
}
}
int main()
{
int a[]={2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
sort(a,n);
printf("數組為");
for(int i=0;i<6;i++)
printf("%d",a[i]);
printf("\n");
printf("最大值為%d",a[n-1]);
printf("\n");
printf("次大值為%d",a[n-2]);
return 0;
}
11.堆排序
#include<stdio.h>
void head_adjust(int* arr,int s,int m) // 一個交換的過程
{
int temp=arr[s]; //将要交換的值存起來
for(int j=2*s+1;j<=m;j=2*j+1) //挑出目前層的最大值
{
if(j<m&&arr[j]<arr[j+1])//選擇兩個中較大的
++j; //左邊小的話選右邊
if(temp>=arr[j])//如果有一個值超過了arr[j],兩者進行一次交換
break;
arr[s]=arr[j];//交換1
s=j; //記錄j的小标
}
arr[s]=temp; //交換2
}
void swap(int a,int b) //将兩個數字進行交換
{
int t;
t=a;
a=b;
b=t;
}
void sort(int *arr,int len)
{
for(int i=(len-1)/2;i>=0;i--)//建立一個大頂堆 //保證n-1層滿足即可
{
head_adjust(arr,i,len-1); //
}
for(int i=len-1;i>0;i--)//進行堆排序
{
swap(arr[0],arr[i]);//每次與将其中的一個值與a[0]交換，破壞頂堆
head_adjust(arr,0,i-1);//堆頂元素和堆底元素交換，使用的大頂堆
}
}
int main()
{
int a[]={2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
printf("排序前數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
sort(a,n);
printf("\n");
printf("排序後數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[0]);
printf("\n");
printf("次大值為%d",a[1]);
return 0;
}
12.桶排序
//快速排序
#include<stdio.h>
#define N 100
void sort(int a[],int n)
{
int k=0;
int bucket[N];
for(int i=0;i<N;i++)
bucket[i]=0;
for(int i=0;i<n;i++)
bucket[a[i]]=1;
for(int i=0;i<N;i++)
for(int j=0;j<bucket[i];j++)
a[k++]=i;
}
int main()
{
int a[]={2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
printf("排序前數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
sort(a,n);
printf("排序後數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[n-1]);
printf("\n");
printf("次大值為%d",a[n-2]);
}
13.計數排序
#include<stdio.h>
void sort(int a[],int n)
{
int max=a[0],min=a[0];
for(int i=0;i<n;i++) //挑選最大，最小值
{
if(a[i]>max)
{
max=a[i];
}
if(a[i]<min)
{
min=a[i];
}
}
int k=max-min+1;
int c[k]={0}; //建立計數數組
for(int i=0;i<n;i++) //計數
{
c[a[i]-min]+=1;
}
int j=0;
for(int i=0;i<k;i++)
{
while(c[i]>0)
{
a[j]=i+min;
j++;
c[i]--;
}
}
}
int main()
{
int a[]={2,5,1,4,6,3};
int n=sizeof(a)/sizeof(a[0]);
printf("排序前數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
sort(a,n);
printf("排序後數組為");
for(int i=0;i<6;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[n-1]);
printf("\n");
printf("次大值為%d",a[n-2]);
}
14.基數排序
#include<stdio.h>
#include<stdlib.h>
void RadixCountSort(int *index,int *a,int len)
{
int i;
int *count=(int *)malloc(sizeof(int)*10);
for(i=0;i<10;i++) //計數數組為0
count[i]=0;
for(i=0;i<len;i++) //記錄索引對應标記
count[index[i]]++;
for(i=1;i<10;i++) //将數字累加
count[i]=count[i]+count[i-1];
int *sort=(int *)malloc(sizeof(int)*len); //建立一個臨時數組空間
for(i=len-1;i>=0;i--) //倒序輸出
{
count[index[i]]--; //對應位置-1
sort[count[index[i]]]=a[i]; //放入對應的數組
}
//index[i]值-----sort----count[]下标
for(i=0;i<len;i++)
a[i]=sort[i];
free(sort);
free(count);
}
void RadixSort(int *a,int len)
{
int i,x=1;
int tmp=1;
int *radix=(int *)malloc(sizeof(int)*len);//建立一個單個位數的數組 （同為個位，十位，或百位）
while(x) //當x不等于0時
{
tmp=tmp*10;
x=0;
for(i=0;i<len;i++)
{ //舉例當a[i]=123
radix[i]=a[i]%tmp; // 3 23 123 123
radix[i]=radix[i]/(tmp/10); // 3 2 1 0
if(a[i]/tmp>0)//如果對應還存在不為0的商，繼續循環
{
x=1;
}
}
RadixCountSort(radix,a,len);//是數組a發生變化，本輪的a将會排好
//同位數的比較，當a排好之後，位數相同的就排好了
// 不位數的比較，位數不同的以0做區分
}
free(radix);
}
int main()
{
int i,len;
int a[]={2,5,1,4,6,3};
len=sizeof(a)/sizeof(int);
printf("排序前，數組為");
for(i=0;i<len;i++)
printf("%d ",a[i]);
printf("\n");
RadixSort(a,len);
printf("排序後，數組為");
for(i=0;i<len;i++)
printf("%d ",a[i]);
printf("\n");
printf("最大值為%d",a[len-1]);
printf("\n");
printf("次大值為%d",a[len-2]);
return 0;
}