为什么要学习时间复杂度为O（n² ）？
3.在一些特殊情况下，简单的排序算法更有效
4.简单的排序算法思想衍生出复杂的排序算法
1.选择排序
选择排序，就是每一次都筛选出最小（或最大）的数字，然后放在每一次排序的第几个位置。
比如第一次排序，找出最小（或最大）的元素，放在第一个位置，第二次排序，找出最小（或最大）的元素，放在第二个位置.....
顺序从小到大排序：
首先选出最小元素：“1”
然后将这个“1”和第一个位置进行交换：
此时的“1”是在最终位置了，可以不去理会了。
接着找出剩余还没排序的最小元素：“2”
跟第二个位置进行交换：
以此类推进行排序，这种排序就是选择排序了。
public class SelectionSort { public static void swap(Object[]arr , int i , int j){
Object obj = arr[i];
arr[i] = arr[j];
arr[j] = obj;
}
public static void sort_asc(Comparable[] arr){
int n = arr.length -1;
for( int i = 0 ; i <= n ; i++ ){
for( int j = i+1 ; j <= n ; j++ ){
if( arr[j].compareTo(arr[i]) < 0 ){
swap(arr,i,j);
}
}
}
}
public static void main(String[] args) {
Integer [] arr = {10,3,5,2,4,1,8,6,7,9};
sort_asc(arr);
for( int i : arr ){
System.out.print(i + " ");
}
}
}
2.插入排序
插入排序，从前（或往后），第n次排序，则对n个元素进行排序。
例如第一次排序，对于“8”来说，已经排序完毕了。
第二次排序，对于“6”来说，要放到前面合适的位置。
比“8”还要小，放在前面的位置。
第三次排序，对于“2”来说，要放在前面3个元素合适的位置。
“2”比“8”小。
“2”比“6”小，继续交换一次位置。
进行多次的数据交换。
这样前面3个元素就排序完成了。以此类推排序完成......
public class InsertionSort { public static void swap(Object[]arr , int i , int j){ Object obj = arr[i]; arr[i] = arr[j]; arr[j] = obj; } public static void sort_asc(Comparable[]arr){ int n = arr.length - 1; for( int i = 1 ; i <= n ; i++ ) { //寻找元素arr[i]适合插入的位置 for( int j = i ; j > 0 ; j--) { if( arr[j].compareTo(arr[j-1]) < 0 ) { swap(arr,j,j-1); } else { //如果不小于，则已排序完成，可以跳出当前循环，进行下一个循环 break; } } } } public static void main(String[] args) { Integer [] arr = {10,3,5,2,4,1,8,6,7,9}; sort_asc(arr); for( int i : arr ){ System.out.print(i + " "); } }}
对于比较插入排序和选择排序。
在插入排序中：
public static void InsertSort(Comparable[]arr){ int n = arr.length - 1; for( int i = 1 ; i <= n ; i++ ) { //寻找元素arr[i]适合插入的位置 for( int j = i ; j > 0 ; j--) { if( arr[j].compareTo(arr[j-1]) < 0 ) { swap(arr,j,j-1); } else { //如果不小于，则已排序完成，可以跳出当前循环，进行下一个循环 break; } } } }
有一个break操作，能够节省一些时间。
所以理应来说比较于“选择排序”来说，要快的很多。
但是其实不然，选择排序只是每一次进行一次数据的交换操作（swap）。
而插入排序在每一次的排序中要进行多次的数据交换操作（swap里面有3次赋值的操作），所以对于一个break语句来说，其实并没有快的多少。
所以能不能改变一下算法，让插入排序也能只进行一次数据交换呢？答案是完全可以的
改进的插入排序：
第一次排序“8”还是在那里：
在第二次排序，“6”的位置的时候，不像之前那样冒然交换了。
而是先把“6”复制一份，保存起来。
然后看“6”是否合适放在当前位置。
那么判断是否合适放在当前位置，比较这两位数的大小，“6”比“8”小，所以不能放在当前位置。
所以把“8”向后移动一个位置，直接在当前位置进行赋值，而不是交换：
然后再来考察“6”，是否能放在前一个位置：
此时的位置是第一个，所以不用比较了：
接下来看”2“，直接复制一个副本：
因为 “2” 比前面 “8”小，所以“2”不能放在这个位置，此时“8”赋值到“2”这个位置：
然后再次判断 “2”是不是应该放在之前“8”这个位置，跟前面的“6”比较，不是：
所以把“6”赋值到这个位置：
然后再来看 “2”是不是应该放在原来 “6”放的位置：
因为是第0个位置：所以直接赋值就好了：
依次类推，不用一次排序进行多次数据的交换，而是变成数据的赋值操作。
代码如下：
public static void changeSort(Integer [] arr){ for( int i = 1 ; i < arr.length ; i++ ){ //寻找元素arr[i]适合的插入位置 int temp = arr[i]; //j保存元素temp应该插入的位置 int j; for( j = i ; j > 0 && arr[j-1] > temp ; j-- ){ arr[j] = arr[j-1]; } arr[j] = temp; } }
4.冒泡排序
顾名思义：像冒泡泡一样上升。
对于一个数组，有n个元素。
第一轮排序下来，把最大（或最小）的数据给筛选出来，放在数组的最右（或最左），
然后进行第二轮排序，找出第二大（或次小）的数据，放在数组的[n-2](或[1]),
....
依次类推，进行第n轮排序，数据便以排序完成。
所以冒泡排序需要两个循环:
public class BubbleSort { public static void swap(Object[]arr , int i , int j){ Object obj = arr[i]; arr[i] = arr[j]; arr[j] = obj; } public static void sort_asc(Comparable[]arr){ for(int i = arr.length-1 ; i >= 0 ; i-- ){ for( int j = i-1 ; j >= 0 ; j-- ){ if(arr[i].compareTo(arr[j]) < 0){ swap(arr,i,j); } } } } public static void main(String[] args) { Integer [] arr = {10,3,5,2,4,1,8,6,7,9}; sort_asc(arr); for( int i : arr ){ System.out.print(i + " "); } }}