排序算法（Java）

每一行关键代码都有解释，只需要拿出笔和纸结合代码中的说明一步步操作，就能很容易理解这几个算法。

桶排序

   1.待排序数组和桶数组，待排序数字的最大数字加1为桶的个数
   2.桶数组的初始化会默认全是0，由于数组的有序性，这些桶相当于顺序编号（0,1,2，……，n）
   3.把待排序数组中与桶的序号相等的数放置在对应的桶中，同一个序号对应多少个数字，这个桶在桶数组中的值（0）就变为多少
   4.顺序输出桶数组的下标，每个下标对应的桶数组中的值是多少就输出该下标多少次，若为0，即为不输出。代码如下

<pre>public class BucketSort {
private int[] array; //存储通过构造函数传入的待排序数组
private int[] buckets; //桶

/\*\* 
 \* 初始化数组
 \* @param range 待排序数组中的最大数字
 \* @param array 待排序的数组
 \*/
public BucketSort(int range, int[] array) {
    this.array = array;
    buckets = new int[range];
}

/\*\*
 \* 待排序数组中的最大数字即为桶的长度，array中的数字对应buckets中的数组下标，桶中存储的是
 \* array中当前数字的个数
 \*/
public void sort() {
    if (array != null && array.length > 1) {
        for (int i = 0; i < array.length; i++) {
            buckets[array[i]] ++;
        }
    }
}

/\*\*
 \* 顺序打印出buckets的下标，对应下标的buckets中的数是多少就打印多少次，若是0则不打印
 \*/
public void print() {
    for (int i = 0; i < buckets.length; i++) {
        for (int j = 0; j < buckets[i]; j++) {
            System.out.println(i);
        }
    }
}

}</pre>

</br>

冒泡排序

    1.从左向右，第一个数和第二个数相比，若第一个数大于第二个，则两数互换位置。同理第二个数字和第三个数字。当最右边两个数比较完成后，最右边的数字即为所有数中的最大数。即第一个最大数“冒”了出来
    2.排除最后一个数字，剩下的数，继续从左到右，第一个数和第二个数字相比，若第一个数大于第二个，则两数互换位置……，最后，最右边的数字即为当前数中的最大数字。即第二个最大数“冒”了出来
    3.重复这个步骤，当所有数字都这样“冒”了一遍，整体即已经从小到大顺序排列。代码如下

<pre>public class BubbleSort {
private int[] array; //存储通过构造函数传入的待排序数组

public BubbleSort(int[] array) {
    this.array = array;
}

/\*\*
 \* 由于冒泡排序每次只冒出一个最大数字，所以需要冒（array.length-1）次，最后一个数字不
 \* 需要冒便已经排好序，所以是 （int i = 1; i < array.length; i++）
 \* 每一次冒泡，都是左右两个数字做比较，而且都会减少一个待排数，所以左右比较的次数会是
 \* （array.length - i）次，所以是(int j = 0; j < array.length - i; j++)
 \*/
public void sort() {
    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < array.length - i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

/\*\*
 \* 顺序输出，即从小到大排列，若需要从大到小排列，倒序输出即可
 \*/
public void print() {
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}

}
</pre>

</br>

快速排序

    1.对于待排序数组，选择其中一个数（一般选择第一个即可）作为基准，实现思想是，这个基准数的左边的数全部小于这个基准数，右边的数全部大于这个基准数。
    2.当选取第一个数为基准数后。从右向左，逐个检查数字是否小于基准数，如果是，则交换当前数和基准数；然后再从左向右，逐个检查数字是否大于基准数，如果是，则交换当前数和基准数。然后再从右到左……从左到右……直到从右到左和从左到右检查刚好重合到同一个数字。
    3.此时，基准数左边的数全部小于基准数，右边的数全部大于基准数。然后再分别对两部分数据进行同上诉的操作。代码如下

<pre>public class QuickSort {
private int[] array; // 存储通过构造函数传入的待排序数组
public QuickSort(int[] array) {
this.array = array;
}
public void sort() {
quickSort(array, 0, array.length - 1);
}
/**
* 递归方法
* @param src 待排序数组
* @param begin 待排序数组的最左边的序号
* @param end 待排序数组的最右边的序号
*/
public void quickSort(int[] src, int begin, int end) {
//当begin与end相等，即满足从右到左和从左到右检查刚好重合，基准数左边的数小于基准
//数，右边的数大于基准数，所以只有在begin小于end时才进行逐个检查
if (begin < end) {
//取第一个数为基准数
int key = src[begin];
//待排序数组的最左边的序号
int i = begin;
//待排序数组的最右边的序号
int j = end;
while (i < j) {
while (i < j && src[j] > key) {
//从右向左，逐个检查
j--;
}
if (i < j) {
//当上面的while循环结束，即为检查找到了比基准数小的数，然后把当前
//序号i处的数的值设为这个比基准数小的数的值
src[i] = src[j];
//此时开始从左向右检查
i++;
}
while (i < j && src[i] < key) {
//从左向右，逐个检查
i++;
}
if (i < j) {
//当上面的while循环结束，即为检查找到了比基准数大的数，然后把当前
//序号处为j的数的值设为这个比基准数大的数的值
src[j] = src[i];
//此时继续从右向左检查
j--;
}
//上诉的循环执行结束，表明i和j到达了同一个位置，此时这个位置的值应设置为
//基准数，因为i之前的数都要比基准数小，j之后的数都要比基准数大，所以i和j
//所在的位置即是基准数
src[i] = key;
//基准数左边的部分进行快速排序
quickSort(src, begin, i - 1);
//基准数右边的部分进行快速排序
quickSort(src, j + 1, end);
}
}
}
public void print() {
for (int i = 0; i < array.length - 1; i++) {
System.out.println(array[i]);
}
}
}</pre>

</br>

选择排序

    1.整体思想是：数组分为已排序数组和待排序数组两部分，然后遍历待排序数组，插入到已排序数组的正确位置。默认数组的第一个数是已经排好序的。
    2.从第二个数开始，与前一个数比较，若小于前一个数，则把当前的数拿出来作为临时变量，把前一个数移到当前数的位置，再把这个临时变量放到前一个数的位置上，依此进行循环。待排序部分就会慢慢减少，直到全部排好序。代码如下

<pre>public class InsertSort {
private int[] array; //存储通过构造函数传入的待排序数组

public InsertSort(int[] array) {
    this.array = array;
}

public void sort() {
    //由于第一个数相当于是已经排好序的，所以i=1，循环要从第二个数开始
    for (int i = 1; i < array.length; i++) {
        //临时变量存储当前数
        int temp = array[i];
        //j为下面for的设定条件，从当前数开始循环判断
        int j = i;
        //如果当前数的前一个数大于当前数，则把当前这个位置的值设为前一个数的值，然后
        //j自减1后再判断此时的当前数的前一个数是否大于此时的当前数，依此完成移位
        for (; j > 0 && array[j-1] > temp; j--) {
            //把当前位置的值改为前一个数的值
            array[j] = array[j-1];
        }
        //循环结束，说明j已经移位到了一个小于右边数大于左边数的位置，也就是已经到达
        //它应该插入的位置
        array[j] = temp;
    }
}

public void print() {
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}

}</pre>