排序算法总结[2]

标签（逗号分隔）： 排序、算法、Java

---

一、冒泡排序

冒泡排序是最简单的排序算法了，基本思路是：相邻元素两两比较，每次得出一个最大（最小）的冒出即可

• 时间复杂度：
  平均和最坏是：O(N^2)
  最好是：O(N)---算法需要改进，记录每次要不要交换即可
• 空间复杂度：O(1)
• 稳定性：稳定
• 冒泡排序效率极其低下，在数据量很小的时候拿来玩玩还可以

void bubbleSort(int[] arr]){    if(arr==null)throw new NullPointerException();    if(arr.length<2)return;    boolean didSwap;    for(int i=arr.length-1;i>0;--i){        didSwap=false;        for(int j=0;j
    
     arr[j+1]){                int tmp=arr[j];                arrr[j]=arr[j+1];                arr[j+1]=arr[j]; //避免函数调用以提高效率                didSwap=true;            }        }        if(didSwap==false)return;//不需要再比较了    }}
    

二、插入排序

在数据量不大的时候可以使用插入排序，基本思路是：将数组看做已排序区域和未排序区域，每次从未排序区域取一个数据插入排序区域的正确位置即可。

• 时间复杂度：
  最坏和平均：O(N^2)
  最好是：O(N)，输入是排序的数据，每次只需和前一个元素比较即可
• 空间复杂度：O(1)
• 稳定性：稳定
• 使用：在优化快排的一种策略中，就是选择在数据量较小(n<10)时使用插入排序来完成即可。**

void insertSort(int[] arr){    if(arr==null)throw new NullPointerException();    if(arr.length<=1)return;    for(int i=1;i
    
     0 && arr[j-1]>tmp;--j){            arr[j]=arr[j-1]; //插入到前面正确的位置上        }        arr[j]=tmp;    }}
    

三、希尔排序

希尔排序又称为缩小增量排序，基本思路：选定一个由大到小的增量序列，每次以一个增量为基准使用直接插入排序。

根据选定的增量序列，时间复杂度可能会不同:

参考：《数据结构与算法分析_C语言描述》 P170 作者：Mark Allen Weiss

• Hibbard序列的最坏时间复杂度是：O(N^(3/2))
• Sedgwick提出了其他的序列，最坏可以达到O(N^(4/3))
  下面是一个参考代码：