目录
对象的比较
玫瑰都是在荆棘中绽放的！
比较引用类型的关系：
- 大小关系：
实现比较器Comparable(compareTo方法重写：调用的对象是this)
Comparator接口（直接写一个类来实现该接口，其中要重写compare方法） - 相等关系：true false
== 比较值（地址 or 直接值）
否则就需要重写equals方法，equals方法的底层默认还是 ==
努力成为你想成为的人！
一、排序的概念及应用
1. 排序的概念
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳
定的；否则称为不稳定的。
（稳定性：就是指如果存在多个相同的关键字，如果排序前后其相对位置一样就说明具有稳定性。）
- 内部排序：数据元素全部放在内存中的排序。（也就是相当于在RAM中排序）
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。（也就是相当于在磁盘中排序）
- 思考：Arrays.sort -->底层是一个什么排序？
- 注：在本章节讲到的所有排序都默认是从小到大排列，所讲的都是内部排序。
2. 常见的排序算法
二、常见排序算法的实现
1. 插入排序（用处广泛）
1. 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
2. 直接插入排序
- 当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。（即：比较 插入）
- 直接插入排序的特性总结：
1） 元素集合越接近有序，直接插入排序算法的时间效率越高
2） 时间复杂度：O(N^2) 3）
空间复杂度：O(1)，它是一种稳定的排序算法
4） 稳定性：稳定
- 代码思路：从第二个元素开始排序：设i,j=i-1,然后进行比较，i++，j–（可能会出现j<0)，然后又j=i-1。（需要一个临时变量tmp）
（其实也就是：第n个数据要与前n-1个比较） - 源码：
/** 直接插入排序：
* 时间复杂度：等比数列求和
* 最坏：O(N^2) 逆序
* 最好：O(N) 有序
* 结论：对于直接插入排序来说，数据越有序越快。
* 场景：当数据基本有序的时候就使用直接插入排序。
* 空间复杂度：O(1)
* 稳定性：tmp<arr[j]时不加=就是稳定，加了就不稳定了
* 一个本身就稳定的排序，你可以实现为不稳定；
* 但是一个本身就不稳定的排序，是没有办法变成稳定的排序的。
* @param arr
*/
public void insertSort(int[] arr) {
// 从第二个元素开始排序
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
// 进行比较
int j = i-1;
for (; j >= 0; j--) {
if(tmp<arr[j]) {
// 小于就j往前挪,然后j的值往后移动
arr[j+1] = arr[j];
// 注意这里不需要再次j--，条件已经在括号中
} else {
// 大于则直接插入
// arr[j+1] = tmp; // 也可以拿到循环外面，这样的话j要定义在外面！
// 结束循环
break;
}
}
// 大于则直接插入
arr[j+1] = tmp;
}
}
3. 希尔排序（缩小增量排序）
- 希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个组，所有相隔某个“增量”的记录分在同一内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达==1时，所有记录在统一组内排好序。
- 简而言之，希尔排序shellSort:缩小增量算法：
分组、组内直接插入排序 - 希尔排序其实就相当于跳着排序：使得数据大的尽可能靠后！数据逐渐趋于有序
n组：可以理解为：每两个数据之间间隔n个数据 - 希尔排序：选择增量值（也就是组数），最后一个增量值是1。
希尔排序较少考。 - 希尔排序的特性总结：
1） 希尔排序是对直接插入排序的优化。
2） 当gap（分组，即：增量值） > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。故就整体而言，可以达到优化的效果。
3） 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在许些树中给出的希尔排序的时间复杂度都不固定。
（注：因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们计算时间复杂度暂时就按照：O(n1.25 ) ~ O(1.6* n1.25）来计算
4）稳定性：不稳定
- 源码：
private static void shell(int[] arr, int gap) {
// i表示后面的元素
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
// 进行比较
int j = i-gap;
for (; j >= 0; j-=gap) { // 注意此时j的变换条件是j-=gap，因为交换的是对应的两个元素！
if(tmp<arr[j]) {
// 小于就j往前挪,然后j的值往后移动
arr[j+gap] = arr[j];
} else {
// 大于则直接插入
// arr[j+gap] = tmp; // 也可以拿到循环外面，这样的话j要定义在外面！
// 结束循环
break;
}
}
// 大于则直接插入
arr[j+gap] = tmp;
}
}
public static void shellSort(int[] arr) {
// 问题：如何确定增量值？
/*int[] drr = {5,2,1};
for (int i = 0; i < drr.length; i++) {
shell(arr,drr[i]);
}*/
int gap = arr.length;
while(gap > 1) {
shell(arr,gap);
gap /= 2; // 注意变换！！
}
// 最后进行一次增量值为1的排序就行
shell(arr,1);
}
2. 选择排序
1. 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2. 直接选择排序
- 代码思路：
定义i,j下标，j下标移动寻找比i下标的元素小的值并记录其下标minIndex，继续移动更新minIndex；当i走完后，minIndex所指的值与i下标所指的值进行交换，然后i++；j=i+1，minIndex=i；重复以上操作。（minIndex的初值记录为当前i下标对应的值）
- 【直接选择排序的特性总结】：
1）直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2） 时间复杂度：O(N2)
3） 空间复杂度：O(1)
4） 稳定性：不稳定
- 直接选择排序源码：
/**
* 直接选择排序：
* 时间复杂度：等差数列求和(N-1+N-2+...+1+0)，即：O(N^2)-->对数据不敏感，不管是有序还是无序，时间复杂度都是一样的
* 空间复杂度：O(1)
* 稳定性：不稳定
*/
public static void selectSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len-1; i++) { // 最后一个数据不用比较
int minIndex = i; // 记录当前被比较的下标,以此作为最小值的对照条件
for (int j = i+1; j < len; j++) {
if(arr[minIndex] > arr[j]) {
// 进行minIndex的更新
minIndex = j;
}
}
// 来到这儿说明找到minIndex最终值,是要把minIndex值与i值进行交换，而不是简单的赋值
// 简单的赋值会丢失原来i下标所指的值
// arr[i]= arr[minIndex];
swap(arr,minIndex,i);
}
}
// 交换方法
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
- 直接选择排序的优化：
直接选择排序的优化，同时选择两个元素，一个最小放左边，一个最大放右边。注意：修正maxIndex！！
- 直接选择排序优化的源码（时间复杂度不变）：
/**
* 直接选择排序的优化：一次选择两个元素--> 一个最小minIndex放最左边left，一个最大maxIndex放最右边right
* 完成一次后left++ right-- 但是要始终保证该循环是在left<right条件下进行的
* minIndex/maxIndex首先都标记为left
* 时间复杂度依旧是：O(N^2)
*/
public static void selectSort2(int[] arr) {
int left = 0;
int right = arr.length-1;
//for (int i = 0; i <= arr.length/2; i++) {
while(left<right) {
int minIndex = left;
int maxIndex = left; // 首先进行标记,都以未排序的最左边为min、max
for (int i = left+1; i <= right; i++) { // 注意i从left+1开始
if(arr[i]<arr[minIndex]) { // 更小就更新
minIndex = i;
}
if(arr[i]>arr[maxIndex]) { // 更大就更新
maxIndex = i;
}
}
// 标记好后进行交换
// 直接min交换完交换max可能会存在一个问题：如果left==max，而又有min需要left与min交换，
// 交换后原来的max就变了，之后的right与max交换就不是原来的值，就会出错。
swap(arr,left,minIndex);
// 交换完后进行判断，修正 max的下标！！！
if(left == maxIndex) {
maxIndex = minIndex;
}
swap(arr,right,maxIndex);
// 完成交换后进行left right变换
left++;
right--;
}
}
3. 堆排序
- 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。（即：从小到大建大根堆）
- 从小到大（升序）：建立大根堆（需要使用【向下调整】）、每次最后一个元素跟堆顶元素进行交换（注意：最后一个元素下标是会逐步向前的）、交换后【向下调整】保证大根堆。
- 【直接选择排序的特性总结】：
1） 堆排序使用堆来选数，效率就高了很多。
2） 时间复杂度：O(N*logN)
3） 空间复杂度：O(1)
4） 稳定性：不稳定
- 源代码：
/**
* 堆排序：建堆（【调整】）
*
* 时间复杂度：O(N*logN)
* 空间复杂度：O(1)
* 稳定性：不稳定
*/
public static void heapSort(int[] arr) {
// 创建大根堆：（从小到大）
createBigHeap(arr);
// 最后一个元素与堆顶元素进行交换
int end = arr.length-1;
while(end>=0) {
swap(arr,0,end);
// 进行【向下调整】：注意源码中是<len
shiftDown(arr,0,end);
end--; // 调整好后最后一个数据就是maxValue，将其排除后进行循环比较
}
}
// 建大根堆
private static void createBigHeap(int[] arr) {
// 先确定最后一颗子树的根结点，根据根结点进行建堆
for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
// 由根结点开始【向下调整】
shiftDown(arr,parent,arr.length);
}
}
// 向下调整
private static void shiftDown(int[] arr,int parent, int len) { // 结束位置是数组长度！
// 左右孩子比较取最大，然后最大孩子结点与根结点进行比较，是否交换
int child = 2*parent+1;
// 最起码保证左孩子存在
while(child<len) {
if(child+1<len && arr[child]<arr[child+1]) {
child++; // child存储最大值下标
}
if(arr[child] > arr[parent]) {
swap(arr,child,parent);
// 交换完之后进行parent与child的调整，保证在交换后其子树也是满足大根堆
parent = child;
child = 2*parent+1;
} else {
break; // 满足大根堆就直接终止循环
}
}
}
THINK
- 插入排序：直插、希尔（缩小增量法）
- 选择排序：直接选择、堆排
- 注意时间以及空间复杂度
- 注意代码思路以及书写
- 稳定性