排序
概念
稳定性
稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后，次序不变，则是稳定的。
内部排序
排序记录全部存放在内存中进行排序的过程。
外部排序
待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
选择排序-不稳定
每次选择剩余待排序元素中的最小值，放到已排序元素的末尾。
原理：每次排序选出最小的元素，替换到对应顺序末尾的位置。 思路：第一次排序选出最小的元素，和待排序数组第一位的元素进行交换。
json
/**
* 选择排序的思路：
* 1.外层循环n-1次，对所有元素进行遍历，
* 2.首先设置循环位次为初始下标位置
* 3.内层排序从遍历元素位置+1开始遍历，到最后一个元素。
* 4.比较元素下标，记录最小元素的下标
* 5.将最小元素下标位置元素与循环位次下标元素进行替换
*
* @param arr
* @return
*/
public static int[] choooseSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
//设置最小元素下标初始值
int min = i;
//选择出最小的值
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
//设置最小元素下标位置
min = j;
}
}
if (min != i) {
//设置临时变量
int temp;
//交换最小元素与未排序的第一个元素
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
log.info("第{}次排序后的结果：{}", i, Arrays.toString(arr));
}
return arr;
}
- 17和21交换位置。破坏了两个21之间的相对位置。
冒泡排序-稳定
从第一个元素开始，和相邻的元素进比较，若前面的元素比后面的元素大，则两者交换位置，直到最大的元素放到最后位置。
相邻两个元素，两两交换。
- 外层循环n-1次，代表需要循环n-1次。
- 内层循环：比较为排序的字段列表，相邻元素进行比较，大的元素排在后面。
直接插入排序-稳定
将数据按照顺序插入到表里。保证插入每个元素之后，表元素顺序是有序的。
- 将传入数组的第一个元素视为顺序表的第一个元素。
- 从第二个元素开始和之前的元素进行比较
- 比较规则是：若元素比比较的元素小，则两者交换位置
json
public static int[] sort(int[] arr) {
//临时变量
int temp;
for (int i = 1; i < arr.length; i++) {
//从第一个开始和之前的元素比较
for(int j =0;j<i;j++){
//若比之前的元素小，则交换元素
if(arr[i]<arr[j]){
temp = arr[i];
arr[i]=arr[j];
arr[j] = temp;
}
}
System.out.println("第"+i+"次排序后的结果:"+ Arrays.toString(arr));
}
return arr;
}
如果待排序列基本有序，使用直接插入排序。
希尔排序-不稳定
直接插入排序的增强版本。
现将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序；待整个序列中的记录基本有序的时候，再对全体记录进行一次直接插入排序。
堆排序-不稳定
对树进行调整，调整完的树保证根节点比左右子树都要大。即为大根堆，每次调整将堆顶元素弹出。
每次调整完，弹出堆顶元素，直到弹出所有元素即可得到有序序列。
大根堆递增，小根堆递减。
快速排序-不稳定
快速排序首先选择了一个基准值，然后分别选择两个指针在数组中一个找大，一个找小，然后进行交换。
通过一趟排序将待排序的记录以基准值为分界，分为独立的两个部分，称为前半区和后半区；前半区均小于基准值，后半区均大于基准值。
然后再分别对这两个部分在进行快速排序，从而使得整个序列有序。
分而治之
在基本有序的情况下，快排的时间复杂度是最坏的。
- 快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序。
- 时间复杂度：最好：O(N*logN) ； 最坏：O(N2)
- 空间复杂度：O(logN) ~ O(N)
- 稳定性：不稳定
- 快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序。
- 时间复杂度：最好：O(N*logN) ； 最坏：O(N2)
- 空间复杂度：O(logN) ~ O(N)
- 稳定性：不稳定
归并排序
总结
- 选择排序：
- 将元素分为已排序和待排序。
- 从待排序元素中选择出最小值。追加到待排序元素末尾。
- 冒泡排序：相邻元素两两交换，直到最大元素放到末尾。
- 直接插入排序：
- 将元素分为排序和待排序，已排序元素保持有序状态。
- 遍历待排序中的元素，将元素插入到已排序元素列表合适的位置。
- 希尔排序 - 插入排序增强版（分而治之）：
- 适合大数据量的情况，将数据分为多个分组。
- 每个分组先进行直接插入排序。
- 将排序好的分组统一进行直接插入排序。
- 快速排序：
- 选择一个基准值，将比基准值小的元素放到左边，比基准值大的元素放到右边。
- 对左右分区进行快速排序，直到整个序列有序。
- 堆排序：
- 构造排序树，每次将最小值出树。
复杂度
空间复杂度
大部分排序都是比较交换，无需额外空间。
快速排序需要存储每次基准值。
时间复杂度
与堆、树、二分有关的算法都是 n*logn。
- 堆排序（堆）
- 快速排序（二分）
直接的算法都是 n*n。