Java 排序方法
冒泡排序
- 相邻记录，反序则交换，if(a[j]>a[j+1])
- 冒泡排序每一趟都能把一个数送到最终位置【最大(向前向后），最小(从后向前)】
- 时间复杂度：平均o(n*n),最坏的情况：n-1+n-2+n-3…+1=n(n-1)/2，最好的情况：比较n-1次，交换0次o(n)
- 冒泡排序法受初始序列的影响
- 空间复杂度：o(1)
- 冒泡排序是稳定的【相同关键字在比较过程中不会发生前后位置交换】
for(i=1;i<n;i++){
for(j=0;j<n-i;j++)
if(a[j]>a[i]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
快速排序
- 枢轴：序列的第一个数当作枢轴先提出，i从前向后，j从后向前，都与枢轴比，j对应的数小于枢轴则提到i处，i对应的数大于枢轴则提到j处，i，j相遇则将枢轴值填入
- 每一次会把当前序列中的一个数送到最终位置【枢轴】
- 时间复杂度：o(log₂n)，原始有序时间复杂度最差：o(n² )
- 快速排序时间受初始序列影响（初始有序，反倒最差）
- 空间复杂度：o(log₂n)
- 稳定性：不稳定
选择排序
-
第i躺选当第i小的值，放到第i个位置【求最小值】
-
时间复杂度o(n²)
-
选择排序每一趟都能把一个值送到最终位置，从待排序序列中选择一个最小值放到已排序序列的末尾
-
选择排序时间不受初始序列影响，恒为o(n²)
-
空间复杂度：交换时用一个空间o(1)
-
选择排序不稳定
for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++){ if(a[j]<a[k]) k=j; if(k!=i){ t=a[i]; a[i]=a[k]; a[k]=t; } } }
插入排序
-
直接插入排序
（1）基本思想：将一个待排序记录插入到一个有序子序列中依然保持有序。
（2）最后一次排序开始之前有可能所有的元素都不在最终位置上，也就是说插入排序并不保证每一趟都 把一个元素送到最终位置上
（3）插入排序最好的情况下：数据已经按要求有序，比较n-1次，不发生移动o(n)
最坏的情况下：数据全部反序，需要比较n(n-1)/2，移动n(n-1)/2，o(n²)（4）插入排序受数据初始序列的影响，数据基本有序的时候用插入排序最好。
（5）空间复杂度：o(1)
（6）稳定性：稳定
希尔排序
- 分组插入排序，逐渐合并分组后再插入排序
- 稳定性：不稳定
归并排序
- 两个有序子序列合并成一个有序子序列
- 归并排序每一趟都要进行n次赋值，进行log₂n躺，所以时间复杂度恒o(log₂n)
- 最后一次排序开始之前有可能所有的元素都不在最终位置上，也就是说归并排序并不保证每一趟都把一个元素送到最终位置
- 空间复杂度：o(n)
- 稳定性：稳定
堆排序【选择类排序】
-
基本思想：树形选择排序的一个变形，使用一种堆的概念
-
大根堆【从小到大排序】任意一个非叶子结点的值都大于其左右孩子的值，
小根堆【从大到小排序】任意一个非叶子结点的值都小于其左右孩子的值，
-
时间复杂度：初始建堆+n-2次调整堆时间，恒为o(log₂n)
-
空间复杂度：o(1)交换用的一个空间
-
每趟都会把一个元素送到最终位置
-
不受初始序列的影响
-
不稳定
基数排序【桶】
- 基本思想：按数值的各位进行桶的分配，之后收集成一组，再按十位分配桶，再收集，再按百位分配收集，依次进行
- 位数为d，基数(桶数)
总结
-
不稳定排序：快速排序，选择排序，堆排序，希尔排序
-
稳定排序：冒泡排序，直接插入排序，归并排序，基数排序
-
时间复杂度受初始序列影响：快速排序，希尔排序，直接插入排序，冒泡排序
-
每次排序都能使一个元素到达最终位置：快速排序，选择排序(最小)，堆排序(最大)，冒泡排序(大泡沉底)
-
平均性能最好的是：快速排序
-
空间复杂度最大的是：归并排序
-
基本有序时选：插入排序
-
数据有序反而更差的是：快速排序
如有错误，欢迎私信纠正，谢谢支持！
标签：常用,Java,插入排序,冒泡排序,枢轴,序列,排序,复杂度 From： https://www.cnblogs.com/yangyezhuang/p/16905940.html