经典排序算法总结

[luoxn28]

排序就是将一些数据按照其中某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法在很多方面都有重要的应用，尤其是在大数据的处理方面，一个优秀的排序可以节省大量的计算资源。

冒泡排序

冒泡排序是一种简单易理解的排序算法，其思想是依次遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，依次遍历数列直到该数列排序完成。该算法名字由来就是因为数列中较小的元素会慢慢“浮”到数列的顶端。

/**
 * bubble sort.
 * A simple sort function.
 */
static void bubbleSort(int[] array) {
    int length = array.length;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j+1]) {
                swap(array, j, j+1); // 交换数组中两个元素的值
            }
        }
    }
}

选择排序

选择排序的思想就是首先找到数组中最小的那个元素，其次，将它和数组的第一个元素交换(如果第一个元素就是最小元素那么它就和自己交换)。再次，在剩下数组中元素找到最小的元素，和数组的第二个元素交换。如此循环往复，直到把整个数组排好序。

/**
 * select sort.
 */
static void selectSort(int[] array) {
    int length = array.length;

    for (int i = 0; i < length; i++) {
        int min = i;
        for (int j = i + 1; j < length; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }

        if (min != i) {
            swap(array, i, min);
        }
    }
}

插入排序

插入排序是一种简单直观的排序算法，其思想是通过构建有序队列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

/**
 * insert sort.
 */
static void insertSort(int[] array) {
    int length = array.length;

    for (int i = 1, j; i < length; i++) {
        for (j = i; (j > 0) && (array[j] < array[j-1]); j--) {
            swap(array, j, j - 1);
        }
    }
}

快速排序

快速排序是一种分治的排序算法，它将一个数组分成两个数组，将两个部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序的方式是当两个子数组有序时整个数组也就自然有序了。归并排序中，递归发生在处理整个数组之前，一个数组被分为两半；快速排序中，递归调用发生在处理整个数组之后，切分的位置取决于数组的内容。 快速排序递归地将子数组a[left…right]排序，先用partion()方法将a[j]放到一个合适的位置，然后在递归调用将其它位置的元素排序。

/**
 * quit sort.
 */
static int partion(int[] array, int left, int right) {
    int i, j;
    int tmp = array[right];

    for (i = j = left; i < right; i++) {
        if (array[i] <= tmp) {
            swap(array, i, j++);
        }
    }
    swap(array, j, right);

    return j;
}
static void quickSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = partion(array, left, right);
        quickSort(array, left, mid - 1);
        quickSort(array, mid + 1, right);
    }
}
static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
}

归并排序

归并排序是将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归的）将他分成两半分别排序，让后将结果归并起来。它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点就是所需的额外空间和N成正比。

/**
 * merge sort.
 */
static void merge(int[] array, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;
    int[] tmpArray = new int[array.length];

    while ((i <= mid) && (j <= right)) {
        if (array[j] < array[i]) {
            tmpArray[k++] = array[j++];
        }
        else {
            tmpArray[k++] = array[i++];
        }
    }
    while (i <= mid) {
        tmpArray[k++] = array[i++];
    }
    while (j <= right) {
        tmpArray[k++] = array[j++];
    }

    /* back fill the array data */
    for (int t = left; t <= right; t++) {
        array[t] = tmpArray[t];
    }
}
static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}
static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length - 1);
}

堆排序

堆排序可以分为两个阶段。在堆的构造阶段，我们将元使数组重新组织安排进一个堆中；然后在下沉阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。堆排序主要工作都是在堆的下沉阶段完成的，这里我们将堆中最大的元素删除，然后放入堆缩小后数组中空出的位置。

/**
 * heap sort.
 */
static void sink(int[] array, int maxIndex, int k) {
    while (2 * k <= maxIndex) {
        int child = 2 * k;
        if ((2 * k < maxIndex) && (array[child] < array[child + 1])) {
            child++;
        }

        if (array[k] >= array[child]) {
            break;
        }

        swap(array, k, child);
        k = child;
    }
}
static void heapSort(int[] array) {
    for (int i = array.length / 2; i >= 0; i--) {
        sink(array, array.length - 1, i);
    }

    int maxIndex = array.length - 1;
    while (maxIndex > 0) {
        swap(array, 0, maxIndex--);
        sink(array, maxIndex, 0);
    }
}

各种排序算法的稳定性和时间复杂度分析

什么是排序的稳定性呢？如果一个排序算法能够保留数组中重复元素的相对位置则可以称为是稳定的。以下是各个排序算法稳定性总结：

• 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
• 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 各个排序时间复杂度总结：
• 冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(n^2)。
• 插入排序：O(n^2)
• 选择排序：O(n^2)
• 快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
• 归并排序：log2(n)*n
• 堆排序：log2(n)*n

参考链接：

1. 视觉直观感受 7 种常用的排序算法
2. 排序算法源码