常用排序算法

排序

插入排序、冒泡排序、归并排序、快速排序，选择排序 算法的比较，需要从额外空间消耗，平均时间复杂度和最差时间复杂度等方面去比较他们的优缺点

插入排序

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）的时间复杂度。代价是需要额外的内存空间。

1. 基本思想
   把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

2、算法描述

• 自上而下的递归
• 自下而上的迭代
  一、递归法（假设序列共有n个元素）：

①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③. 重复步骤②，直到所有元素排序完毕。

归并实际上要做两件事
分解：采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列
分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

合并：分别把从左右子序列的编号对比 较小的就提出来放入新开辟的数组中已放入的元素不再参与比较，直到任意一个子序列的元素都放入新数组中就结束，再把另一个数组剩余的元素放进新数组。

image

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，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序通过分之策略来吧一个序列分成两个子序列

1. 挑选一个元素作为基准
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（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 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。

image
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

1. 选择增量序列 初值为数组长度的一半
2. 按增量的个数k对序列进行k趟排序交换
3. 每一趟排序的增量为当前的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));
        }
    }
}

排序慢，不稳定，但不需要额外空间