冒泡排序、插入排序、希尔排序、选择排序
二、冒泡排序
冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。
它会遍历若干次需要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。
这样，一次遍历之后，最大的元素就在数列的末尾！
采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。
重复此操作，直到整个数列都有序为止！
private static void bubbleSortBySorted(int[] a){
if(a == null || a.length < 2){
return;
}
//若不交换值，则表示已排序好，结束比较
boolean isSorted = true;
//表示每轮比较的终止点，已排序好的不需要再比较
int sortBorder = a.length - 1;
//每轮比较最后一次交换的下标
int lastExchangeIndex = 0;
//因为有a.length个元素，所以需要循环a.length-1轮
for(int i = 0; i < a.length-1; i++){
for(int j = 0; j < sortBorder; j++){
//前者大于后者，则想换交换值，将前者大的值往后移
if(a[j] > a[j+1]){
swap(a[j],a[j+1]);
lastExchangeIndex = j;
isSorted = false;
}
}
//每轮最后一次交换的下标，表示其后面都已排序好，就是下一轮比较的终止点
sortBorder = lastExchangeIndex;
if(isSorted){
break;
}
}
}
//相互交互值
public static void swap(int a,int b){
int temp = a;
a = b;
b = temp;
}二、插入排序
插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，类似于摸牌时对扑克牌的排序。
private static void insertSort2(int[]a){
if(a == null || a.length < 2){
return;
}
//有a.length个元素，需要比较a.length-1轮
//已排序区默认是下标0，未排序区从下标1开始
for(int i = 1; i < a.length; i++){
//记录待插入的元素
int temp = a[i];
int j = i;
//若前面已排序元素大于待插入元素，则排序元素往后移，给待插入的元素腾位置
for( ; j >= 1 && a[j-1] > temp; j--){
a[j] = a[j-1];
}
//待插入元素放到合适位置
a[j] = temp;
}
}三、希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
public static void shellSort(int[] a) {
//增量gap代表同组元素间距，也代表有多少组
//初始分为arr.length / 2组，每次减半直至分为1组，进行最后一次排序结束
for(int gap = a.length/2; gap > 0; gap /=2){
//插入排序（同组间距为gap）
//非排序区从gap开始
for(int i = gap; i < a.length; i++){
//记录待插入的元素
int temp = a[i];
int j = i;
//若前面gap间距已排序元素大于待插入元素
//则已排序元素往后移gap间距，给待插入的元素腾位置
for(;j >= gap && a[j-gap] > temp;j -= gap){
a[j] = a[j-gap];
}
//
a[j] = temp;
}
}
}四、选择排序
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。
但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
public void selectSort2(int[] a){
if(a == null || a.length < 2){
return;
}
//进行a.length-1次选择,最后一个元素不需要再选择比较
for(int i = 0; i < a.length; i++){
int minIndex = i;
//从无序区选取最小元素的下标
for(int j = i + 1; j < a.length; j++){
if(a[j] < a[minIndex]){
minIndex = j;
}
}
//无序区最小元素放到有序区
if(i != minIndex){
swap(a[i],a[minIndex]);
}
}
}五、比较
选择排序是非稳定排序，每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。因此，插入排序比冒泡排序在性能方面更优。
希尔排序是对直接插入排序算法更进一步优化的版本，平均时间复杂度为O(n^1.3)，性能更优，但是属于非稳定排序。
这四种算法排序，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以我们更倾向于用后面要讲的时间复杂度为O(nlogn)的排序算法。
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
