时间复杂度是O(N²)的排序算法有三个——冒泡排序、选择排序、插入排序
- 冒泡排序
- 基本思想
设待排序数组为arr，长度为n，外层循环i从n-1到0遍历，内层循环j从0到i-1遍历，一旦发现arr[j]>arr[j+1]，则交换arr[j]与arr[j+1]的值；纵观全局，每排序一次，就将最大的数一步一步的交换到最后的位置，看起来就像是冒泡一样。
- 代码实现
public void bubbleSort(int[] arr) {
for(int i = arr.length-1 ; i > 0 ; i --) {
for(int j = 0 ; j < i ; j ++) {
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
- 性能分析
因为有两层循环，因此可以很直观的就可以看出时间复杂度为O(N²)，因为只有交换值的时候使用了额外的变量，因此额外空间复杂度为O(1)。
冒泡排序是稳定的排序算法，冒泡排序的比较是发生在相邻元素之间的，如果有相同大小的元素，在冒泡排序的过程中不会改变他们的相对次序。
2.选择排序
·基本思想
假设待排序数组为arr，长度为n，依然使用两层循环，外层循环i从0到n-1，内层循环j从i到n-1，每一次，从内层循环(即无序区)中找到最小的值，如果最小值不是arr[i]则将最小值与arr[i]交换(因为arr[i]是有序区之后的第一个元素)，继续下一层直到结束。
每次都是从无序区选出最小的值放入到有序区的末尾位置，因此叫选择排序。
·代码实现
public void selectionSort(int[] arr) {
for(int i = 0 ; i < arr.length ; i ++) {
//记录最小值的下标
int minIndex = i;
for(int j = i ; j < arr.length ; j ++) {
if (arr[j]<arr[minIndex]) {
minIndex = j;
}
}
if(minIndex!=i){
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
}
·性能分析
因为有两层循环，因此可以很直观的就可以看出时间复杂度为O(N²)，因为只有在记录最小数据的时候以及交换的时候定义了额外的变量，因此额外空间复杂度为O(1)。
选择排序是不稳定的排序算法，举个例子，如果数组是3,5,3,1,4，第一排序将第一个3与1交换，两个3的相对次序就变化了，因此是不稳定的。
3.插入排序
·基本思想
假设待排序数组是arr，长度为n，依然使用两层循环，外层循环i从0到n-1，内层循环j从i到1，当发现arr[j]<arr[j-1]的时候，就交换arr[j]与arr[j-1]的值，接下来进行下一层循环，直到结束。
每次都是选出无序区的第一个元素与之前的元素作比较，然后调整无序区第一个元素在有序区的位置，直到找到合适的位置则有序区又变成有序的，就像玩扑克牌一样，将无序的元素插入到合适的位置，因此叫插入排序。
·代码实现
public void insertionSort(int[] arr) {
for(int i = 0 ; i < arr.length ; i ++) {
for(int j = i ; j > 0 ; j --) {
//如果无序区第一个值小于前一个值，则交换
if (arr[j]<arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
·性能分析
因为有两层循环，因此可以很直观的就可以看出时间复杂度为O(N²)，因为只有在交换元素位置的时候定义了额外的变量，因此额外空间复杂度为O(1)。
插入排序是稳定的排序算法，每次是相邻元素的交换，如果有序区内遇到了相同的元素，则就不需要再进行交换了，相对次序没有改变，因此是稳定的。