myAlgorithm
我的算法从这里开始:
选择排序:
最简单也最没用,即一遍遍的过滤数组,找到最小的数和最前面做交换;单指针记录此次遍历中最小值的索引;
冒泡排序:
两两比较,后一个数比前一个数大就做交换,同样是单指针,也是没用的算法;
插入排序:
即从索引1处开始和前面的数做比较找到当前它应该在的位置,移位,就是摸扑克排顺序的过程,在简单排序中最常用;
希尔排序:
基于插入排序,可以看作多线程版插排,即设置一个步长,每一轮比较步长间隔处的数,使用插排;特点是间隔大移动次数少,间隔小移动距离短(移位法);
归并排序:
1.使用递归**,把数组分为左右两部分,假设左右两部分都是有序的,然后继续往下假设直到分成子数组只有一个数或两个数;
2.现在子数组有序了,此时分配一个新数组,长度等于两个子数组长度和,定义三个指针,左指针指第一个子数组的最左边,右指针指向第二个子数组的最左边
第三个指针指向新数组的最左边,比较这两个指针处的值,把更小的那个值赋给新数组指针处,同时移动左右指针中指向更小值的那个指针和新数组指针
直到左右指针中其中一个移到了它的最大值,这时把另一个没达到最大值的左右指针后面的数直接按顺序赋给新数组指针处,直到新数组指针到达最大值
此时左右两个指针也都到达了各自的最大值,此次归并结束,把新数组赋值回原数组对应位置(即从左指针到右指针能移动到的最大值处)
3.编写递归方法,分四步:(1)把当前数组分为两部分;(2)左边排序;(3)右边排序;(4)归并排序;
4.归并排序是java对象的默认排序算法(要经过判断),可以实现稳定排序,最好最坏时间复杂度都是O(N*logN),个人觉得是比较完美的一种算法;
快速排序:
1.使用递归**,选定一当前数组中的数当轴,然后把当前数组排序成轴左边都比轴小,右边都比轴大,然后轴左右两边的数组再各自选定一个轴,排序,递归下去;
2.经典单轴快排:选定当前数组最后一个数做轴,设置左右两个指针,左指针指向当前数组最左端,右指针指向轴处索引减一,左右指针
不断向中间靠近,左指针遇到比轴大的数停下,右指针遇到比轴小的数停下,只有在左右指针同时停止时,交换左右指针指向的值,然后左右指针继续向中间靠近,当左右指针变为相邻那一刻时,停止左右指针变化且不交换对应值,把右指针处值和轴做交换,一次快排结束
3.编写递归方法,分四步:(1)选定一个轴[轴的选取直接影响快排的时间复杂度];
(2)对当前数组快速排序,确定轴应该在的位置;(3)轴左边排序;(4)轴右边排序;
4.快速排序的轴选定很重要,直接影响时间复杂度,平均时间复杂度和最好时间复杂度都是O(N*logN),最坏时间复杂度是O(N^2)
快排是不稳定的;
计数排序:
桶**算法,但局限性较大,即首先要确定当前数组中值的取值范围,定义一个按照这个范围的长度的新数组,遍历原数组,把遍历出
的值对应到新数组的索引,把新数组此索引处值加一;
遍历完原数组后,定义一个指针指向新数组索引为1处,把此处的值变为指针前一个索引处的值和自己的值的和,向后移动指针,创建一个最终数组长度等于原数组,
倒着遍历原数组的值,把这个值对应成新数组索引并拿到新数组这个索引处的值(并对这个新数组的值进行减减操作),这个值减一就是原数组值在最终数组中应该放入的位置
遍历完原数组,最终数组里就是排序好的原数组,并且是稳定的;
如果不要求稳定性则不需要累加新数组而且最后不需要倒着遍历原数组,实现简单很多,具体见代码
基数排序:
基数排序也是桶**,创建一个二维数组作为桶,一维索引长度等于原数组最大值的位数(就是几位数)遍历原数组,按位数的值存入桶,并设置一个新数组长度等于最大位数记录桶的
对应一维索引处放了几个值,遍历完再把桶里的数据按照新数组里的值拿出来放回原数组,然后置空新数组;
接下来提高位数再次遍历原数组,思路和实现都简单;
桶排序**实质上是用空间换时间;
桶排序:
用的很少,也要先确定原数组值的取值范围,把这个范围分成几份,每份对应一个桶,遍历原数组存入对应的桶,遍历完后再在每个桶内部排序后取出;