1 冒泡排序
冒泡排序的0（N2）的复杂度中，外层的循环表示有n个数要排，内层从0开始到n-1才是左右交换的实现，造个名字：相邻比较互换法。
代码如下：
- <span style="font-size:14px;">//冒泡排序
- public void bubbleSort(T[] t,Comparator<T> c){
- for(int i=0;i<t.length;i++){//有length-1个元素要移动
- for(int j=0;j<t.length-i-1;j++){//从开始位置往后扫描
- if(c.compare(t[j], t[j+1])>0){//如果发现前面元素比后面大
- T temp=t[j];t[j]=t[j+1];t[j+1]=temp;//就互换
- }
- }
- }
- }</span>
2 选择排序
选择排序的0（N2）的复杂度中，外层的循环找到那个当成最小值的坑保存下标，内层从i+1开始到n-1依次与最小值比较，找到小的就更新之前的下标：
代码如下：
- <span style="font-size:14px;">//选择排序
- public void selectionSort(T[] t,Comparator<T> c){
- for(int i=0;i<t.length;i++){//确定位置当成最小值存放点
- int k=i;
- for(int j=i+1;j<t.length;j++){//从开始位置往后扫描
- if(c.compare(t[k], t[j])>0){//发现小值就记录下标
- k = j;
- }
- }
- T temp=t[i];t[i]=t[k];t[k]=temp;//存放入最小值
- }
- }</span>
3 插入排序
插入排序里貌似有个很好的启发点就是在计算机的世界里，最小规模对于条件总是成立的，比如这里当元素个数只有1的时候就是可以看成有序的。
这个在归并、快速排序、硬币问题中等都有应用，类似数学归纳法。
插入排序外层循环确定前i个元素的有序数组，内层从i+1开始到0，依次比较i+1位置的元素与前面的元素，大就插入位置，小就前面的元素往后挪一位。小心的地方是循环可能一直做到0的位置都在往后挪，最后没有把i+1位置的元素插入在0处。复杂度也是平方阶。
代码如下：
- <span style="font-size:14px;">//插入排序
- public void insertionSort(T[] t,Comparator<T> c){
- for(int i=1;i<t.length;i++){//确定有序序列
- T temp = t[i];//空出位置
- for(int j=i-1;j>=0;j--){//往前依次查找
- if(c.compare(temp, t[j])<0){
- t[j+1] = t[j];//前面的值大就往后移一位
- }else{
- t[j+1] = temp;//前面的值等于或者小于就插入
- break;
- }
- if(j==0){//循环到头了
- t[0] = temp;
- }
- }
- }
- }</span>
4 shell 排序
插入排序外层套了个循环，不是每次间隔1互换减小逆序，间隔从array.length/2一直到1，快速消除逆序。找了些书讲到每次除以2.2效率是最好的，因此最外层循环迭代条件应该是 i==2 ? 1: (int)(i/2.2),效率是大概n的1.5次方阶。内层循环的原理和插入排序一模一样。
代码如下：
- <span style="font-size:14px;">//希尔排序:思路类似插入排序
- public void shellSort(T[] t,Comparator<T> c){
- //除以2.2分割貌似是最佳的，最后分割必须为1
- for(int gap=t.length/2;gap>0;gap=(gap==2? 1
int)(gap/2.2))){//加了个分割循环 - for(int i=gap;i<t.length;i+=gap){
- T temp = t[i];//当前的为坑
- for(int j=i-gap;j>=0;j-=gap){//0到i每个都比较，大的往后坑里填，小的就填值
- if(c.compare(t[j], temp)>0){
- t[j+gap]=t[j];
- }else{
- t[j+gap]=temp;
- break;
- }
- if(j==0){//循环到头了
- t[0] = temp;
- }
- }
- }
- }
- }</span>
后续见 各种排序算法（2）