文章目录
- 排序
- 一、 排序的概念
- 1.排序：
- 2.稳定性：
- 3.内部排序：
- 4.外部排序：
- 二、插入排序
- 1.直接插入排序
- 2.希尔排序
排序
一、 排序的概念
1.排序：
- 一组数据按递增/递减排序
2.稳定性：
- 待排序的序列中，存在多个相同的关键字，拍完序后，相对次序保持不变，就是稳定的
3.内部排序：
- 数据元素全部放在内存中的排序
4.外部排序：
- 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
二、插入排序
1.直接插入排序
和整理扑克牌类似，将乱序的牌，按值的大小，插入整理好的顺序当中
从头开始，比最后一个小的话依次向前挪，直到大于之前牌时，进行插入
1.如果只有一个值，则这个值有序，所以插入排序， i 从下标1开始，把后面的无序值插入到前面的有序当中
2.j = i-1,是i的前一个数，先用tmp将 i位置的值（要插入的值）先存起来，比较tmp和j位置的值
3.如果tmp的值比 j位置的值小，说明要向前插入到有序的值中，把 j位置的值后移，移动到 j+1的位置，覆盖掉 i 的值
4.j 下标向前移动一位，再次和 tmp 比较
5.如果tmp的值比 j 位置的值大，说明找到了要插入的位置就在当前j位置之后，把tmp存的值，放到 j+1的位置
6.如果tmp中存的值比有序的值都小，j位置的值依次向后移动一位，j不停减1，直到排到第一位的数移动到第二位，j的下标从0移动到-1，循环结束，最后将tmp中存的值，存放到 j+1的位置，也就是0下标
public void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];//tmp存储i的值
int j = i - 1;
for (; j >= 0; j--) {
if (tmp < array[j]) {
array[j + 1] = array[j];
} else {
// array[j+1] = tmp;
break;
}
}
array[j + 1] = tmp;
}
}
插入就是为了维护前面的有序
-
元素越接近有序，直接插入排序算法的时间效率越高
-
时间复杂度O( N 2 )
-
空间复杂度O ( 1 )
-
稳定性：稳定
如果一个排序是稳定的，可以改变实现为不稳定的
如果是不稳定的排序，则没有办法改变
2.希尔排序
希尔排序shellSort 叫缩小增量排序，是对直接插入排序的优化，先分组，对每组插入排序，让整体逐渐有序
利用了插入排序元素越有序越快的特点
- 先确定一个整数，把待排序数分成多个组，每个组中的数距离相同，
- 对每一组进行排序，然后再次分组排序，减少分组数，组数多，每组数据就少
- 找到分组数=1时，基本有序了，只需要再排一次插入排序即可
一开始组数多，每组数据少，可以保证效率
随着组数的减少，每组数据变多，数据越来越有序，同样保证了效率
到达1分组之前，前面的排序都是预排序
public static void shellSort2(int[] array) {
int gap = array.length;
while (gap > 1) { //gap>1时缩小增量
gap /= 2;//直接在循环内进行最后一次排序
shell(array, gap);
}
}
/**
*
* 希尔排序
* 时间复杂度O(N^1.3---N^1.5)
* @param array
*/
public static void shellSort1(int[] array) {
int gap = array.length;
while (gap > 1) { //gap>1时缩小增量
shell(array, gap);
gap /= 2;//gap==1时不进入循环，再循环为再次排序
}
shell(array, gap);
//组数为1时，进行插入排序
}
public static void shell(int[] arr, int gap) {
//本质上还是插入排序，但是i和j的位置相差为组间距
for (int i = gap ; i < arr.length; i++) {
int tmp = arr[i];
int j = i-gap;
for (; j >=0; j -= gap) {
if (tmp<arr[j]){
arr[j+gap] = arr[j];
}else {
break;
}
}
arr[j+gap] = tmp;
}
}
- 时间复杂度：O( N^1.3 ^) ---- O( N^1.5 ^)
- 空间复杂的：O(1)
- 稳定性：不稳定
点击移步博客主页，欢迎光临~
