目录
一：插入排序
1）直接插入排序insertSort
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。
思路：将一组待排序的序列，第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
public class insertSort {
public static void insertSort (int[] arr){
for(int i=1;i<arr.length;i++){
int key = arr[i];
int end=i-1;
while(end>=0 && arr[end]>key){//注意：因为&&逻辑运算符具有短路特性，左端条件为假直接不成立，因此顺序不可变
arr[end+1] = arr[end];//把end处位置放到后面，实现交换的一半
end--;
}
arr[end+1]=key;//此时end+1处也就是arr（i-1）处，上方只交换了一半，完成下一半
}
}
public static void printArray(int[] array){
for(int i=0;i< array.length;i++){
System.out.print(array[i]+" ");
}
}
public static void main(String[] args) {
int[] array ={12,11,23,25,22,36};
insertSort(array);
printArray(array);
}
}空间复杂度：o(1)，没有多余的空间
时间复杂度：o(N^2) 。
最优有序或者接近有序o(N),只用外部循环，数据量小；最差比较乱，随机
应用场景：数据量比较小或者接近有序
稳定性：稳定
2）希尔排序shellSort
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
思路：希尔排序是将待排序的数组元素 按下标一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
//2）希尔排序
public static void shellSort(int[] array){
int gap = array.length;
while(gap>0){
gap=gap/3+1;
for(int i=gap;i<array.length;i++){
int key = array[i];
int end = i-gap;
while(end>= 0 && key < array[end]){
array[end+gap] = array[end];
end -= gap;
}
array[end+gap] = key;
}
gap--;
}
}空间复杂度：o(1)，没有多余的空间
时间复杂度：
希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。虽然有很多论文专门研究过不同的增量对希尔排序的影响，但都无法证明某个增量是最好的。
1) 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2) 最坏情况
：
O(n^2)。应用场景：数据量大且接近凌乱
稳定性：不稳定
一个排序算法是否稳定就看是否有间隔的排序，间隔一定不稳定。稳定即
排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同
二：选择排序
1）选择排序selectSort
选择排序是一种简单直观的排序算法
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。
1）从arr[0]开始排
public static void selection_sort(int[] arr) {
int len = arr.length-1;
for (int i = 0; i < len ; i++) {
int min = i;
for (int j = i + 1; j <= len; j++)
if (arr[min] > arr[j]){//两两比较找到最小的
min = j;
}
swap(arr,i,min);
}
}2）从最后一个开始排
public static void selectSort(int[] arr){
int end = arr.length-1;
while(end>0){
int pos=0;
for(int i=0;i<=end;i++){//循环遍历找到最大的一个数
if(arr[pos]<arr[i]){
pos=i;
}
}
if(pos!=end){//如果最大的不等于end,则交换
swap(arr,pos,end);
}
end--;//end减去已经排好的这个，再继续找
}
}空间复杂度：o(1)，没有多余的空间
时间复杂度：o(N^2)
1) 最好情况：o(N^2)
2) 最坏情况
：
o(N^2)应用场景：无
稳定性：不稳定
缺陷：在找最小元素时前面的元素已经比较过了，会存在重复比较，所一出现了堆排序。
2）堆排序heapSort
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构，并同时满足：子结点的索引总是小于（或者大于）它的父节点。堆排序也是有用到选择最大的或者最小的所以归为选择排序。
最后一个
叶子节点
的索引值是n-1，它的父节点索引值是[(n-1)-1]/2 = n/2 -1
① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
public static void heapSort(int[] arr){
//第一步：建堆
int size = arr.length;
int lastleaf = ((size-2)>>>1);
for(int root=lastleaf;root>=0;root--){
shiftDown(arr,size,root);
}
//第二步：利用堆删除的思想排序
int end = size-1;
while(end>0){
swap(arr,0,end);//用堆顶元素与堆中最后一个元素交换
shiftDown(arr,end,0);//将堆元素向下调整
end--;//有效元素减少一个
}
}
public static void shiftDown(int[] arr,int size,int parent){
int child = parent*2+1;//先标记左孩子，可能有左没有右
while(child<size){//如果条件存在则左孩子一定存在
if(child+1<size && arr[child+1]>arr[child]){//右孩子存在的情况下找大的
child += 1;
}
//检验parent是否满足堆的特性
if(arr[parent] < arr[child]){//不符合则调整
swap(arr,parent,child);
parent = child;
child = parent*2+1;
}else{//符合直接退出
return;
}
}
}
public static void swap(int[] arr,int a,int b){
int str = arr[a];
arr[a] = arr[b];
arr[b] = str;
}空间复杂度：o(1)，没有多余的空间
时间复杂度：因为堆排序无关乎初始序列是否已经排序已经排序的状态，始终有两部分过程，
构建初始的大顶堆
的过程时间复杂度为O(n)，
交换及重建大顶堆的过程中，需要交换n-1
次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn)1) 最好情况：O(nlogn)
2) 最坏情况
：
O(nlogn)应用场景：无
稳定性：不稳定
堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1…n]中选择最大记录，需比较n-1次，然后从R[1…n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。
三：直接排序
1）冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
//冒泡排序
public static void bubbleSort(int[] arr){
//冒泡趟数
for (int i = 0; i < arr.length-1; i++) {
//比较次数。。上下都要减1，下面可以减i,也可以不减
for(int j = 0; j < arr.length-1-i; j++){
if(arr[j] > arr[j+1]){
swap(arr,j,j+1);
}
}
}
}空间复杂度：o(1)，没有多余的空间
时间复杂度：因为是要挨个比较，并且每层循环都需要走满，才能将序列变得有序，因此时间复杂度为O(N^2)
应用场景：数据量较大时，时间复杂度已经随之水涨船高了，不考虑使用
稳定性：因为需要挨个进行比较，且挨个进行交换，因此冒泡排序是稳定的
2）快速排序
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用
快速排序思想—-分治法！
1~递归
//递归版
public static void quickSort(int[] arr,int left,int right){
if(right - left > 1){
int div = partition(arr,left,right);
quickSort(arr,left,div);//左侧[left,div)
quickSort(arr,div+1,right);//右侧[div+1,right)
}
}
2~非递归——栈
//非递归版快速排序
public static void quick_Sort(int[] arr,int left,int right){
Stack<Integer> s = new Stack<>();
s.push(left);//先放左，再放右
s.push(right);//先出右，再出左
while(!s.empty()) {
right = s.pop();//右 2div
left = s.pop();//左 2left
if (right - left > 1) {
//将left和right分割，将区间分为了[left,div)和[div + 1,right)
int div = partition1(arr, left, right);
s.push(div + 1);//div+1,right,left,div
s.push(right);
s.push(left);
s.push(div);
}
}
}从快速排序的算法思想上分析，快排时间复杂度的根本在于我们选择的
基准值
，基准值越趋向于这一组数据的中间数值，那么它的排序效率就越高
- 我们可以假设，此时我们取到了一组数据，它接近有序，并且我们运气不好取到了最大或者最小的元素，每次在进行分割时，左侧或者右侧永远只有一个元素，那么，它的分割场景就类似于一棵递增顺序（或者递减）查找树，它要么只有左子树，要么只有右子树（O(N ^ 2) ）
- 那假如，这一组数据是无序的并且我们的运气好，每次取到的基准值都比较靠近相应的中间数值，那么它的递归图像，就像是一棵二叉平衡树，那么这就是两种时间复杂度了(O(NlogN))
我们能做的就是，尽可能的取到靠近的中间数值的那个元素当做基准值，那么它的时间复杂度就会稳定在最最优情况下
因此–>找一个基准值的方法
三数取中法：一次性去3个数，最左，最右，中间，比较这三个数据取中间的那个
//三数取中法：找基准值
public static int getMidIndex(int[]arr,int left,int right){
int mid = left + (right-left)>>1;
if(arr[left] < arr[right-1]){//left<right
if(arr[mid] < arr[left]){//mid<left
return left;
}else if(arr[mid] > arr[right-1]) {//mid>right
return right - 1;
}else{
return mid;
}
}else{//left>right
if(arr[mid] > arr[left]){//mid>left
return left;
}else if(arr[mid] < arr[right-1]) {//mid<right
return right - 1;
}else{
return mid;
}
}
}
方法一：Hoare版本 霍尔划分（提出快排思想的大佬）
public static int partition(int[] array, int left, int right){
/**
用三数取中法找到index，在将其放到最后一个位置，就可以不用改动代码
int index = getMidIndex(array,left,right);
if(index != right - 1){
swap(array,index,right - 1);
}
*/
int key = array[right-1];//设最右数为基准值
int begin = left;
int end = right-1;
while(begin < end){
//基准值取在右侧，因此begin先走，找比基准值大的元素
while(begin < end && array[begin] <= key){
begin++;
}
//end再走，找比基准值小的，并停下来
while(begin < end && array[end] >= key){
end--;
}
//如果begin和end在同一个位置就不用交换了
if(begin != end){
swap(array,begin,end);
}
}
//当begin和end走到同一个位置时，和此时数组的最后一个元素交换位置
swap(array,begin,right - 1);
return begin;
}
方法二：挖坑法
public static int partition2(int[] array,int begin,int end){
{
int key = array[begin];//选取第一个数为基准值
while(begin<end)//循环条件
{
while(begin<end && array[end] >= key)//从后向前找第一个小于基准值的数
end--;
array[begin] = array[end];//放到begin位置
while(begin<end&&array[begin] <= key)//从前向后找第一个大于基准值的数
begin++;
array[end] = array[begin];//放到end的位置
}
//此时跳出循环，则begin和end相遇
array[begin] = key;//将基准值放入该位置
return begin;//返回当前基准值的位置，以便递归划分
}
}
方法三：前后标记法
//前后指针法
public static int partition2(int[] array,int left,int right){
int index = getMidIndex(array,left,right);
if(index != right - 1){
swap(array,index,right - 1);
}
int key = array[right - 1];//选取最后一个数为基准值
int cur = left;//前指针
int prev = cur - 1;//后指针
while(cur < right){
if(array[cur] < key && ++prev != cur){
//从前往后找比key小的数并且判断++prev的值是否等于cur
swap(array,cur,prev);
}
cur++;
}
if(++prev != right - 1) {
swap(array, prev, right - 1);
}
return prev;
}性能分析
时间复杂度：
- 快速排序的时间复杂度是O(NlogN)
- 但是这是最好情况下，如果是最坏情况下，它的时间复杂度是O(N ^ 2)
空间复杂度：O(NlogN)
应用场景：和上面的排序算法最大的不同是，数据越无序越好，快速排序的时间复杂度就会降低，效率越高
稳定性：因为是交换排序，并且有间隔交换，因此是不稳定的
public class quickSort {
public static void main(String[] args) {
int[] arr = {12,11,2,13,22,1,5,34};
quickSort(arr,0,arr.length);
for(int i : arr){
System.out.print(i+" ");
}
}
public static void quickSort(int[] arr,int left,int right) {
if(right-left>1){
int div = partition1(arr,left,right);
quickSort(arr,left,div);//左闭右开
quickSort(arr,div+1,right);
}
}
public static int partition1(int[] arr,int left,int right){
int index = getMidIndex(arr,left,right);
if(index!=right-1){
swap(arr,index,right-1);
}
int key = arr[right-1];//取基准值
int begin = left;
int end = right-1;
while(begin<end){
while(begin<end && arr[begin]<=key){
begin++;//从左到右找比基准值大的
}
while(begin<end &&arr[end]>=key){
end--;//从右到左找比基准值小的
}
if(begin != end){//交换
swap(arr,begin,end);
}
}
swap(arr,begin,right-1);//相遇，基准值和中间的交换
return begin;//返回中间的
}
public static int partition2(int[] array,int begin,int end){
int key = array[begin];//选取第一个数为基准值
while(begin<end)//循环条件
{
while(begin<end && array[end] >= key)//从后向前找第一个小于基准值的数
end--;
array[begin] = array[end];//放到begin位置
while(begin<end&&array[begin] <= key)//从前向后找第一个大于基准值的数
begin++;
array[end] = array[begin];//放到end的位置
}
//此时跳出循环，则begin和end相遇
array[begin] = key;//将基准值放入该位置
return begin;//返回当前基准值的位置，以便递归划分
}
public static int getMidIndex(int[] arr,int left,int right){
//一次性取3个数，比较最左最右中间这三个数，取中间值
int mid = left+(right-left)>>1;
if(arr[left] < arr[right-1]){
if(arr[mid] < arr[left]){
return left;
}else if(arr[mid] > arr[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(arr[mid] > arr[left]){
return left;
}else if(arr[mid] < arr[right-1]){
return right-1;
}else{
return mid;
}
}
}
public static void swap(int[] arr,int a,int b){
int str = arr[a];
arr[a] = arr[b];
arr[b] = str;
}
}
四：归并排序
归并排序采用的是
分治
思想。
基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
- 比如有两个已经排序好的数组，如何将他归并成一个数组？
我们可以
开辟一个临时数组
来辅助我们的归并。也就是说他比我们插入排序也好，选择排序也好多使用了存储的空间，也就是说他需要o（n）的额外空间来完成这个排序。只不过现在计算机中时间的效率要比空间的效率重要的多。无论是内存也好还是硬盘也好可以存储的数据越来越多，所以设计一个算法，时间复杂度是要优先考虑的。
public class mergeSort {
public static void main(String[] args){
int[] arr={11,32,24,33,45,22,3,67,5,1,244,566,54,32};
mergeSort(arr);
for (int i : arr){
System.out.print(i+" ");
}
}
public static void mergeSort(int[] arr){
int[] tmp = new int[arr.length];
mergeSort(arr,0,arr.length,tmp);
}
public static void mergeSort(int[] arr,int left,int right,int[] tmp){
if(right-left>1){
int mid = left+((right-left)>>1);
mergeSort(arr,left,mid,tmp);
mergeSort(arr,mid,right,tmp);
mergeDate(arr,left,mid,right,tmp);
System.arraycopy(tmp,left,arr,left,right-left);
}
}
public static void mergeDate(int[] arr,int left,int mid,int right,int[] tmp){
int begin1=left,end1=mid;
int begin2=mid,end2=right;
int index = left;
while(begin1<end1 && begin2<end2){
if(arr[begin1] <= arr[begin2]){
tmp[index++] = arr[begin1++];
}else{
tmp[index++] = arr[begin2++];
}
}
while(begin1<end1){
tmp[index++] = arr[begin1++];
}
while(begin2<end2) {
tmp[index++] = arr[begin2++];
}
}
}
1~递归版归并排序
private static void mergeSort(int[] array,int left,int right,int[] temp){
//判断是否满足条件（只有一个元素时，默认时有序的）
if(right - left > 1){
int mid = left + ((right - left) >> 1);//找中间元素的下标
//将原数组分为了两部分[left,mid) 和 [mid,right)
mergeSort(array,left,mid,temp);//进行左半部分的递归
mergeSort(array,mid,right,temp);// 进行右半部分的递归
mergeDate(array,left,mid,right,temp);//开始进行归并
//将临时数组当中的元素往原数组当中拷贝
System.arraycopy(temp,left,array,left,right - left);
}
}
//对归并排序方法体进行包装一下,否则参数太多了不方便调用
public static void mergeSort(int[] array) {
int[] temp = new int[array.length];
mergeSort(array, 0, array.length, temp);
}
2~非递归版——循环
//非递归实现——循环
//循环的思想就是利用一个gap，充当递归分割的过程，从单个元素开始，一直到最后一个结束
//以此类推，直到将数组只能分为两个之后结束
public static void merge_Sort(int[] array){
int size = array.length;
//创建一个临时数组
int[] temp = new int[size];
int gap = 1;
while (gap < size){
for(int i = 0;i < size;i += 2 * gap){
int left = i;
int mid = left + gap;
int right = mid + gap;
//如果mid大于size，说明已经到数组最后一个元素之外了
if(mid >= size){
mid = size;
}
//如果right大于size，说明已经到数组最后一个元素之外了
if(right >= size){
right = size;
}
//进行合并
mergeDate(array,left,mid,right,temp);
}
//将临时数组中的元素拷贝到原数组当中
System.arraycopy(temp,0,array,0,size);
gap *= 2;
}
}
归并排序：
public static void mergeDate(int[] arr,int left,int mid,int right,int[] temp){
int begin1 = left;int end1 = mid;//第一个数组的开始结尾
int begin2 = mid;int end2 = right;
int index = left;//临时数组的起始下标
while (begin1<end1 && begin2<end2){
if(arr[begin1] <= arr[begin2]){
temp[index] = arr[begin1];
index++;
begin1++;
}else{
temp[index] = arr[begin2];
index++;
begin2++;
}
}
while(begin1<end1){
temp[index] = arr[begin1];
index++;
begin1++;
}
while(begin2<end2){
temp[index] = arr[begin2];
index++;
begin2++;
}
}时间复杂度：归并排序的空间复杂度和快速排序的最优情况类似，只是减少基准值的那一部分，因此它的时间复杂度也为O(NlogN)
空间复杂度：因为借用了一段和原数组大小相等的空间，因此空间复杂度也为O(N)
应用场景：归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题
稳定性：稳定
