十大排序总结：

排序的分类

冒泡排序

冒泡排序（Bubble Sort） 是一种简单直观的排序算法。它重复的走过要排序的数列，一次比较 两个元素，如果顺序错误就把他们交换过来。走访的数列的工作是重复的进行直到没有再需要交换，也就是说数据已经排列完成。这个算法敏子是因为越小的数字会慢慢的”浮到”数列的顶端。

1.算法步骤

比较相邻的元素，如果第一个比第二个大，就交换他们两个。对每一个相邻元素同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

    
/**
   冒泡排序
**/
public static void BubbleSort(Integer []a){
        for(int i= a.length-1;i>0;i--){
            for (int j=0;j<i;j++){
                if (a[j]>a[j+1]){
                ex(a,j,j+1);
                }
            }
        }
    }

    /**
     * @description: 交换数组中的值
     * @author jwz
     * @date: 2022/4/8
     */
    public static void ex(Integer a[], int i,int j){
        int temp ;
        temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }

2.算法分析

是否原地排序算法：

是空间复杂度为O(1)的算法，不牵涉额外得到其他空间

是否稳定：

当数组中出现相同数值的时候并没进行交换，所以是稳定的

比较与交换次数

两层 for 循环第一轮比较 n-1 次，就是比较的是 一次。总比较的次数是 n*(n-1), 时间复杂度是 O (n^2). 当输入的数组为

** 最佳情况：T (n) = O (n) **

每个数只需要交换一次即可

最差情况：T (n) = O (n2)

每个比较都需要进行交换

平均情况：T (n) = O (n2)

选择排序（Selection Sort）

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 {每次选择一个假装是最小的，然后使用一个指针进行记录，每次找到一个最小的，然后与初始值交换}

动图演示

（1）红色表示当前最小的元素

（2）绿色表示正在比较的元素

（3）黄色表示已经排好的元素

上面的看不懂也没关系，结合另外一张图来看一下：

    public static  int [] selectionSort(int [] array){
        if (array.length ==0){
            return  array;
        }
        for(int i=0;i<array.length;i++){
            int minIndex =i;
            for(int j=i;j<array.length;j++){
                if (array[j]<array[minIndex]){
                    minIndex = j;
                }
//                记录的最小值已i进行交换
                ex(array,minIndex,i);
            }
        }
        return  array;
    }


    public static void  ex(int [] array,int i,int j){
     int temp;
     temp =array[i];
     array[i]=array[j];
     array[j]=temp;
    }

算法复杂度：

比较次数：

无论好坏，比较次数一样多，共需要比较 （n-1）+ （n-2）+…+ 2 + 1 = n * (n-1)/2次；

交换次数：

对交换次数而言，最好的时候是0次，

最坏就是每次都要交换， 为n-1次

基于最终的排序时间是比较和交换次数总和，因此，总的时间复杂度依然为O(n^2)，但性能优于冒泡排序。

有N个学生，要跑N-1趟或者是N/2趟

等差数列求和

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

插入排序：

构建有序序列，对于未排序数列数据，在已排列的序列中从后向前进行扫描，找到相应的位置并插入。在实现上采用in-place 排序，从后往前的查找中，需要不断的将已排序的元素逐步向后移动，为新的元素 提供插入空间。

插入排序是一种简单直观且稳定的排序算法
1、把所有的元素分为两组，已经排序的和未有排序的
2、找到未有排序组中的第一个元素，向已经排序的组中进行插入
3、倒序遍历已经排序好的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他元素向后移动一位

算法复杂度

• 在最坏的情况下，数组完全逆序

  这时候插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，以此类推，插入第N个元素，要考虑前 N - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + … + (N - 1)，结果为 N^2 / 2，所以最坏情况下的复杂度为 O(N^2)。

• 最好情况下，数组已经是有序

算法分析：

比较的次数：
（n-1)+(n-2)+(n-3)+……+3+2+1=(n)(n-1)/2
交换的次数：
指的是最坏的情况，就是每一个的元素都要比原来的要小。就是交换的的次数也是一样的
（n-1)+(n-2)+(n-3)+……+3+2+1=(n)(n-1)/2
所以说最后的次数就是两者进行相加
所以复杂度为O(n^2/2)

public void insertSort(int []a ) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j - 1] > a[j]) {
                ex(a, j-1, j);
            } else {
                break;
            }

        }
    }
}
    public static void ex(int a[],int i,int j){
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

希尔排序：

排序：希尔排序（算法） - 简书 (jianshu.com)

希尔排序是基于直接插入排序的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

原理：

希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

**增量d 的范围： **1<= d < 待排序数组的长度 （d 需为 int 值）
**增量的取值： **一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。

时间复杂度：

1) 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2) 最坏情况：O(nlog2n)。
3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）

希尔排序的时间性能优于直接插入排序

①当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和 n² 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n²)差别不大。（n指待排序序列长度）
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量d 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。

稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

public static int[]  insertionSort(int[] arr){
    if(arr == null || arr.length <= 1){
        return arr;
    }
    //希尔排序  升序
    for (int d = arr.length / 2;d>0;d /= 2){ //d：增量  7   3   1
        for (int i = d; i < arr.length; i++){
            //i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
            //j:代表与i同一组的数组元素角标
            for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界
                if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标
                    //符合条件，插入元素（交换位置）
                    int temp = arr[j];
                    arr[j] = arr[j + d];
                    arr[j + d] = temp;
                }
            }
        }
    }
    return arr;
}

归并排序：

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间，并不是原地排序算法。

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

算法描述

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

参考：

(40条消息) 归并排序java（内附超详解图文讲解）_一个热爱编程的小白白的博客-CSDN博客_归并排序java

/**
 * 
 * @param arr  排序的原始数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right    右边索引
 * @param temp    做中转的数组
 */
	
	//4 5 7 8   1 2 3 6
	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
		int i=left;  //初始i,左边有序序列的初始索引
		int j=mid+1;  //初始j,右边有序序列的初始索引
		int t=0;       //指向temp数组的当前索引
		
		//1.
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列,有一边处理完毕为止
		while(i<=mid&&j<=right) {
		
			if(arr[i]<arr[j]) {
				temp[t]=arr[i++];
				/**
				 * 这里我们这里是：temp[t]=arr[i++];
				 * 如果不好理解，你可以写成这样：
				 * temp[t]=arr[i];i++;
				 */
				}
			else {
				
				temp[t]=arr[j++];
			
			}
			//因为无论执行if里面的语句还是else里面的语句,t都要加1,所以把t移出来.
	
			t++;
		 	
		}
		
		//2.
		//把有剩余数据的一边的的数据依次全部填充到temp
		//由上述循环条件：i<=mid&&j<=right 可知 
		//此时要么i>mid 要么j>right
		while(i<=mid) {
			temp[t]=arr[i];
			t++;
			i++;
			
		}
		while(j<=right) {
			temp[t]=arr[j];
			t++;
			j++;
			
		}	
		//3.
		//把temp的数组转移到arr上
	   int n=0;
       int tempLeft=left;
	   while(tempLeft<=right){
		   arr[tempLeft]=temp[n];
		   n++;
		   tempLeft++;
		   
	   }
	}

算法分析

时间复杂度

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。

用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c，则对于n个待排序记录来说整个问题的规模为cn。

从这个递归树可以看出，第一层时间代价为cn，第二层时间代价为cn/2+cn/2=cn…..每一层代价都是cn，总共有logn+1层。所以总的时间代价为cn*(logn+1).时间复杂度是o(nlogn).

(40条消息) 漫谈经典排序算法:四、归并排序(合并排序)_一个程序写手的博客-CSDN博客

快速排序：

快速排序是冒泡排序的一种改进，冒泡排序排完一趟是最大值冒出来了，那么可不可以先选定一个值，然后扫描待排序序列，把小于该值的记录和大于该值的记录分成两个单独的序列，然后分别对这两个序列进行上述操作。这就是快速排序，我们把选定的那个值称为枢纽值，如果枢纽值为序列中的最大值，那么一趟快速排序就变成了一趟冒泡排序。

效率分析

​ 快速排序时间与划分是否对称有关。快速排序的平均时间复杂度为o（nlogn），至于为什么是o（nlogn），请参考《算法导论》第7章，书中用递归树的方法阐述了快速排序平均时间。且常数因子很小，所以就平均时间而言，快速排序是很好的内部排序方法。最佳情况下（每次划分都对称）时间复杂度o（n*logn）。最坏情况下（每次划分都不对称，如输入的序列有序或者逆序时）时间复杂度为o(n^2)，所以在待排序序列有序或逆序时不宜选用快速排序。此外，快速排序是不稳定的。

    最佳情况下，每次划分都是对称的，由于枢纽值不再考虑，所以得到的两个子问题的大小不可能大于n/2，同时一趟快速排序时间为o（n），所以运行时间递归表达式：

T（n）<=2T(n/2)+o(n)。这个递归式的解法请参考下一篇博客中归并排序效率分析。其解为T（n）=o（n*logn）。

    最坏情况下，每次划分都很不对称，T(n)=T(n-1)+o(n),可以用递归树来解，第i层的代价为n-i+1.总共有n层。把每一层代价加起来有n-1个n相加。所以这个递归式的解为T（n）=o（n^2）,此时就是冒泡排序。

public class QuickSort {

//    每一次排序都能够确定一个元素的位置
    public  static  int partition(int []a,int low,int high){
        int left =low;
        int right = high;
//        存储临时的数组元素
        int temp = a[left];
        while (left<right){
            while (right>left&&a[right]>=temp){
                //       从右往左进行遍历，移动right指针，找到第一个比分界值小的元素
//            没有找到就一直移动右指针
                right--;
            }
//        找到之后进行值交换,此时移动左指针，右指针指向交换过的元素，相当于占了一个坑，等右边的的元素添加进来
            a[left] =a[right];
//        从左往右进行扫描，移动left指针，找到一个分界点的值
            while (left<right&&a[left]<temp){
                left++;
            }
            a[right] =a[left];
        }
      a[left] =temp;

        return left;
    }
// 一直进行分治递归
public void sort(int a[],int first,int end){
        int i ;
        if(first<end){
            i =partition(a,first,end);：
                
            sort(a,first,i-1);
            sort(a,i+1,end);
        }
}


    public static void main(String[] args) {
        int arr[] = {1,5,8,7,10,48,10,5};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }

    }
}

堆排序：

将输入数组建立为一个 大顶堆，之后反复取出堆顶并对剩余元素重建大顶堆，将依次取出的堆顶逆序排列，即可将原数组从小到大排列完成排序。

一个直接的想法是在原数组之外新建一个数组保存每次取得的堆顶，这样会有 O (n) O (n) 的空间开销，可以用一种称作 「原地堆排序」的技巧避免此开销，具体做法如下。

• 首先将原待排序数组 $arr [] 建立为一个大顶堆 (heapify 堆化方法)。
• 交换堆顶和当前未排序部分中最末尾元素，则堆顶元素已排序（此时在数组最末尾）。
• 剩余元素中 只有当前堆顶（之前被交换的末尾元素）可能造成 堆失序，因此只需对堆顶调用一次调整堆序的下滤 (siftDown) 操作（操作范围为未排序部分），即可恢复未排序部分的堆序。
• 重复 2，3 直到所有元素已排序，返回 $arr []。

上述通过交换堆顶与当前未排序部分末尾元素的做法，避免了额外的空间开销，即 原地堆排序，程序结束后返回的 $arr [] 为已排序状态

稳定性：不稳定。

交换可能会破坏稳定性。例：输入数组 {1, 2, 2}，变灰表示已排序。可以看到红 2 和绿 2 的相对顺序相比输入已改变。

堆化方法 (heapify)
将原输入数组看作一棵 完全二叉树 (Complete Binary Tree)。根节点下标为 0，于是根据完全二叉树的结构性质，任意一个节点 (下标为 i ) 的左子节点下标为 2 * i + 12∗i+1，右子节点下标为 2 * i + 22∗i+2，父节点下标为 i / 2i/2。 堆化过程即使得整棵树满足堆序性质，也即任意一个节点大于等于其子节点（大顶堆）。堆化操作总结为一句话就是：对最后一个非叶子节点到根节点，依次执行下滤操作 (siftDown)。

从最后非一个叶子开始下滤的原因是此节点之后的节点均为叶子节点，叶子节点无子节点，故其本身已满足堆序性质，也就无下滤的必要（也无法下滤）。每一次下滤使得该节点及其之后的节点都满足堆序性质，直到根节点。

※ 最后一个非叶子节点（也即最后一个元素的父节点）下标为 (n - 1) / 2 (n−1)/2，n 为数组长度。

如下动图是将输入数组 {4, 6, 2, 1, 7, 9, 5, 8, 3} (1 为最后一个非叶子结点) 堆化成大顶堆 {9, 8, 5, 6, 7, 2, 4, 1, 3} 的过程。

下滤方法 (siftDown)
下滤 (siftDown) 是堆排序的核心方法，在堆排序中用于在程序开始时 创建大顶堆，以及在每次排序堆顶时用于 恢复未排序部分的堆序。

该方法来源于删除堆顶元素操作，先介绍下滤在删除堆顶元素操作中的处理过程。如下动图展示了删除大顶堆 {9, 8, 5, 6, 7, 2, 4, 1, 3} 堆顶元素 9 的过程（动图中出现的 100 表示堆顶，值为 9）。

删除堆顶，堆中元素减 1，将当前最后一个元素 3 暂时置为堆顶。

可以看到，此时影响堆序的只有该堆顶元素 3，于是交换其与左右子节点中的较大者。

对元素 3 重复操作 2，直到 3 再无子节点，堆序恢复。

恢复堆序的过程就是将影响堆序的元素不断向下层移动（并交换）的过程，因此形象地称之为下滤 (siftDown)。

※ 注意，此处沿用 JDK 源码中下滤操作的方法名”siftDown”，sift 为过滤之意，网上有的博客文章将其讹误成 shift。

桶排序:

将数组分配到有限的数量的桶中，对每个桶再进行排序，最后进行排序，最后将桶进行合并