8种基本排序情况概述：
1、稳定性
归并排序、冒泡排序、插入排序、基数排序是稳定的
选择排序、快速排序、希尔排序、堆排序是不稳定的
2、时间复杂度
最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n*log2n)，其他都是O（n2）
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) |
B是真数(0-9)， R是基数(个十百) |
| Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
直接插入排序：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。（使用场景：把新的数据插入到已经排好的数据列中）
- 将第一个数和第二个数排序，然后构成一个有序序列
- 将第三个数插入进去，构成一个新的有序序列。
- 对第四个数、第五个数……直到最后一个数，重复第二步
java代码实现
- 设定插入次数，即循环次数，但是第一个数字不用排序，所以一共循环数组长度-1次，for(int i=1;i<length;i++)；
- 设定插入数=insertNum和得到已经排好序列的最后一个数的位数j=i-1。
- 从已经排好序列的最后一个数开始向前循环，如果要插入数小于当前数insertNum<a[j]，就将当前数向后移动一位。
- 将当前数放置到空着的位置，即j+1。
public class InsertSort {
public void insertSort(int[] a){
int length=a.length;//数组长度，将这个提取出来是为了提高速度。
int insertNum;//要插入的数
for(int i=1;i<length;i++){//插入的次数
insertNum=a[i];//要插入的数
int j=i-1;//已经排序好的序列元素个数
while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格
a[j+1]=a[j];//元素移动一格
j--;
}
a[j+1]=insertNum;//将需要插入的数放在要插入的位置。
}
}
}冒泡排序:是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法,冒泡排序是最慢的排序算法，实际运用中效率最低，当数列为由小到大的有序数列时为最好情况，当由大到小时为为最坏情况。（很少使用）
- 将序列中所有元素两两比较，将最大的放在最后面。
- 将剩余序列中所有元素两两比较，将最大的放在最后面。
- 重复第二步，直到只剩下一个数。
java实现：
- 设置循环次数。
- 设置开始比较的位数，和结束的位数。
- 两两比较，将最小的放到前面去。
- 重复2、3步，直到循环次数完毕。
public class BubbleSort {
public void bubbleSort(int[] a){
int length=a.length;//数组长度
int temp;
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
}
未完待续
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/15814.html
