学习日志——算法（一）

本文编写于 995 天前，最后修改于 995 天前，其中某些信息可能已经过时。

为了参加某项赛事，正式开始学习算法了，作为算法方面的小白，看着书上的代码就如同天书一般。虽然很难，但还是要坚持下去。为了开一个好头，这次决定写一个稍微不那么难以理解的算法——排序。
最简单和古老的排序方法是桶排序。它的基本思想是由E.J.Issac和R.C.Singleton提出来的。顾名思义，就是假设有n个桶，设一个数组有n个元素，不妨把这n个元素看成对应不同值的球。然后把这n个球放在不同的桶里面。如果桶里有一个球，就说明这个球对应的值在数组中出现了一次；如果桶里有两个球，就说明这个球对应的值在数组中出现了两次，以此类推。

代码如下：

 int []a=new int[11];
    int i,j,t;
    Scanner in=new Scanner(System.in);
    for (i=0;i<a.length;i++){
        a[i]=0;   //初始化数组
    }
    for (i=0;i<6;i++){
        t=in.nextInt();//输入数字
        a[t]++;        //数组相应位置的元素+1，也就相当于上文所说的桶里多了一个球
    }
    for (i=0;i<a.length;i++){//遍历数组
        for (j=0;j<a[i];j++){ //如果a[i]不为0的话，就会打印出i
            System.out.println(i);
        }
    }

输入：6 2 5 4 3 7
输出：2 3 4 5 6 7

接下来的是冒泡排序，这是一种很有名的排序方法。它的基本思想是每两个相邻的元素进行比较，如果它们的顺序错误，就调换这两个元素的位置。从而可以实现从大到小或从小到大排序。
冒泡排序的代码如下：

int arr[] = new int[5];
    int temp;
    Scanner in=new Scanner(System.in);
    for (int i=0;i<arr.length;i++){
        arr[i]=in.nextInt();   //读入一些数字
    }
    for(int i=0;i<arr.length-1;i++){//n个数进行排序，只需要进行n-1次比大小
        for(int j=0;j<arr.length-i-1;j++){//每一轮比较的次数
            if(arr[j+1]<arr[j]){ //当前面的元素比后面的大时，交换他们的位置
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    for (int i=0;i<arr.length;i++){ //输出排序后的数组
        System.out.println(arr[i]);
    }

输入：10 15 24 3 17
输出：3 10 15 17 24

在看到这一部分时一开始有一个地方有点理解不来，就是嵌套循环的内层为什么是j<arr.length-i-1。其实仔细想想后就想通了，外层的循环完成i次，就有i个元素已经处于正确的位置上了，那么内层循环，即从第一个开始两两比较，就不用再将已经放好的元素拿来比较了，所以内层比较的次数就要减去i。

接下来是一个更有效率的排序方法——快速排序。快速排序的基本原理是在几个数组成的序列中随便找一个数作为基准数。将小于这个数的放在左边，大于这个数的放在右边。然后在基准数左边和右边的两部分采取同样的方法，找一个基准数，把小于这个数的放在左边，大于这个数的放在右边。最后就能得到由小到大排列的序列。
代码如下：

public class sortthree {
static int []a=new int[101];
static void quicksort(int left,int right){
    int i,j,t,temp;
    if (left>right){
        return;
    }
    temp=a[left];//temp储存基准数
    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);//处理基准数右边的数（大于基准数的数）
    return;
}
public static void main(String args[]) {
    int i,j,n;
    Scanner in=new Scanner(System.in);
    n=in.nextInt();
    for (i=1;i<=n;i++){
        a[i]=in.nextInt();
    }
    quicksort(1,n);
    for ( i=1;i<=n;i++){
        System.out.println(a[i]);
    }
    return;
}

输入：10
      6 1 2 7 9 3 4 5 10 8
输出：1 2 3 4 5 6 7 8 9 10

可以看出，与前面两种方法相比，快速排序效率更高，更快速。也是我本人觉得比较好的一种算法。

这一篇学习日志就到这里了，万事开头难，希望自己能够坚持下去。

登录后台

页面导航

代码如下：