1.选择排序
看算法书才知道还有一种排序叫选择排序，还是经典排序，果然是算法渣渣，还孤陋寡闻，皮皮甜要加油啊
什么是选择排序呢，首先找到数组中最小的元素，其次，将它和数组中的第一个元素交换位置(如果第一个元素最小，自己和自己交换)，其次，在剩下的元素中找到最小元素和第二个位置的元素进行排序，依此类推
Example:
ChooseSort.java
public class ChooseSort {
public static void main(String[] args) {
int[] a = {1, 5, 7, 9, 2 , 4, 6, 8};
System.out.println("排序前:" + Arrays.toString(a));
//1.外层循环做交换
//2.内存循环找到剩余数组中的最小值
for (int i = 0; i < a.length; i++) {
int k = i; //k元素记录最小元素的位置
for (int j = k + 1; j < a.length; j++) {
if (a[j] < a[k]) {
k = j;
}
}
//如果刚好在正确的位置上，则不进行排序
if (k != i) {
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
System.out.println("排序后:" + Arrays.toString(a));
}
}
时间复杂度为o(n^2)
2.冒泡排序
冒泡排序可能是我唯一知道的排序算法了，就这么差劲。
BubbleSort.java
public class BubbleSort {
public static void main(String[] args) {
int[] a = {1, 3, 5, 7, 9, 2, 4, 6, 8};
System.out.println("排序前: " + Arrays.toString(a));
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] > a[j]) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
System.out.println("排序前: " + Arrays.toString(a));
}
}
冒泡排序每次找到一个比外层位置小的元素就做一次交换，假设外层循环为i，内层循环为j，则每次做交换的次数为i-j次，时间复杂度为o(n^2)
那么冒泡排序和选择排序有什么区别呢，虽然时间复杂度都为o(n^2)，但是选择排序的性能要优于冒泡排序，因为选择排序的时间效率取决于比较的次数，如果有序的话，它将非常快，而冒泡排序每次循环一定是要进行i-j次的交换的
随机生成10000个数字初始化数组，costTime总不为0了，
测试结果：
BubbleSort costTime: 214
ChooseSort costTime: 82
乱序的情况下，选择排序的性能要远优于冒泡排序。因为这时候冒泡要做很多次交换
而在有序情况下：
BubbleSort costTime:1631
ChooseSort costTime: 1758
选择排序花费时间略微长于冒泡排序。在有序情况下，冒泡不用做一次交换，而选择仍要做n次交换，这些时间差应该是交换所花时间
但是有序情况下做了几次测试，有时候选择排序的时间要少于冒泡排序，搞不懂，反正理论上应该是冒泡排序会快一些
3.插入排序
public class InsertSort {
public static void main(String[] args) {
int[] a = {1, 3, 5, 2, 4};
insertionSort(a);
System.out.println(Arrays.toString(a));
}
public static void insertionSort(int[] a){
int key,n=a.length;
for(int i = 1; i < n; i++){
key = a[i];
int j = i - 1;
for (; j >= 0; j--) {
if (a[j] > key) {
a[j + 1] = a[j];
} else {
break;
}
}
a[j + 1] = key;
}
}
}
插入排序和冒泡排序还有选择排序最大的区别在于它不是通过交换实现的，而是通过移动来实现的，最左边总是有序的，找到要插入元素的位置，该位置的元素向右移动一个位置。时间复杂度为o(n^2)
网友评论