小哼买书（C&Java实现）
本篇博客主要是《啊哈！算法》的读书笔记，一本很好的算法书，这里做一下记录。
分别利用三种算法解小哼买书问题，主要依据书中代码，顺带写了一下Java语言的实现。
1、桶排序
C语言
/*
* 创建人：czc
* 创建时间：2019/8/29
* 创建用途：C语言桶排序解小哼买书
*/
#include<stdio.h>
int main(){
int total;
int a[1001],n,i,t;
//初始化
for(i=1;i<=1000;i++){
a[i]=0;
}
//读入n个数
scanf("%d",&n);
//循环读入n个图书的ISBN编号
for(i=1;i<=n;i++){
scanf("%d",&t);
if(a[t]==0){
a[t]=1;
total++;
}
}
printf("%d
",total);
for(i=1;i<=1000;i++){
if(a[i]==1){
printf("%d ",i);
}
}
return 0;
}
结果截图：
Java:
/*
创建人：czc
创建时间：2019/8/29
创建用途：Java利用桶排序解小哼买书问题
*/
import java.util.Scanner;
import static java.lang.System.out;
public class BucketSort {
public static void main(String[] args){
int[] a=new int[1001];
int n,i,t;
int total=0;
Scanner scanner=new Scanner(System.in);
//读入n
n=scanner.nextInt();
//循环读入n个ISBN编号
for(i=1;i<=n;i++){
t=scanner.nextInt();
if(a[t]==0){
a[t]=1;
total++;
}
}
out.println(total);
for(i=1;i<=1000;i++){
if(a[i]==1){
out.print(i+" ");
}
}
}
}
结果截图：
2、冒泡排序
C语言
/*
* 创建人：czc
* 创建时间：2019/8/29
* 创建用途：C语言冒泡排序解小哼买书
*/
#include<stdio.h>
int main(){
int total=1;
int a[101],n,i,j,t;
//读入n
scanf("%d",&n);
//循环读入n个图书ISBN编号
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//冒泡排序
for(i=1;i<=n-1;i++){
for(j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
total++;
}
}
printf("%d
",total);
printf("%d ",a[1]);
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
if(a[i]!=a[i-1]){
printf("%d ",a[i]);
}
}
}
return 0;
}
结果截图：
Java:
/*
创建人：czc
创建时间：2019/8/29
创建用途：Java利用冒泡排序解小哼买书问题
*/
import java.util.Scanner;
import static java.lang.System.out;
public class BubbleSort {
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int[] a=new int[101];
int n,i,j,t;
int total=1;
//读入n
n=scanner.nextInt();
//读入n个ISBN编号
for(i=1;i<=n;i++){
a[i]=scanner.nextInt();
}
//冒泡排序
for(i=1;i<=n-1;i++){
for(j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
total++;
}
}
out.println(total);
out.print(a[1]+" ");
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
out.print(a[i]+" ");
}
}
}
}
结果截图：
3、快速排序
C语言：
/*
* 创建人：czc
* 创建时间：2019/8/29
* 创建用途：C语言快速排序解小哼买书
*/
#include<stdio.h>
int a[101],n;
void quicksort(int left,int right){
int i,j,t,temp;
if(left>right){
return;
}
//temp存储基准数
temp=a[left];
i=left;
j=right;
while(i!=j){
//先从右往左找
while(a[j]>=temp&&i<j){
j--;
}
//再从左往右找
while(a[i]<=temp&&i<j){
i++;
}
//交换两个数在数组中的位置
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//将基准数归位
a[left]=a[i];
a[i]=temp;
//递归处理基准数的左右边
quicksort(left,i-1);
quicksort(i+1,right);
}
int main(){
int total=1,i;
//读入n
scanf("%d",&n);
//循环读入n个ISBN编号
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
quicksort(1,n);
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
total++;
}
}
printf("%d
",total);
printf("%d ",a[1]);
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
printf("%d ",a[i]);
}
}
return 0;
}
结果截图：
Java:
/*
创建人：czc
创建时间：2019/8/29
创建用途：Java利用快速排序解小哼买书
*/
import java.util.Scanner;
import static java.lang.System.out;
public class QuickSort {
private static int[] a=new int[101];
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n,i;
//读入n
n=scanner.nextInt();
int[] book=new int[n];
int j=1;
//读入n个ISBN编号
for(i=1;i<=n;i++){
a[i]=scanner.nextInt();
}
//快速排序
quickSort(1,n);
//输出排序后结果，且去重
book[1]=a[1];
for(i=2;i<=n;i++){
if(a[i]!=a[i-1]){
j++;
book[j]=a[i];
}
}
out.println(j);
for(i=1;i<=j;i++){
out.print(book[i]+" ");
}
}
private static void quickSort(int left,int right){
int i,j,t,temp;
//递归出口
if(left>right){
return;
}
//存储基准数
temp=a[left];
i=left;
j=right;
while(i!=j){
//先从右往左找
while(a[j]>=temp&&i<j){
j--;
}
//再从左往右找
while(a[i]<=temp&&i<j){
i++;
}
//交换两个数在数组中的位置
if(i<j){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//将基准数归位
a[left]=a[i];
a[i]=temp;
//递归处理基准数左右边
quickSort(left,i-1);
quickSort(i+1,right);
}
}
结果截图：
吾生也有涯，而知也无涯。