插入排序的基本思想：每步将一个待排序元素，按其排序码大小插入到前面已经排好序的一组元素中，直到元素全部插入为止。在这里，我们介绍三种具体的插入排序算法：直接插入排序，希尔排序与折半插入排序。

1、直接插入排序

**直接插入排序的思想：**当插入第i(i>=1)个元素时，前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时，将第i个元素与前i-1个元素V[i-1]，…，V[0]依次比较，找到插入位置即将V[i]插入，同时原来位置上的元素向后顺移。在这里，插入位置的查找是顺序查找。直接插入排序是一种稳定的排序算法，其实现如下：

/***Title:插入排序中的直接插入排序，依赖于初始序列*Description:在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的*时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)*空间复杂度：O(1)*稳定性：稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月20日上午10:40:00*/publicclassStraightInsertionSort{publicstaticint[]insertSort(int[]target){if(target!=null&&target.length!=1){//待排序数组不为空且长度大于1for(inti=1;ifor(intj=i;j>0;j--){//向有序序列中插入新的元素if(target[j]returntarget;}}

2、希尔排序

**希尔排序的思想：**设待排序序列共n个元素，首先取一个整数gap

/***Title:插入排序中的希尔排序，依赖于初始序列*Description:分别对间隔为gap的gap个子序列进行直接插入排序，不断缩小gap,直至为1**刚开始时，gap较大，每个子序列元素较少，排序速度较快；*待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。**时间复杂度：O(n)~O(n^2)*空间复杂度：O(1)*稳定性：不稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月20日上午10:40:00*/publicclassShellSort{publicstaticint[]shellSort(int[]target){if(target!=null&&target.length!=1){intgap=target.length;//gap个大小为gap的子序列do{gap=gap/3+1;//不断缩小gap直至为1for(inti=0+gap;iif(target[i]do{target[j+gap]=target[j];//后移元素j=j-gap;//再比较前一个元素}while(j>=0&&target[j]>temp);//向前比较的终止条件target[j+gap]=temp;//将待插入值插入合适的位置}}}while(gap>1);}returntarget;}}

3、折半插入排序

**折半插入排序的思想：**当插入第i(i>=1)个元素时，前面的V[0],…,V[i-1]等i-1个 元素已经有序。这时，折半搜索第i个元素在前i-1个元素V[i-1]，…，V[0]中的插入位置，然后直接将V[i]插入，同时原来位置上的元素向后顺移。与直接插入排序不同的是，折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），但其减少了比较次数，所以该算法仍然比直接插入排序好。折半插入排序是一种稳定的排序算法，其实现如下：

/***Title:插入排序中的折半插入排序，依赖于初始序列*Description:折半搜索出插入位置，并直接插入;与直接插入搜索的区别是，后者的搜索要快于顺序搜索*时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，*折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。*空间复杂度：O(1)*稳定性：稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月25日下午12:03:23*/publicclassBinaryInsertSort{publicstaticint[]binaryInsertSort(int[]target){if(target!=null&&target.length>1){for(inti=1;iif(tempwhile(leftif(target[mid]elseif(target[mid]>temp){right=mid-1;//缩小插入区间}else{//待插入值与有序序列中的target[mid]相等，保证稳定性的处理left=left+1;}}//left及其后面的数据顺序向后移动，并在left位置插入for(intj=i;j>left;j--){target[j]=target[j-1];}target[left]=temp;}}}returntarget;}}选择排序

**选择排序的基本思想：**每一趟 (例如第i趟，i = 0,1,…)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素，直到第n-1趟结束后，所有元素有序。在这里，我们介绍两种具体的选择排序算法：直接选择排序与堆排序。

1、直接选择排序

**直接选择排序的思想：**第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R1~R[n-1]中选取最小值，与R1交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳定的排序算法，其实现如下：

/***Title:选择排序中的直接选择排序，依赖于初始序列*Description:每一趟(例如第i趟，i=0,1,...)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素*时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)*空间复杂度：O(1)*稳定性：不稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月20日上午10:40:00*/publicclassStraightSelectSort{publicstaticint[]selectSort(int[]target){if(target!=null&&target.length!=1){for(inti=0;ifor(intj=i+1;jif(target[min_index]>target[j]){min_index=j;}}if(target[min_index]!=target[i]){//导致不稳定的因素：交换intmin=target[min_index];target[min_index]=target[i];target[i]=min;}}}returntarget;}}

2、堆排序

**堆排序的核心是堆调整算法。**首先根据初始输入数据，利用堆调整算法shiftDown()形成初始堆；然后，将堆顶元素与堆尾元素交换，缩小堆的范围并重新调整为堆，如此往复。堆排序是一种不稳定的排序算法，其实现如下：

/***Title:堆排序(选择排序)，升序排序(最大堆)，依赖于初始序列*Description:现将给定序列调整为最大堆，然后每次将堆顶元素与堆尾元素交换并缩小堆的范围，直到将堆缩小至1*时间复杂度：O(nlgn)*空间复杂度：O(1)*稳定性：不稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月25日上午9:48:06*/publicclassHeapSort{publicstaticint[]heapSort(int[]target){if(target!=null&&target.length>1){//调整为最大堆intpos=(target.length-2)/2;while(pos>=0){shiftDown(target,pos,target.length-1);pos--;}//堆排序for(inti=target.length-1;i>0;i--){inttemp=target[i];target[i]=target[0];target[0]=temp;shiftDown(target,0,i-1);}returntarget;}returntarget;}/***@description自上而下调整为最大堆*@authorrico*@created2017年5月25日上午9:45:40*@paramtarget*@paramstart*@paramend*/privatestaticvoidshiftDown(int[]target,intstart,intend){inti=start;intj=2*start+1;inttemp=target[i];while(jif(jtarget[j]){//找出较大子女j=j+1;}if(target[j]break;}else{target[i]=target[j];i=j;j=2*j+1;}}target[i]=temp;}}交换排序

**交换排序的基本思想：**根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，也就是说，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1、冒泡排序

**冒泡排序的思想：**根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排序是一种稳定的排序算法，其实现如下：

/***Title:交换排序中的冒泡排序，一般情形下指的是优化后的冒泡排序，最多进行n-1次比较，依赖于初始序列*Description:因为越大的元素会经由交换慢慢"浮"到数列的顶端(最后位置)，最大的数最后才确定下来，所以称为冒泡排序*时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)*空间复杂度：O(1)*稳定性：稳定*内部排序(在排序过程中数据元素完全在内存)**@authorrico*@created2017年5月20日上午10:40:00*/publicclassBubbleSort{/***@description朴素冒泡排序(共进行n-1次比较)*@authorrico*/publicstaticint[]bubbleSort(int[]target){intn=target.length;if(target!=null&&n!=1){//最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡for(inti=0;ifor(intj=n-1;j>i;j--){if(target[j]returntarget;}/***@description优化冒泡排序*@authorrico*/publicstaticint[]optimizeBubbleSort(int[]target){intn=target.length;if(target!=null&&n!=1){//最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡for(inti=0;ifalse;for(intj=n-1;j>i;j--){if(target[j]true;}}System.out.println(Arrays.toString(target));if(!exchange){//若i到n-1这部分元素已经有序，则直接返回returntarget;}}}returntarget;}}

2、快速排序

**快速排序的思想：**通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法。

/***Title:交换排序中的快速排序，目前应用最为广泛的排序算法，是一个递归算法，依赖于初始序列*Description:快速排序包括两个过程：划分和快排*"划分"是指将原序列按基准元素划分两个子序列*"快排"是指分别对子序列进行快排**就平均计算时间而言，快速排序是所有内部排序方法中最好的一个**对大规模数据排序时，快排是快的；对小规模数据排序时，快排是慢的，甚至慢于简单选择排序等简单排序方法**快速排序依赖于原始序列，因此其时间复杂度从O(nlgn)到O(n^2)不等*时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)**递归所消耗的栈空间*空间复杂度：O(lgn)**可选任一元素作为基准元素*稳定性：不稳定***内部排序(在排序过程中数据元素完全在内存)**@authorrico*@created2017年5月20日上午10:40:00*/publicclassQuickSort{/***@description快排算法(递归算法)：在递去过程中就把问题解决了*@authorrico*@created2017年5月20日下午5:12:06*@paramtarget*@paramleft*@paramright*@return*/publicstaticint[]quickSort(int[]target,intleft,intright){if(right>left){//递归终止条件intbase_index=partition(target,left,right);//原序列划分后基准元素的位置quickSort(target,left,base_index-1);//对第一个子序列快速排序，不包含基准元素！quickSort(target,base_index+1,right);//对第二个子序列快速排序，不包含基准元素！returntarget;}returntarget;}/***@description序列划分，以第一个元素为基准元素*@authorrico*@created2017年5月20日下午5:10:54*@paramtarget序列*@paramleft序列左端*@paramright序列右端*@return*/publicstaticintpartition(int[]target,intleft,intright){intbase=target[left];//基准元素的值intbase_index=left;//基准元素最终应该在的位置for(inti=left+1;iif(target[i]if(base_index!=i){//相等情况意味着i之前的元素都小于base,只需要换一次即可，不需要次次都换inttemp=target[base_index];target[base_index]=target[i];target[i]=temp;}}}//将基准元素就位target[left]=target[base_index];target[base_index]=base;System.out.println(Arrays.toString(target));returnbase_index;//返回划分后基准元素的位置}}归并排序

**归并排序包含两个过程：”归”和”并”。**其中，”归”是指将原序列分成半子序列，分别对子序列进行递归排序；”并”是指将排好序的各子序列合并成原序列。归并排序算法是一个典型的递归算法，因此也是概念上最为简单的排序算法。与快速排序算法相比，归并排序算法不依赖于初始序列，并且是一种稳定的排序算法，但需要与原序列一样大小的辅助存储空间。

/***Title:归并排序，概念上最为简单的排序算法，是一个递归算法，不依赖于初始序列*Description:归并排序包括两个过程：归和并*"归"是指将原序列分成半子序列，分别对子序列进行递归排序*"并"是指将排好序的各子序列合并成原序列**归并排序的主要问题是：需要一个与原待排序数组一样大的辅助数组空间**归并排序不依赖于原始序列，因此其最好情形、平均情形和最差情形时间复杂度都一样*时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)*空间复杂度：O(n)*稳定性：稳定*内部排序(在排序过程中数据元素完全在内存)**@authorrico*@created2017年5月20日上午10:40:00*/publicclassMergeSort{/***@description归并排序算法(递归算法)：递去分解，归来合并*@authorrico*@created2017年5月20日下午4:04:52*@paramtarget待排序序列*@paramleft待排序序列起始位置*@paramright待排序序列终止位置*@return*/publicstaticint[]mergeSort(int[]target,intleft,intright){if(right>left){//递归终止条件intmid=(left+right)/2;mergeSort(target,left,mid);//归并排序第一个子序列mergeSort(target,mid+1,right);//归并排序第二个子序列returnmerge(target,left,mid,right);//合并子序列成原序列}returntarget;}/***@description两路归并算法*@authorrico*@created2017年5月20日下午3:59:16*@paramtarget用于存储归并结果*@paramleft第一个有序表的第一个元素所在位置*@parammid第一个有序表的最后一个元素所在位置*@paramright第二个有序表的最后一个元素所在位置*@return*/publicstaticint[]merge(int[]target,intleft,intmid,intright){//需要一个与原待排序数组一样大的辅助数组空间int[]temp=Arrays.copyOf(target,target.length);//s1,s2是检查指针，index是存放指针ints1=left;ints2=mid+1;intindex=left;//两个表都未检查完，两两比较while(s1if(temp[s1]else{target[index++]=temp[s2++];}}//若第一个表未检查完，复制while(s1while(s2returntarget;}}

Ps : 归并排序和快速排序都是典型的递归算法，因此它们比较容易理解和实现。关于递归思想和内涵深度剖析，请见博文《算法设计方法：递归的内涵与经典应用》。

分配排序的基本思想：用空间换时间。在整个排序过程中，无须比较关键字，而是通过用额外的空间来”分配”和”收集”来实现排序，它们的时间复杂度可达到线性阶：O(n)。其中，基数排序包括两个过程：首先，将目标序列各元素分配到各个桶中(分配过程)；然后，将各个桶中的元素按先进先出的顺序再放回去(收集过程)，如此往复，一共需要进行d趟，d为元素的位数。

/***Title:分配排序中的基数排序，不依赖于初始序列*Description:不是在对元素进行比较的基础上进行排序，而是采用"分配+收集"的办法**首先，将目标序列各元素分配到各个桶中；*其次，将各个桶中的元素按先进先出的顺序再放回去*如此往复...**时间复杂度：O(d*(r+n))或者O(dn),d的大小一般会受到n的影响*空间复杂度：O(rd+n)或者O(n)*稳定性：稳定*内部排序(在排序过程中数据元素完全在内存)*@authorrico*@created2017年5月20日上午10:40:00*/publicclassRadixSort{/***@description分配+收集*@authorrico*@created2017年5月21日下午9:25:52*@paramtarget待排序数组*@paramr基数*@paramd元素的位数*@paramn待排序元素个数*@return*/publicstaticint[]radixSort(int[]target,intr,intd,intn){if(target!=null&&target.length!=1){int[][]bucket=newint[r][n];//一共有基数r个桶，每个桶最多放n个元素intdigit;//获取元素对应位上的数字，即装入那个桶intdivisor=1;//定义每一轮的除数，1,10,100,...int[]count=newint[r];//统计每个桶中实际存放元素的个数for(inti=0;ifor(intele:target){digit=(ele/divisor)%10;//获取元素对应位上的数字(巧妙！！！)bucket[digit][count[digit]++]=ele;//将元素放入对应桶，桶中元素数目加1}//收集intindex=0;//目标数组的下标for(intj=0;jwhile(kreturntarget;}}总结

1、直接插入排序 Vs. 折半插入排序 Vs. 希尔排序

这三种排序方法都属于插入排序的范畴。与直接插入排序的顺序搜索插入位置相比，折半插入排序通过折半搜索的方法搜索插入位置，因此，在搜索插入位置方面，折半插入排序要快于直接插入排序。实际上，折半插入排序比直接插入排序只是减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（n^2），但减少了比较次数，所以该算法要比直接插入排序好一点。希尔排序可以看作是对直接插入排序的一种优化，它将全部元素分为间隔为gap的gap个子序列并对每一个子序列进行直接插入排序，同时不断缩小间隔gap，直至所有元素位于同一个序列。使用这种方式可以保证排序效率，因为刚开始时，gap较大，每个子序列元素较少，排序速度较快；待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。因此，希尔排序比直接插入排序 、折半插入排序都要高效，但它不是稳定的。

2、直接选择排序 Vs. 堆排序

这两种排序方法都属于插入选择排序的范畴，它们的核心思想都是每一趟都选择一个极值元素放在靠前/靠后位置，直到序列有序。与直接选择排序不同的是，堆排序不是“蛮力选择”，而是不断进行堆调整以取得每趟中的极值。因此，堆排序比直接选择排序要高效，不过它们都是不稳定的。

3、冒泡排序 Vs. 快速排序

这两种排序方法都属于选择排序的范畴，它们的核心思想都是元素的交换，冒泡排序中每一趟相邻元素互相比较，并将较小的交换到前面(较大的自然沉到后面)位置，快速排序则是以基准点为基础，将比它小的元素和比它大的元素分别交换到它的两边。因此，快速排序比冒泡排序要高效，但它不是稳定的。

4、归并排序 Vs. 快速排序

这两种排序方法都属于递归算法的范畴，因此，它们都比较容易让人理解和实现。与快速排序相比，归并排序不但是稳定的，还是与原始序列无关的(不依赖于原始序列的顺序，时间复杂度总是O(nlgn))，但是需要与原始序列一样大小的空间；而快速排序则一般情况下都要比其他高效排序算法（包括归并排序）快，而且空间复杂度只为O(1)。另外，我们从算法实现中可以看出这两种递归算法有以下区别和联系：

5、小结

直接插入排序、直接选择排序和冒泡排序是基本的排序方法，它们平均情况下的时间复杂度都是O(n^2)，实现也比较简单，它们对规模较小的元素序列很有效。

快速排序、堆排序和归并排序是高效的排序方法，它们平均情况下的时间复杂度都是O(nlgn)，其中快速排序是最通用的高效排序算法，但其是不稳定的；归并排序是上述几种排序算法中唯一与初始序列无关的，而且时间复杂度总是O(nlgn)，但其空间复杂度是O(n)，是一种稳定的排序算法；堆排序的时间复杂度总是O(nlgn)，空间复杂度是O(1)，也是不稳定的。它们对规模较大的元素序列很有效。

希尔排序的效率介于基本排序方法与高效排序方法之间，是一种不稳定的排序算法。它们各有所长，都拥有特定的使用场景。基数排序虽然具有线性增长的时间复杂度，但实际上开销并不比快速排序小很多，应用相对不太广泛。

因此，在实际应用中，我们必须根据实际任务的特点和各种排序算法的特性来做出最合适的选择。