排序算法学习(1)-简单排序
文章目录
选择排序
选择排序(Selection Sort)是一种非常简单明了的排序算法,其基本思路是:假设一个数组有 n 个数,从第一个数开始,遍历一遍找到最小的一个数的下标,将最小的数与第一个数交换位置,这样第一个数的位置就排好了,接下来从第二个数开始遍历找到从 2 到 n 中最小的数与第二个数做交换,如此反复,知道第 n-1 个数也排好序了,整个数组排序就结束了。
示意图

代码示例:
public class SelectionSort {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int mini = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[j] < arr[mini]) {
mini = j;
}
}
swap(arr, i, mini);
}
}
}时间复杂度和空间复杂度
算法第一次循环执行 n-1 次,第二次循环执行 n-2 次,以此类推,直到排序完成大约执行了 (n-1) + (n-2) + ... + 2 + 1,这是一个等差数列,根据等差数列公式可以得出执行了 $\frac{n^2}{2} - \frac{n}{2}$ 次,忽略常数项和低次项得到时间复杂度 $O(n^2)$
根据算法的计算过程,可以知道不论是什么数组都要执行 $\frac{n^2}{2} - \frac{n}{2}$ ,其最好和最差的情况下时间复杂度都是 $O(n^2)$
算法除开一些临时变量并没有使用一些额外空间,因此空间复杂度是 $O(1)$
稳定性
由于算法是直接将数组中找到的最后一个最小的数与第一个数交换,因此相等的两个数的顺序会在交换之后改变,所以选择排序是一个不稳定的排序算法

优化
在一次循环遍历中同时找到最大和最小值,分别与最后一位和第一位数进行交换,减少循环的次数。尽管如此,其时间复杂度任然是 $O(n^2)$

代码示例:
public static void sort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len/2; i++) {
int mini = i;
int maxi = i;
for (int j = i + 1; j < len-i; j++) {
if (arr[j] < arr[mini]) {
mini = j;
}
if (arr[j] > arr[maxi]) {
maxi = j;
}
}
swap(arr, i, mini);
// 注意在最大值交换前有可能已经被最小值交换
if (maxi == i) {
maxi = mini;
}
swap(arr, len-1 - i, maxi);
}
}冒泡排序
冒泡排序也是简单排序的一种,其算法思路是:假设一个数组的长度为 n ,比较第一个数和第二个数,若第一个数大于第二个数,交换两个数,再比较第二个数与第三个数的大小,大于则交换,同样地比较剩下的数,最后,最大的数将会到数组末尾,第 n 个数已经排好序了,再对 1 ~ n-1 的数做相同操作,1 ~ n-1 中最大的数会到 n-1 的位置,n-1 ~ n 是排好序的,重复这个 "冒泡" 过程,直到排序(若一次循环中未发生过一次交换可以提前结束排序)。
示意图

如上图所示,5 8 排好序之后,剩下的 1 3 4 进行排序,同样的一次循环后将不会发生交换,说明剩下部分已经有序,此时可以提前结束排序。
代码示例
public class BubbleSort {
public static void sort(int[] arr) {
for (int i = arr.length; i > 1; i--) {
boolean flag = true;
for (int j = 1; j < i; j++) {
if (arr[j-1] > arr[j]) {
swap(arr, j-1, j);
flag = false;
}
}
if (flag) {
break;
}
}
}
}时间复杂度和空间复杂度
冒泡排序在一般情况下,需要进行两层嵌套循环,第一次循环执行 n-1 次,第二次执行 n-2 次...,直到最后大约执行了 (n-1) + (n-2) + ... + 2 + 1 ,同样是等差数列,因此时间复杂度为 $O(n^2)$ 。最差情况下其时间复杂度为 $O(n^2)$ ,而如果程序中做了优化,在未发生交换时提前结束排序,则只需执行一次循环,所以最好情况的时间复杂度是 $O(n)$ 。
由于除了部分临时变量外,没有用到其他额外空间,所以其空间复杂度为 $O(1)$ 。
稳定性
在冒泡排序算法中,相邻两个数进行比较时,相等的数将不会进行交换,因此可以保证相等的数在排序后的顺序不变,是一种稳定的排序算法。
插入排序
插入排序是简单排序中的最后一种,插入排序顾名思义,类似于持有一手乱序的扑克牌,每次从无序的牌中取出一张插入有序的牌中,随着无序的牌组减少,整副牌趋于有序。其基本思路是:假设数组长度为 n ,从第二个数开始,同前一个数进行比较,若小于前一个数则交换,否则停止插入,再从第三个数开始往前面已经有序的部分插入,重复这个步骤,直到最后一个数插入完成,数组有序。
示意图

代码示例
public class InsertSort {
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
swap(arr, j, j-1);
}
}
}
}上面的代码需要每次进行交换,可以稍加改进:
public class InsertSort {
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
int temp = arr[j];
while (j > 0 && temp < arr[j-1]) {
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
}
}时间复杂度和空间复杂度
插入排序算法同样的使用到了嵌套循环,一般情况下整个算法大约执行了 1 + 2 + ... + (n-2) + (n-1) ,同样的时间复杂度是 $O(n^2)$ ,但是插入排序要比冒泡排序少了许多比较和交换的过程,会快得多,而且在比较有序的情况下,所用的时间会比较少,最好的情况下只需循环一次,因此最好时间复杂度为 $O(n)$ 。
同样的插入排序的空间复杂度为 $O(1)$ 。
稳定性
插入排序通过比较相邻元素的大小进行交换,因此同样是稳定的。
总结
三种简单排序算法的时间复杂度都是 $O(n^2)$ ,空间复杂度是 $O(1)$ ,冒泡排序和插入排序和插入排序的最好时间复杂度是 $O(n)$ ,是稳定排序,选择排序的最好时间复杂度是 $O(n^2)$ ,是不稳定排序,同时插入排序要比冒泡排序快一些,因此在数据量小时可以使用简单排序,优先使用插入排序。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论