1.排序2.选择排序
2.1.直接选择排序2.2双向选择排序2.3堆排 3.插入排序
3.1直接插入排序3.2折半插入排序3.3.希尔排序 4.归并排序5.交换排序
5.1冒泡排序5.2快速排序 6.排序总结
1.排序1.排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。通常排序指的是升序排列。
2.稳定性：
待排序序列中存在值相等的元素，经过排序之后，相等元素之间的原有顺序保持不变，就叫稳定的排序算法。
稳定性的现实意义：假设现在商城系统，要求按照订单金额排序，订单默认都是按照下单时间来进行创建的，此时稳定的排序算法就非常重要，相同的金额订单仍然是按照时间先后来排序(稳定的排序算法)。
3.排序算法的分类：
(1)基于比较内部排序：
(2)外部排序：需要借助硬盘等辅助介质进行的排序操作(大数据排序，数据大到内存放不下)，例如，桶排序(基于归并思想)、计数排序、基数排序。
2.选择排序 2.1.直接选择排序1.直接选择排序：
每次在一组待排序的数据中选择最大(最小值)的一个元素，存放在无序区间的最后或最前，直到全部待排序元素排列完毕为止。
2.所有的排序算法，一定要注意变量和区间的严格定义。
3.直接选择排序是一个不稳定的排序算法。
在[9,2,5a,7,5b,4,3,6]当交换5a和4这两个元素时，5a就换到了5b的后面。
4.直接选择的时间复杂度O(n^2)。
5.代码实现：
//直接选择排序
public static void selectionSort(int[] arr) {
//每次从待排序数组中选择最小值放在待排序数组的最前面
//最外层的for循环表示要执行的总次数，类似于冒泡，当剩下最后一趟时，整个数组已经有序
//默认第一个元素就是有序的
//已经有序的集合[0,i)
//待排序的集合[i+1,n)
//每进行一趟排序，最小值就放在了数组的最前面，已经有序的集合个数+1
//待排序集合元素个数-1
for (int i = 0; i < arr.length - 1; i++) {
//min变量存储了最小值下标
int min = i;
//每次从无序区间中选择最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//此时min就存储了最小值下标，就把min对应的元素换到无序区间的最前面
swap(arr, i, min);
}
}
2.2双向选择排序
1.每次从无序区间中选出一个最大值和最小值，分别放在取件单最前面和最后面，一趟下来就有两个元素到达了最终位置，理论上比直接选择排序快了一倍左右。
2.代码实现：
public static void selectionSortOP(int[] arr){
int low=0,high=arr.length-1;
//有序区间[0,low+1)
while(lowarr[max]){
max=i;
}
if (arr[i]
2.3堆排
1.堆排的基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大数，而是通过堆排来选择无序区间的最大数。
2.排升序要建大堆，排降序要建小堆。
3.时间复杂度：O(nlogn)
4.代码实现;
public static void heapSort(int[] arr) {
// 1.将任意数组调整为最大堆
// 从最后一个非叶子节点开始
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
siftDown(arr,i,arr.length);
}
// 依次将堆顶元素和最后位置元素交换
// 最开始待排序数组[0...arr.length - 1] 已排序的数组[]
// 交换一个之后 [0...arr.length - 2] [arr.length- 1]
// 交换第二个值之后 [0..arr.length - 3] [arr.length - 2,arr.length - 1]
// 此处终止条件不用写i = 0 ，当整个待排序数组就剩一个元素时，其实整个数组已经有序
for (int i = arr.length - 1; i > 0; i--) {
swap(arr,0,i);
siftDown(arr,0,i);
}
}
private static void siftDown(int[] arr, int i, int n) {
// 仍然存在子树
while ((2 * i) + 1 < n) {
int j = 2 * i + 1;
// 右孩子存在且大于左子树值
if (j + 1 < n && arr[j + 1] > arr[j]) {
j = j + 1;
}
// j对应的下标就是左右子树的最大值
if(arr[i] >= arr[j]) {
break;
}else {
swap(arr,i,j);
i = j;
}
}
}
private static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
3.插入排序
3.1直接插入排序
1.插入排序类比打扑克牌，整理牌的时候都是把乱的牌向已经整理好的牌中插入-天然的插入排序。
2.直接插入排序：
每次选择无序区间的第一个元素，插入到有序区间的合适位置，不断重复此流程，直到整个数组有序。
3.插入排序和选择排序最大的不同在于，若arr[j]>arr[j-1],循环可以直接终止，j-1已经是有序集合的元素。
4.插入排序在近乎有序的数组中，性能非常好，插入排序经常作为高级排序算法的优化手段，插入排序在小数据规模上的性能非常好。
5.直接插入排序是一个稳定的排序算法，arr[j]>=arr[j-1]循环就 终止了，因此相等元素排序前和排序后的次序不会发生变化。
6.代码实现：
public static void insertionbase(int[] arr){
//有序区间[0,i)
//默认第一个元素就是有序
for (int i = 0; i 0 && arr[j] arr[j - 1]此时，循环直接终止
// // j - 1已经是有序区间元素，大于前面的所有值
// if (arr[j] < arr[j - 1]) {
// swap(arr,j,j - 1);
// }else {
// // arr[j] >= arr[j - 1],此时j对应的元素已经到达了正确的位置
// break;
// }
}
}
}
3.2折半插入排序
1.由于插入是在有序区间的插入，因此我们可以使用二分查找的办法来快速定位插入的位置。
2.和直接插入的思想相同，等于的值放在左区间保证稳定性。
3.当n比较大时，直接插入排序有序区间中遍历插入位置O(n),一个个比较交换。折半插入排序有序区间中折半查找O(logn)一次比半个区间，找到插入位置后元素的搬移折半查找元素的搬移次数==交换次数，因为无论哪种插入排序方法，元素插入的位置都是一样的。
public static void insertionSortBS(int[] arr){
for (int i = 1; i < arr.length; i++) {
//无序区间第一个值
int val=arr[i];
//有序区间[0,i)
int low=0;
int high=i;
while(low>1;
//将相等的值放在左半区间，保证稳定性
if (val >=arr[mid]){
low=mid+1;
}else{
//右区间取不到，不用-1
high=mid;
}
}
//数据搬移
for (int j = i; j >low; j--) {
arr[j]=arr[j-1];
}
//low就是元素插入位置
arr[low]=val;
}
}
3.3.希尔排序
1.希尔排序：
先选定一个整数gap,将待排序的数据中所有记录按照gap分组，所有距离为gap的数据放在同一组，将组内元素排序，然后不断缩小gap的大小直到变为1，当gap为1时，整个数组已经近乎有序，调用普通插入排序即可。
2.待排序数组为[9,1,2,5a,7,4,8,6,3,5b]
gap是动态步长，相同距离的元素分为同一组，然后在组内排序，组内排好序，gap/=2, 重复上述流程，当gap=1，整个数组上进行插入排序。分组的个数和gap大小相同。
n=10，一般就是gap=n/2,直到等于1.
(1)gap=n/2=5
待排序数组：[9,1,2,5a,7,4,8,6,3,5b]
按照步数为5将原数组分组：
[9,4] ,[1,8],[2,6],[5a,3],[7,5b],
组内排好序：
[4,9],[1,8],[2,6],[3,5a],[5b,7]
即：[4,1,2,3,5b,9,8,6,5a,7]
(2)gap=gap/2=2
数组：[4,1,2,3,5b,9,8,6,5a,7]
按照步数为2将数组分组：
[4,2,5b,8,5a],[1,3,6,7,9]
组内排好序:[2,4,5b,8,5a],[1,3,6,7,9]
即：[2,1,4,3,5b,6,5a,7,8,9]
(3)gap=gap/2=1
在[2,1,4,3,5b,6,5a,7,8,9]这个数组上进行插入排序，在近乎有序的数组上进行插入排序，性能非常好。
最终排序结果为：[1,2,3,4,5b,5a,6,7,8,9]
3.希尔排序就是通过不断的将gap变小的过程中，将原数组整理的近乎有序为gap=1，为最后的插入排序打基础。
4.希尔排序是不稳定的排序算法。
5.希尔排序的时间复杂度为O(N^1.2).
6.代码实现:
public static void shellSort(int[] arr){
int gap=arr.length>>1;
while(gap >1){
//不断按照gap分组，组内进行插入排序
insertionSortGap(arr,gap);
gap /=2;
}
//整个数组的插入排序
insertionSortGap(arr,1);
}
private static void insertionSortGap(int[] arr,int gap){
//最外层从gap开始不断走到数组末尾
//i=4
for (int i = gap; i =0说明前面数组还要相同距离的元素，比较arr[j]和arr[j-gap]
for (int j=i;j-gap >=0 && arr[j]
4.归并排序
1.归并排序：
归并排序是建立在归并操作上的一种有效的排序算法，该算法采用分治法的应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使自序列段间有序，若两个有序表合并成一个有序表，称为二路归并。
(1)**归：**将原集合不断拆分，拆分到每个数组只剩下1个元素时，拆分过程就结束。
(2)并：将拆分后小数组不断合并，直到合并到整个数组，此时整个数组已经有序。
(3)合并时，我们创建一个临时数组，大小就和合并后的数组大小元素相同。
(4)拆分是将原数组一分为二，数组左区间为l,右区间r，左半区间[i,mid],右半区间[mid+1,r].
2.归并排序是稳定的排序算法,因为数组拆分不会造成元素顺序打乱，元素的相对位置不会发生移动，当最终合并时，<=值默认放在左区间，所以合并过程也是稳定的。
3.归并排序的时间复杂度为O(nlogn)。拆分过程原数组长度为n，不断拆分数组，将数组一分为2，直到子数组长度为1.总共拆分的次数就是logN.以最终合并过程为例，最终合并的大数组长度为N，遍历N次，才能将数组元素合并完成NlogN.
4.代码实现：
public static void mergeSort(int[] arr){
mergeSortInternal(arr,0,arr.length-1);
}
private static void mergeSortInternal(int[] arr,int l,int r) {
if (r-l+1 <=15){
//拆分后的小区间直接使用插入排序，不再递归
insertbase(arr,l,r);
return;
}
//有溢出风险(r+l)>>1
//l=0,r=8,mid=4
//0+(8-0)/2
int mid=l+((r-l)>>1);
//在拆分后的两个小数组上使用归并排序
//先排序左半区间
mergeSortInternal(arr,l,mid);
//再拍序右半区间
mergeSortInternal(arr,mid+1,r);
//此时左半区间和右半区间已经有序
//arr[mid]左区间的最后一个元素
//arr[mid+1]右区间的第一个元素,arr[mid]
//arr[mid]
//2.不是上来就合并，当两个小区间之前存在乱序时才合并
if (arr[mid] >arr[mid+1]){
merge(arr,l,mid,r);
}
}
private static void merge(int[] arr, int l, int mid, int r) {
//假设此时l=1000,r=2000
//开辟一个大小和合并后数组大小相同的数组
int temp[]=new int[r-l+1];
//将原数组内容拷贝到新数组中
for (int i = l; i <=r ; i++) {
//temp[0]=arr[1000]
//新数组的索引和原数组的索引有l个单位的偏移量
temp[i-l]=arr[i];
}
//遍历原数组，选择左半区间和右半区间的最小值写回原数组
//i对应左半区间的第一个索引
int i=l;
//j对应右半区间的第一个索引
int j=mid+1;
//k表示当前处理到原数组的哪个位置
for (int k = l; k <=r ; k++) {
if (i>mid){
//此时左半区间已经全部处理完毕，将右半区间的所有值写回原数组
arr[k]=temp[j-l];
j++;
}else if (j>r){
//此时右半区间已经全部处理完毕
arr[k]=temp[i-l];
i++;
}else if(temp[i-1]<=temp[j-1]){
arr[k]=temp[i-l];
i++;
}else{
arr[k]=temp[j-l];
j++ ;
}
}
}
public static void mergeSortNonRecursion(int[] arr){
//sz表示每次合并的元素个数，最开始从1个元素开始合并(每个数组只有一个元素)
//第二次循环时，合并的元素个数变成了2(每个数组有2个元素)
//第三次循环时，合并的元素个数就成了4(每个数组有4个元素)
for(int sz=1;sz <= arr.length;sz=sz+sz){
//merge过程，i表示每次merge开始的索引下标
for (int i = 0; i +sz
5.归并排序的衍生问题：
外部排序：排序过程需要在磁盘等外部存储进行的排序。
海量数据处理，此时要排序的数据大小100G，内存只有1G，如何将100G数据进行排序？
(1)先把100G的大文件拆分为200份，每份0.5G。
(2)分别对0.5G的小文件进行内部排序(使用堆排，快排，归并都可以)。
(3)进行200个小文件的merge过程，整个大文件就有序了。
5.交换排序
5.1冒泡排序
1.在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。
2.冒泡排序是稳定的排序算法。
3.冒泡排序的时间复杂度为O(N^2).
public static void bubbleSort(int[] arr) {
// 最外层表示要比较的趟数，此处-1是因为，整个待排序数组剩一个元素时，整个数组已经有序
for (int i = 0; i < arr.length - 1; i++) {
boolean isSwaped = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
isSwaped = true;
swap(arr,j,j + 1);
}
}
if (!isSwaped) {
// 内层循环没有元素交换，整个数组有序
break;
}
}
}
private static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
5.2快速排序
1.快排的核心思想：选取一个分区点(基准值)，将数组分为三部分，基准值之前的数组<基准值<大于基准值，重复进行此操作。默认选择数组的第一个元素作为比较的基准值。
2.快速排序的具体过程：
i是当前正在扫描的元素下标
(1)若arr[i]>v:
(2)若i
(3)若i=v:
分区完成之后，j对应的元素就到达了最终位置，继续在v的区间重复进行快速排序过程即可。
3.快速排序是不稳定的排序算法，分区时，当扫描arr[i]=v，就有可能把一个等于v从前面交换到了后面，分区函数无法保证稳定性。
4.快速排序的时间复杂度为O(nlogn),递归过程中调用分区函数，分区函数的时间复杂度为O(n),递归过程就是不断将原数组根据基准值拆分为数组，优点类似归并排序，递归次数就是递归树的高度logn.
5.快速排序的性能非常高效：
但是当排序数组接近有序时快速排序的性能衰减
经过观察发现在50w个接近有序的数组上，快速排序退化为O(N^2).
为了解决这个问题引进了随机化快排
在数组中随机化选取一个元素作为基准值，平衡左右两个子树的元素个数。
6.代码实现：
public static void quickSort(int[] arr){
quickSortInternal(arr,0,arr.length-1);
}
private static void quickSortInternal(int[] arr, int l, int r) {
//递归终止时，小数组使用插入排序
if (r-l <= 15){
insertbase(arr,l,r);
return;
}
//选择基准值，找到该值对应的下标
int p=partition(arr,l,r);
//在小于基准值区间进行快速排序
quickSortInternal(arr,l,p-1);
//在>=基准值的区间进行快速排序
quickSortInternal(arr,p+1,r);
}
private static int partition(int[] arr, int l, int r) {
//在当前数组中随机选择一个元素值作为基准值
int randomIndex=random.nextInt(l,r);
swap(arr,l,randomIndex);
int v=arr[l];
//arr[l+1...j] =v最开始为空区间[l+1..l+1]=0
for (int i = l+1; i <=r ; i++) {
if (arr[i]
6.排序总结
