星球狂想战队|是准备家里蹲吗，还不会十大排序 voidsort(){//修剪枝叶的优化方法//基

文章图片

文章图片
voidsort(){//修剪枝叶的优化方法//基于原理：//每一趟完整的循环就对完成一个最大值或者最小值的放置//那每一趟都可以删去枝叶，也就是最大值或者最小值的位置//i的大小也同样可以确定已经完成排序的数值的个数for(inti=0;i<array.length;i++){for(intj=0;j<array.length-i-1;j++){if(array[j]>array[j+1]){swap(array[j],array[j+1]);}}}}代码的效果正好和图片相反，其实冒泡排序作为最简单的排序方法之一，基于的是一个这样的概念：两两交换，比较双方数值大的放在高位，数值小的则放在低位。
而暴力双重循环，就是他的实现方式。每一次都将最大的一位数放到了最后一位，或者反之，将最小的数放到了第一位。

文章图片
staticvoidsort(intleft,intright){if(left<right){//通过split已经完成了左右分割，左边数一定小于中线，右边数一定大于中线intmid=split(left,right);//对左右分区再以中线划分sort(mid+1,right);sort(left,mid-1);}}staticintsplit(intleft,intright){//以当前范围数组的第一个值作为中线inttemp=array[left];while(left<right){//右指针出现了一个数比中线小，则与中线进行交换while(left<right&&temp<array[right])right--;array[left]=array[right];//左指针出现了一个数比中线大，则与中线进行交换while(left<right&&temp>array[left])left++;array[right]=array[left];}//此时left==right ，并无所谓是谁来进行交换array[left]=temp;returnleft;}快速排序其实是冒泡排序的升级版，同样的基于两两交换，但是引入了分治的思想。通过使用中线，对需要排序的区间进行了重新的一个划分，而这内部剩下的性能还有一方面就是在于这个中线，因为数值的比较不再是全局，而是局部，从效率计算上来讲一般情况可降到O(nlogn) ，当然极端情况就可能退化回我们的冒泡排序。
极端例子：5->4->3->2->1
也就是一个已经完成排序的数组，再经过快速排序，想要将数组排序，就将会造成快排的退化。而解决方案就是不再以首个数据作为中线的基准。

文章图片
voidsort(){//修建枝叶的方法虽然可以用，但是效果微乎其微//因为这只是根据数学方法推算，可以得知变量i=0时，是不需要工作的，也就删去的一小部分的工作for(inti=1;i<array.length;i++){intj=i;inttemp=array[i];//如果当前已完成排序数组中，下标数值大于当前数值//就把这个数值往后进行移动while(j>0&&temp<array[j-1]){array[j]=array[j-1];j--;}if(j!=i)array[j]=temp;}}插入排序，顾名思义，就是把数字放到合适的位置。原理上讲就是将一个无序数组拆分成了两个部分，一块有序，一块无序。不断的删去无序队列中的数值，放到有序队列中，最后也就成为了有序队列。
第一趟排序：（5）->3->4->7->2第二趟排序：（3->5）->4->7->2第三趟排序：（3->4->5）->7->2 。。。。以此类推

文章图片
staticvoidsort(){//gap也就相当于组别for(intgap=array.length>>1;gap>0;gap/=2){for(inti=gap;i<array.length;i++){intj=i;while(j-gap>=0&&array[j]<array[j-gap]){swap(array[j],array[j-gap]);j-=gap;}}}}先对代码做一个解释：（1）gap：也就是是我说的组别，分成两个部分（2）array[j]：右半边需要交换的序列（3）array[j-gap]：左半边交换的序列（4）j-=gap：是为了保障最后一位被遗忘的数据被处理。