数据结构-排序(冒泡，选择，插入，希尔，快排，归并，堆排)

排序

概念：排序就是将一组杂乱无章的数据按照一定的规律（升序或降序）组织起来。

小知识

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定的排序能变成不稳定的，而不稳定的排序不能转换成稳定的排序

时间复杂度：对排序数据的总的操作次数。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序

问题：假设有n个数，要进行升序排序

冒泡排序

通过两两比较的方式，找到两个间较大的数并进行交换，与下一个数进行比较，直到找到最大的数，放在n的位置，这是一趟，下一趟还是同样的思路，找到第二大的数，放在n-1的位置，依次下去，总共要走n-1趟，因为最后一趟已经排好了。

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

###动图演示

代码实现

public class BubbleSort {private  static void Swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}public static void main(String[] args) {int[] array={9,8,7,6,5,4,3,2,1,0,15,1,16};//最后一趟不用排for (int i = 0; i <array.length-1 ; i++) {//定义标志，不需要进行交换的，flg不需要改，需要交换的flg置为true，可减少交换的次数从而提高效率boolean flg=false;//j为需要进行比较的数的个数for (int j = 0; j <array.length-1-i ; j++) {if(array[j]>array[j+1]){Swap(array,j,j+1);flg=true;}}if(!flg){break;}}System.out.println("冒泡排序"+ Arrays.toString(array));}
}

选择排序

在区间[0,n-1] 中找到最小的值放在下标为0的位置，在进行交换，接着在 [1,n-1] 的区间上找最小的数，在进行交换，也就是有序区间不动，对于无序区间进行比较，依次下去，直至全部有序
时间复杂度：O(N^2)`

空间复杂度： 没有申请额外的空间O(1)

稳定性：不稳定

动图演示

代码实现

public class SelectSort {public static void main(String[] args) {int[] arr={15,65,48,1,30,6,51,46,15,153,5};int minIndex=0;//i~N-1//0~n-1//1~n-1//2~n-1//....for (int i = 0; i < arr.length; i++) {//初识状态下默认0下标的值最小，后进行比较，再重置minIndex的下标minIndex=i;//j注意是i的后一个for (int j = i+1; j <arr.length ; j++) {if(arr[j]<arr[minIndex]){minIndex=j;}}swap(arr,i,minIndex);}System.out.println("选择排序"+ Arrays.toString(arr));}private  static void swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}
}

插入排序

实际中我们玩扑克牌时，就用了插入排序的思想。

思想：

• 认为第一个数已经是有序的
• 取出下一个元素（也就是下标为1的数），从后往前比较
• 如果该元素（已排序）大于新元素，将该元素移至下一位置
• 重复以上操作，直到找到已排序的元素小于或等于新元素的位置
• 将该元素插入到该位置后

时间复杂度：O(N^2)

空间复杂度 ：O(1)

稳定性：不稳定

动图演示

代码实现

public class InsertSort {public static void main(String[] args) {int[] array={9,8,7,6,5,4,3,2,1,0};if(array==null||array.length<2){return;}for(int i=1;i<array.length;i++){int tmp=array[i];int j=i-1;//0~i-1有序了，新来的数是i位置的数，向左看,对应j+1的位置for(;j>=0;j--){if(array[j]>tmp){array[j+1]=array[j];}else {array[j+1]=tmp;break;}}array[j+1]=tmp;}System.out.println("直接插入排序"+ Arrays.toString(array));}
}

希尔排序

是直接插入排序的优化版，希尔排序又叫缩小增量排序
先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

时间复杂度 ：O(N^1.25)

空间复杂度：O(1)

稳定性: 不稳定

由于gap的划分有多种，所以时间复杂度不好计算，选取的是平均的时间复杂度

当gap==1时，用直接插入排序，因为此时的数据已经趋于有序，对于已经趋于有序的数据，直接插入排序很快

动图演示

代码实现

public class ShellSort {public static void main(String[] args) {int[] array={9,8,7,6,5,4,3,2,1,0};int gap=array.length;while(gap>1){//缩小增量gap/=2;shell(array,gap);}System.out.println("希尔排序"+ Arrays.toString(array));}public static void shell(int[] array,int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0; j-=gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {array[j + gap] = tmp;break;}}array[j + gap] = tmp;}}
}

快速排序

基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。使用了分治的思想

三数取中找基准

• 左边的数比右边小，分别讨论中间值处于哪个位置，找到中间值
• 右边的数比左边小，分别讨论，找到中间值

挖坑法

• 先将最左边第一个数据存放在临时变量key中，形成一个坑位
• 右边先出发找到小于key的值，然后将该值丢到坑中去，此时形成一个新坑位
• 左边后出发找到大于key的值，将该值丢入坑中去，此时又形成一个新的坑位
• 一直循环重复1 2 3步
• 直到两边相遇时，形成一个新的坑，最后将key值丢进去 这样key就到达了正确的位置上了

总结：左边找大，右边找小，直到两者相遇，把key值扔进去

时间复杂度：O(N*logN)
空间复杂度：O(logN)~O(N)
稳定性：不稳定

动图演示

代码实现(递归)

public class QuickSort {public static void main(String[] args) {int[] array={9,8,7,6,5,4,3,2,1,0};quick(array,0,array.length-1);}//递归实现private static void quick(int[] array,int start,int end){if(start>=end){return;}if(end-start+1<=7){InsertRange(array,start,end);return;}int midIndex=GetMiddleNum(array,start,end);Swap(array,start,midIndex);int pivot=Partition(array,start,end);//递归左边quick(array,start,pivot-1);//递归右边quick(array,pivot+1,end);System.out.println("快速排序"+ Arrays.toString(array));}private static void InsertRange(int[] array,int start,int end){for(int i=start+1;i<=end;i++) {int tmp = array[i];int j = i - 1;for (; j >= start; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {array[j + 1] = tmp;break;}}array[j+1]=tmp;}}//挖坑法//由三数取中找到基准在开始位置//基准位置挖个坑//从左往右找比坑大的数，放进坑里，形成新的坑//从右往左找比坑小的数，放进坑里，形成新的坑//直到左右指针相遇//此时的位置作为中心去递归左边和右边private static int Partition(int[] array,int left,int right){int tmp=array[left];while(left<right){//右边找小，找到了就交换，没找到就--while(left<right&&array[right]>=tmp){right--;}array[left]=array[right];//左边大，找到了就交换，没找到就++while (left<right&&array[left]<=tmp){left++;}array[right]=array[left];}array[left]=tmp;return left;}//三数取中private static int GetMiddleNum(int[] array,int left,int right){int mid=(left+right)/2;//两种情况：左边的数比右边小，分别讨论中间值处于那个位置，找到中间值if(array[left]<array[right]){if(array[mid]<array[left]){return left;}else if(array[mid]>array[right]){return right;}else {return mid;}}else {//右边的数比左边小if(array[mid]>array[right]){return mid;}else if(array[mid]<array[left]){return mid;}else{return left;}}}//交换两个数private  static void Swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}}

归并排序

外部排序：排序过程需要在磁盘等外部存储进行的排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定
根据等号判断，当s1，s2是相等时，就是不稳定的
而稳定的可以变成不稳定的，可以说明是稳定的排序

动图演示

代码实现

public class MergeSort {public static void main(String[] args) {int[] array={100,99,8,4,16,56,1,56,4,6,5,2,3,23,32,68};//mergeSort(array,0,array.length-1);mergeSortNor(array,0,array.length-1);System.out.println("合并排序"+ Arrays.toString(array));}//递归实现private static void mergeSort(int[] array, int left, int right) {if(left>=right){return;}//分治算法//递归分解int mid=(left+right)/2;mergeSort(array,left,mid);mergeSort(array,mid+1,right);//依次合并merge(array,left,mid,right);}private static void merge(int[] array, int left, int mid, int right) {//创建临时数组储存数据//合并两个有序数组//依次比较放进临时变量里int[] tmp=new int[right-left+1];int s1=left;int e1=mid;int s2=mid+1;int e2=right;int k=0;while(s1<=e1&&s2<=e2){if(array[s1]>=array[s2]){tmp[k++]=array[s2++];}else {tmp[k++]=array[s1++];}}//处理剩下的，放进临时数组里while (s1<=e1){tmp[k++]=array[s1++];}while (s2<=e2){tmp[k++]=array[s2++];}//保证tmp数组是有序的for (int i = 0;  i<k ; i++) {//没有加left步会覆盖原来的数据//一开始的left为0加了相当于没加//处理完左边，右边的就是left变成了mid+1array[i+left]=tmp[i];}}private static void mergeSortNor(int[] array, int left, int right) {//每个数都看成一个个有序的数int gap=1;//按照gap*2的步距去进行排序//当gap比数组长度大的时候不成立while(gap<array.length){for (int i = 0; i < array.length; i+=gap*2) {int start=i;int mid=start+gap-1;//考虑越界情况if(mid>=array.length){mid=array.length-1;}//考虑越界情况int end=mid+gap;if(end>=array.length){end=array.length-1;}merge(array,start,mid,end);}gap*=2;}}
}

堆排序

小根堆：在逻辑上的二叉树结构中,根结点<子结点,总是最小的,并且在堆的每一个局部都是如此
大根堆：在逻辑上的二叉树结构中,根结点>子结点,总是最大的,并且在堆的每一个局部都是如此

• 将待排序的序列构造成一个大堆，根据大堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；
• 将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大堆；
• 重复步骤2，如此反复，从第一次构建大堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大堆的尾部。最后，就得到一个有序的序列了。

结论： 排升序，建大堆； 排降序，建小堆

向下调整算法的基本思想：

• 从根节点开始，选出左右孩子值较大的一个
• 如果选出的孩子的值大于父亲的值，那么就交换两者的值
• 将大的孩子看做新的父亲，继续向下调整，直到调整到叶子节点为止

时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

动图演示

代码实现

 //建大堆//时间复杂度为O(N)public void creatHeap() {for (int parent = (this.elem.length-1-1)/2; parent >=0 ; parent--) {siftDown(parent,this.usedsize);//为什么有两个参数，一个去进行向下调整，一个作为判断是否已经调整结束的标志，当child>usedsize时说明已经调完了}}
//左孩子等于父亲节点*2+1，右孩子等于父亲节点*2+2
//向下调整法，找到最后一个父亲节点，直到parent==0;//时间复杂度为树的高度O(logN)private void siftDown(int parent, int usedsize) {int child=2*parent+1;//调大堆while (child<usedsize){//判断右孩子坐标的合法性，并找到最大的孩子if(child+1<usedsize&&elem[child]<elem[child+1]){child++;}//如果孩子节点比父亲节点大，交换，因为还要继续向下调整，让孩子节点成为父亲节点，继续判断//当子树已经调整好时，父亲节点比左右孩子都大时，说明下面已经调整好了，不用再调整了if(elem[child]>elem[parent]){swap(elem,child,parent);parent=child;child=2*parent+1;}else{break;}}}public void heapsort() {int end = usedsize - 1;while (end > 0) {swap(elem,0,end);siftDown(0,end);end--;}}