12-5.排序

1.排序算法说明

1.1排序算法指标

• 稳定性：如果a==b且a在b前，排序后a仍保持在b前，则稳定，否则不稳定

• 内排序：算法程序的所有排序完全是在内存中执行的

• 外排序：由于数据量问题，需要把数据放置磁盘中，排序需要通过磁盘与内存间传输才可以进行

• 时间复杂度：运行一个算法程序所需要消耗的时长

• 空间复杂度：运行一个算法程序所需要消耗的内存大小

1.2各排序算法总结表

排序算法	最优情况	最差情况	时间复杂度	空间复杂度	排序方式	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	内排序	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	内排序	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	内排序	稳定
希尔排序	O(n log² n)	O(n log² n)	O(n log n)	O(1)	内排序	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	外排序	稳定
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	内排序	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	内排序	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	外排序	不稳定
桶排序	O(n+k)	O(n²)	O(n+k)	O(n+k)	外排序	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	外排序	稳定

n:数据量 k:桶的数量

2.算法具体实现

• 比较排序 (适用于一切需要排序的情况)

  在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。

  • 冒泡排序

  • 快速排序

  • 归并排序

  • 堆排序

• 非比较排序 (对数据规模和数据分布有一定的要求)

  通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。

  • 计数排序

  • 基数排序

  • 桶排序

2.1冒泡排序(Bubble Sort)

2.1.1定义

比较相邻两个数的大小，按照要求进行位置交换。

2.1.2图示

冒泡排序

2.1.3代码实现

/**
 * 冒泡排序
 *
 * @param array
 * @return
 */
public static int[] bubbleSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++)
        for (int j = 0; j < array.length - 1 - i; j++)
            if (array[j + 1] < array[j]) {
                int tem = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tem;
            }
    return array;
}