爱站程序员基地算法的本质
最近一直在想，算法的本质到底是什么，为什么有时云里雾里，有时却了然可见，深深思考了下，算法本质就是一个解决问题的思想，计算机的世界里需要的就是抽象的思想，有了抽象思想，你就有了高度，原谅我突然的。
冒泡、选择、插入排序的本质
常见的平均时间复度为O(n²)的冒泡，选择，插入排序算法的本质是什么，说白了就是一个交换位置思想，以及什么时候交换位置，怎么交换位置。先贴一下交换位置的代码，一会要用：
public static void swap(int[] arr,int i,int j) {
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] – arr[j];
arr[i] = arr[i] – arr[j];
}
简单的把一个数组的两个位置的值交换一下，数组也传进来了，交换有效。
冒泡排序
冒泡排序，就是最大的数字或最小的数字经过比较大小并交换位置后从数组中冒出来，冒到数组最左端或最右端。
假如有一个数组：8，9，6，7，5，我们将他们冒一个泡泡，按照我们的抽象思想，开启循环，然后冒泡。第一次冒泡只要把9冒出到数组最右端，9已经是最大的泡泡了。第二次冒泡，可以直接忽略9了，只要把8冒出到数组的最右端(这里是指忽略9的情况)，直到循环结束。贴一段言简意赅的代码：
public static void sort(int[] arr) {
int length = arr.length;
for(int i=length-1;i>0;i–) {
for(int j=0;j<i;j++) {
if(arr[j]>arr[j+1]) {
swap(arr,j,j+1);
}
}
}
}
我们需要两次循环依次把最大的数从数组中冒出去，如果左边的数值大于相邻的右边的数值，就将两个位置的数值进行交换。
选择排序
选择排序可以看作是一个冒泡排序的变种，选择排序先从数组中选择一个基准值作为最小值或最大值，然后再和剩下的数组元素逐一比较，循环找到最小的数组下标，然后交换最小值与基准位置的数值。
还是数组：8，9，6，7，5，基准值默认选择外部循环的第一个元素，第一次选择8为基准值，这里的基准值被当作最小值对待，内部循环剩下的数组元素，经过一轮比较，不断调整最小值的下标，找到最小数值的元素下标，然后将最小值与基准值交换。贴一段言简意赅的代码，貌似和冒泡排序变化不大：
public static void sort(int[] arr) {
int length = arr.length;
int minIndex;
boolean swapFlag;
for(int i=0;i<length;i++) {
minIndex = i;
swapFlag = false;
for(int j=i+1;j<length;j++) {
if(arr[j]<arr[minIndex]) {
minIndex = j;
swapFlag = true;
}
}
if(swapFlag) {
swap(arr,i,minIndex);
}
}
}
选择排序每次记录下最小元素数值下标，然后与基准值交换位置，如果基准值已经是最小值，就不会再进行交换操作，交换次数明显小于冒泡排序，数据集较大时，选择排序要优于冒泡排序。
插入排序
插入排序同样可以看作是冒泡排序的一个变种，插入排序同样选择一个基准值，一般外部循环循环的当前下标元素8000为基准值，插入排序就是要将基准值左边的子数组排好序，在内部循环内，从数组下标0开始到基准下标比较大小并交换位置，直到把基准位置左边子数组排好序，最终外部循环结束。
还是数组：8，9，6，7，5，第一次选择下标1即元素9作为基准下标，然后从数组起始下标开始到基准下标开始比较对应元素数值大小，8小于9不需要交换位置，第二次选择6为基准下标，再次从数组起始下标到基准下标比较数值大小，6和8交换位置，9和8交换位置，数组变为：6，8，9，7，5。说是插入排序，其实还是保证局部排序，然后不断用外部元素与已排序子数组循环比较，将外部元素交换到排序子数组中。
public static void sort(int[] arr) {
int length = arr.length;
int baseIndex;
for(int i=1;i<length;i++) {
baseIndex = i;
for(int j=0;j<i;j++) {
if(arr[j]>arr[baseIndex]) {
swap(arr,j,baseIndex);
}
}
}
}
简单排序总结
以上三种排序算法是最简单排序，平均时间复杂度均为O(n²)，因为都需要两次循环，只是交换规则略不相同，实现方式都是先将数组局部排序然后直到数组全部排序。
