排序算法(上)
1.排序算法 (O(n^2)时间复杂度)
1.1选择排序
核心思想：
从第一个元素开始，扫描后面所有元素，当比其小时就进行交换。
//外循环 扫描所有的元素
for(int i = 0 ; i < arr.length ; i++){
//内循环 i 所在位置 后面的所有元素
for(int j = i + 1 ; j < arr.length ; j++){
if(arr[i] > arr[j]){
swap(arr,i,j);
}
}
}
1.2插入排序
核心思想：
默认将整个数组，分成了 一个是有序的，一个是无序的。关键点在于，将一个元素放入一个有序数组，且保持其数组有序。
//数组的第二个元素开始，因为此时默认第一个元素为有序的
for(int i = 1 ; i < arr.length ; i++){
//遍历这个默认有序的数组，找到 *第一个* 小于这个无序元素的位子 停止
for(int j = i ; j > 0 && arr[j] < arr[j - 1]; j --){
swap(arr,j,j-1);
}
}
//优化，思路减少交互次数。
//可以将 无序的元素，复制一份，作为对比，大于其的就向前挪一位。最后找到小于其的跳出循环，（减少赋值次数）
for(int i = 1 ; i < arr.length ; i++){
int e = arr[i];
int j;
//遍历这个默认有序的数组，找到 *第一个* 小于这个无序元素的位子 停止
for(j = i ; j > 0 && e < arr[j - 1]; j --){
arr[j] = arr[j - 1];
}
arr[j] = e;
}
优点：
当遇到一个近乎有序的数组时，可以非常快的排序完成，时间复杂度为O(n)级别的。在对于其他算法的优化时也非常的有用，因为在小于一定数量的数组，其本身就有序性很强，使用插入排序效率很高。
1.3冒泡排序
核心思想：
两两交互，最大的通过两两交互到最右边。其过程每一步都是将最大的哪一个往后移，很像水中的泡泡慢慢上升一样，所以顾名思义。
for(int i = 0 ; i < arr.length ; i++){
for(int j = 1 ; j < arr.length - i ; j++){
if(arr[j] < arr[j - 1]){
swap(arr,j - 1,j);
}
}
}
//优化
// 优化核心： 减少循环次数
// 减少 外循环次数：设置一个标记，当内循环没有一次交换时就跳出
// 减少 内循环次数：控制循环的上限，将上限设置为 内循环最后一次交换的位置。
// 也有缺点 就是 标记为太多，有时可能会 影响性能。
int i,j,pos;
int k = arr.length;
boolean flag = false;
for(i = 0 ; i < arr.length ; i++){
for(j = 0 ; j < k ; j++){
flag = true;
if(arr[j] < arr[j - 1]){
flag = fasle;
swap(arr,j,j-1);
pos = j;
}
}
k = pos;
if(flag){
break;
}
}
1.4希尔排序
核心思想：
是插入排序的一种优化，数组全部个数的一半为长度size，取出数组中，从第一个开始，此元素相隔size个的元素，进行插入排序，后面的元素依次内推。外部，每次size减少一半，直到最后size为1停止。
排序分解图:
思想理解:
这样的思想，最大利用了插入排序对于有序数组的快捷性。当size非常大时，其内循环的组数就比较多，且需要排序元素却少。当内循环的组数少时。元素比较多，但是其元素在之前已经被粗密度的排过一次序了。
一句话就是：开始 粗密度，组数多，元素少，排序快。后面 细密度，组数少，元素多，但是近乎有序。
int d = arr.length;
while(true){
d = d/2;
for(int i = 0; i < d; i++ ){
for(int j = 0; j < arr.length;j+=d){
int e = arr[j];
int l ;
for(l = j - d ; l > 0 && arr[l] > e ; l = l - d){
//这里加d的原因是，此时的元素，后移一位。
arr[l+d] = arr[l];
}
//这里+d 是因为 第一次初始 l 减了一个d。
arr[l + d] = e;
}
if(d==1){
break;
}
}
}
1.5总结测试
测试
测试用例 长度 50_000，元素随机范围为 [0,50_000]
第一次：
selectSort-->5.35 s
insertSort-->5.119 s
bubbleSortInt-->3.366 s
betterBubbleSortInt-->3.534 s
shellSort-->0.008 s
第二次：
selectSort-->5.224 s
insertSort-->5.169 s
bubbleSortInt-->3.484 s
betterBubbleSortInt-->3.561 s
shellSort-->0.009 s
测试用例 长度 10_000，元素随机范围为 [0,10_000]
第一次：
selectSort-->0.173 s
insertSort-->0.167 s
bubbleSortInt-->0.191 s
betterBubbleSortInt-->0.151 s
shellSort-->0.003 s
第二次：
selectSort-->0.161 s
insertSort-->0.159 s
bubbleSortInt-->0.137 s
betterBubbleSortInt-->0.152 s
shellSort-->0.005 s
测试用例 长度 10_000，元素随机范围为 [0,20]
第一次：
selectSort-->0.084 s
insertSort-->0.098 s
bubbleSortInt-->0.142 s
betterBubbleSortInt-->0.153 s
shellSort-->0.004 s
第二次：
selectSort-->0.074 s
insertSort-->0.088 s
bubbleSortInt-->0.161 s
betterBubbleSortInt-->0.159 s
shellSort-->0.003 s
测试用例 长度 1_000_000，元素随机范围为 [0,1_000_000]
shellSort-->0.213 s
测试用例 长度 1_000_000，元素随机范围为 [0,20]
shellSort-->0.1 s
测试用例 长度 10_000_000，元素随机范围为 [0,10_000_000]
shellSort-->3.529 s
测试用例 长度 10_000_000，元素随机范围为 [0,20]
shellSort-->1.922 s
总结
- 可以看出 冒泡排序 数组 数量多且，重复度低的情况下要比 插入与选择排序的效率好。
- 当 数组元素重复度高时，选择排序与插入排序的效率比冒泡排序要好。
- 而冒泡排序的优化，其实并不理想，因为中间存在了大量的多余赋值操作。
- 希尔排序 无论哪一种数据都很快
- 希尔排序，可以最大接受范围 百万级别的排序 0.2s
- 排序效率与元素的重复程度有关
- 进而在证实 其中是插入排序进化版
