数据结构(三)简单排序算法
- O(n^2) : 选择排序、冒泡排序、插入排序、希尔排序
- O(nlogn) :归并排序、快速排序、堆排序
- O(n+1) :桶排序、基数排序、计数排序
选择排序(Selection Sort)
选择排序是一种最简单的排序算法,它的算法步骤如下:
- 找到数组中最小的元素
- 将它和数组的第一个元素交换位置(如果相同,也交换)
- 在剩下的元素中找到最小的元素
- 将它和数组的第二个元素交换位置
- 重复。。
选择排序交换的总次数为N,算法的效率取决于比较的次数。
特点:
- 运行时间和输入无关、移动数据是最少的
- 选择排序是不稳定的排序方法
- 对于长度为 N 的数组,选择排序需要大约 N²/2次比较和 N 次交换
- 时间复杂度 O(n^2)
1 | public static void selectSort(int[] arr){ |
插入排序(Insertion Sort)
插入排序,将数插入到其他已经有序的数中的适当位置。为了给要插入的数腾出空间,我们需要将其余所有元素在插入之前都向右移动一位。
插入排序所需的时间取决于输入中元素的初始顺序。(原始数据越接近有序,越快)
命题:对于随机排列的长度为 N 且主键不重复的数组,平均情况下插入排序需要约 N²/4 次比较以及 N²/4 次交换。最坏情况下需要 约 N²/2 次比较以及 N²/2 次交换,最好情况下需要 N-1 次比较 和 0 次交换。
时间复杂度:O(n^2)
1 | /** |
希尔排序(Shell Sort)
在插入排序和选择排序中,由于它们只能交换相邻的元素,如果有位于数组起始的大元素,则需要多次遍历才能交换到队尾,很不划算。希尔排序以更大的间隔来比较和交换元素,这样,大元素在交换的时候,可以向右移动不止一个位置。
希尔排序只需要在插入排序的代码中将移动的元素距离由1改为h即可。
希尔排序依赖于间隔(step)的选取。
1 | public class Shell { |
冒泡排序
比较相邻元素,大的放右边
要点:第一躺结束后,最右元素一定是最大的,因此第二趟最右元素不参与,即 size - i - 1
时间复杂度:O(n^2)
1 | public static void bubbleSort(int[] arr){ |