排序
插入排序、冒泡排序、归并排序、快速排序，选择排序 算法的比较，需要从额外空间消耗，平均时间复杂度和最差时间复杂度等方面去比较他们的优缺点
插入排序
1. 直接插入排序
| 平均时间复杂度 | 最好情况 | 最坏情况 | 辅助空间 |
|---|---|---|---|
| O(n^2) | o(n) | O(n^2) | O(1) |
最好情况是 每次都插在最后 只需要遍历一遍数组
最坏情况是 每次都要交换到第一个元素去和之前每个数都要比较一遍
直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。
public static void insertionSort(int[] a){
for(int i=0;i<a.length;i++){
for(int j=i-1;j>=0;j--){
if(a[i]<a[j]){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
i--;
}
}
}
}
归并排序
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog2n) | o(nlog2n) | O(n^2) | O(n) |
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
- 基本思想
把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
2、算法描述
- 自上而下的递归
- 自下而上的迭代
一、递归法（假设序列共有n个元素）：
①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③. 重复步骤②，直到所有元素排序完毕。
归并实际上要做两件事
分解：采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列
分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。
合并：分别把从左右子序列的编号对比 较小的就提出来放入新开辟的数组中已放入的元素不再参与比较，直到任意一个子序列的元素都放入新数组中就结束，再把另一个数组剩余的元素放进新数组。
public class MergingSort {
public static void main(String[] args){
int a[] = {5, 2, 4, 6, 1, 3, 2, 6};
System.out.println(Arrays.toString(merging(a)));
}
public static int[] merging(int[] a){
int middle = a.length/2;
if(middle>0){
int[] left = Arrays.copyOfRange(a, 0, middle);
int[] right = Arrays.copyOfRange(a, middle,a.length);
return sort(merging(left), merging(right));
}
return a;
}
public static int[] sort(int[] left,int[]right){
int[] temp = new int[left.length+right.length];
int k=0;
int i=0,j=0;
while(i<left.length&&j<right.length){
if(left[i]<=right[j]){
temp[k++]=left[i++];
}else{
temp[k++]=right[j++];
}
}
while(j<right.length){
temp[k++]=right[j++];
}
while(i<left.length){
temp[k++]=left[i++];
}
return temp;
}
}
快速排序
| 平均时间复杂度 | 最好情况 | 最坏情况 | 辅助空间 |
|---|---|---|---|
| O(nlog2n) | o(nlog2n) | O(n^2) | nlog₂n |
快速排序基本思想挖坑填数+分治法
首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序通过分之策略来吧一个序列分成两个子序列
- 挑选一个元素作为基准
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
public static void quicksort(int[] a,int low,int high){
int left=low;
int right=high;
int temp = a[left];//坑1
while(left<right){
//坑2：从后向前找到比基准小的元素，插入到基准
while(left<right&&a[right]>=temp){ 位置坑1中
right--;
}
a[left]=a[right];
//坑3：从前向后找比基准数大的元素，插入到坑2中
while(left<right&&a[left]<=temp){
left++;
}
a[right]=a[left];
}
a[left]=temp; //填坑3
if(left-1>low){
quicksort(a, low, left-1);
}
if(left+1<high){
quicksort(a, left+1, high);
}
}
以上是递归版的快速排序，递归的本质是栈，非递归版本就用栈来保存中间变量，就可以实现非递归了，这个中间变量的实质是划分为子序列的low和high。
public static void quickSortByStack(int[] a){
if(a.length<=0) return;
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
stack.push(a.length-1); //在栈中存放两端
while(!stack.isEmpty()){
int right = stack.pop();
int high = right;
int left = stack.pop();
int low = left;
int temp = a[left];
while(left<right){
while(left<right&&a[right]>=temp){
right--;
}
a[left]=a[right];
while(left<right&&a[left]<=temp){
left++;
}
a[right]=a[left];
}
a[left]=temp;
System.out.println("Sorting: " + Arrays.toString(a));
if(low<left-1){
stack.push(low);
stack.push(left-1);
}
if(left+1<high){
stack.push(left+1);
stack.push(high);
}
}
}
堆排序
堆
堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：
- Parent(i) = floor(i/2)，i 的父节点下标
- Left(i) = 2i，i 的左子节点下标
- Right(i) = 2i + 1，i 的右子节点下标
二叉堆一般分为两种：最大堆和最小堆。
最大堆：
最大堆中的最大元素值出现在根结点（堆顶）
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
最小堆：
最小堆中的最小元素值出现在根结点（堆顶）
堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
堆排序原理
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点，一个完全二叉树拥有子节点的个数为(n/2)-1个
堆排序（Heap-Sort）：将第一个节点(最大的数)与尾节点交换 然后堆大小-1，此时数组末尾的数即为最大的数
继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based(下标从0开始)，这就意味着我们的堆数据结构模型要发生改变 即根节点的下标为0
相应的，几个计算公式也要作出相应调整：
Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2i + 2，i 的右子节点下标
代码实现
public class HeapSort {
public static void main(String[] args){
int a[]={7,9,4,8,6,1,5,2,3,0};
heapSort(a,a.length);
}
public static void heapSort(int[] a,int heapsize){
if(heapsize<=0){
return;
}
for(int index=(heapsize/2)-1;index>=0;index--){ //创建最大堆
int parent = index;
int left = parent*2+1;
int right = parent*2+2;
if(left<heapsize){
if(a[parent]<a[left]){
parent = left;
}
}
if(right<heapsize){
if(a[parent]<a[right]){
parent=right;
}
}
if(parent!=index){
int temp = a[index];
a[index]=a[parent];
a[parent]=temp;
}
}
System.out.println(Arrays.toString(a));
adjust_heap(a, heapsize);
heapsize--;
System.out.println(heapsize);
heapSort(a,heapsize); //递归创建最大堆 知道堆的大小为0
}
public static void adjust_heap(int[] a,int heapsize){
int maxnum = a[0];
a[0]=a[heapsize-1];
a[heapsize-1]=maxnum; //交换头节点和尾节点 此时尾节点最大
}
}
| 平均时间复杂度 | 最好情况 | 最坏情况 | 辅助空间 |
|---|---|---|---|
| O(nlog2n) | o(nlog2n) | O(nlog2n) | O(1) |
①. 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
②. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(log2n);
③. 堆排序的过程由n次第②步完成, 时间复杂度为O(nlog2n).
第一个n是堆中根节点个数 第二个n是堆调节的次数
希尔排序
是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
- 选择增量序列 初值为数组长度的一半
- 按增量的个数k对序列进行k趟排序交换
- 每一趟排序的增量为当前的gap，将序列划分成若干长度为m的子序列
如 (13,55,38,76)(27)
分别对各个子表进行直接插入排序仅当gap为1的时候相当于一个有一定顺序的序列然后进行直接插入排序。
选择排序
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n^2) | o(n^2) | O(n^2) | O(1) |
1、基本思想
选择排序的基本思想：比较 + 交换。
在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
2、算法描述
①. 从待排序序列中，找到关键字最小的元素；
②. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
③. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
3.代码实现
public static void selectionSort(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[j] < arr[min]){
min = j;
}
}
if(min != i){
int temp = arr[min]; //交换操作
arr[min] = arr[i];
arr[i] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
}
排序慢，不稳定，但不需要额外空间
