[Algorithm] 常见排序算法的总结

[fred-ye]

好久没看看算法这些东西了，今天突然想看一下，先看几个常见的排序算法，自己写写。找找当年的感觉。

算法的分类

常见的排序算法通常可以划分为插入排序，交换排序，选择排序三大类，每一类中又有多个子类： 1.选择排序：直接选择排序 2.插入排序：直接插入排序，折半插入排序，希尔排序 3.交换排序：冒泡排序，快速排序

• 以下代码中如没有特殊说明，int [] a是待排序数组，int n 是数组的长度。最初采用C写，所以传了一个数组长度进去，如果用java实际上就没必要了。

  直接选择排序

思想： 第一趟：程序将记录定位在第1个数据上，将第1个数据和后面的每个数据进行比较，如果第1个数据大于后面某个数据，交换它们,第一趟结束后，最大数在最末。 第二趟：程序将记录定位在第2个数据上，将第2个数据和后面的第个数据进行比较，如果第2个数据大于后面某个数据，交换它们 .... 依次类推了。

/**
 * @param a
 *            array
 * @param n
 *            the length of array
 */
public static void selectSort(int a[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

修正后直接选择排序

思想：直接选择排序的一个缺点是每一趟中都会进行多次的数据交换，而实际上每一趟都只是从子序列中选出一个最大值或最小值到末尾。因此，其实可以只需要找出本趟中的最小数或最大数，然后和子序列的第一个元素或最后一个元素交换就行。 如对于序列[3,1,2,5,4]： 第一趟，找出最小值1,和序列的第一值比较，1<3，将1放到首位，序列变为[1,3,2,5,4] 第二趟, 从子序列[3,2,5,4]中找出最小值2,和子序列的第一个值比较2<3,将2放到首位,序列变为[1,2,3,5,4] 第三趟，从子序列[3,5,4]中找出最小值3，和子序列的第一个值比较3=3,所以不用移动。序列还是[1,2,3,5,4] 第四趟, 从子序列[5,4]中找出最小值4，和子序列的第一个值比较4<5，故将二者对换，序列变为[1,2,3,4,5]. 排序结束。

public static void ajustSelectSort(int a[], int n) {
    int i, j, k, minIndex;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            k = a[i];
            a[i] = a[minIndex];
            a[minIndex] = k;
        }
    }
}

插入排序

思想：依次将待排序的数组元素按其关键字的大小插入前面的有序序列。 第一趟：将第2个位置上的元素插入到前面的有序序列，此时，前面只有一个元素，当然是有序的。 第二趟：将第3个位置上的元素插入到前面的有序序列， .......

public static void insertSort(int a[], int n) {
    int i, j, k, t;
    for (j = 1; j < n; j++) {
        t = a[j];
        k = j - 1;
        while ((k >= 0) && (a[k] > t)) {
            a[k + 1] = a[k];
            k = k - 1;
        }
        a[k + 1] = t;
    }
}

折半插入排序

思想：对于简单插入而言，当第i-1趟需要将第i个元素插入到前面的0~i-1个元素序列中，它总是从i-1个元素开始逐个比较每个元素，直到找到它的位置，这显然没有利用前面的0~i-1个元素已有序的特点。折半插入排序则是对这一缺点的改进,其思想可参看这个 ,代码记录如下：

public static void binaryInsertSort(int a[], int n) {
    int i, j, low, high, temp, mid;
    for (i = 1; i < n; i++) {
        temp = a[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (temp > a[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        for (j = i; j > low; j--) {
            a[j] = a[j - 1];
        }
        a[low] = temp;
    }
}

希尔排序

希尔排序实际上是分组的插入排序。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。维基百科中对此有详细的讲解

public static void shellSort(int[] array) {
    int i, j, d, t;
    int length = array.length;
    for (d = length / 2; d >= 1; d /= 2) {
        // 子序列中相隔增量为d的数据元素直接进行插入排序
        for (j = d; j < length; j++) {
            t = array[j];
            i = j - d;
            while ((i >= 0) && array[i] > t) {
                array[i + d] = array[i];
                i = i - d;
            }
            array[i + d] = t;
            System.out.println("增量为" + d + "   元素-->"
                    + Arrays.toString(array));
        }
    }
}

冒泡排序

思想： 第一趟，依次比较0和1,1和2，2和3...,n-2和n-1索引的元素，如果发现前一数据大于后一数据，交换它们，经过第1趟，最大的元素排到最后。 第二趟，依次比较1和2,2和3，3各4...,n-2和n-1索引的元素，如果发现前一数据大于后一数据，交换它们，经过第2趟，第2大的元素排到倒数第2位。 ....... 所以：直接选择排序和冒泡排序的一个很重要的区别在于：冒泡排序每次比较的是相邻的元素。

public static void bubbleSort(int a[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

修正后的冒泡排序

思想：冒泡排序可以每一次将最大的元素移到最末，同时也可以理顺部分元素。其有一个很重要的特点，一旦某一趟没有交换发生，即可提前结束排序。因此，我们采用一个标识flag，对一趟排序的初始值为0, 对于每一趟排序，当发生交换时，就将flag设为1。如果一趟排序后，发现没有flag还是为0，即没有发生交换，则可提前退出排序。

public static void ajustBubbleSort(int a[], int n) {
    int i, j, k, flag;
    for (i = 0; i < n; i++) {
        flag = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                k = a[j + 1];
                a[j + 1] = a[j];
                a[j] = k;
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。 分：以数组中的某一项元素x为枢轴(pivot)，把数组分成两部分，前一部分的所有元素均≤x，后一部分的所有元素均≥x； 治：对前后两部分数组采用同样的办法处理。 其步骤为：

1. 从数列中挑出一个元素，称为 基准（pivot）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 示意图如下，摘自维基百科： 。 代码如下：

public static void quickSort(int[] array, int low, int upper) {
    if (low < upper) {
        int i = low, j = upper;
        int temp = array[low];
        while (i < j) {
            while (i < j && array[j] > temp)
                j--;
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            while (i < j && array[i] < temp)
                i++;
            if (i < j) {
                array[j] = array[i];
                j--;
            }
            array[i] = temp;
            quickSort(array, low, i - 1);
            quickSort(array, i + 1, upper);
        }
    }
}