十一种排序算法全面解析

大家好，欢迎来到IT知识分享网。

1. 排序相关概念

排序算法的评价：

• 时间复杂度：主要分析关键字的比较次数和记录的移动次数
• 空间复杂度：需要的辅助内存的大小
• 稳定性：假设数据在有两个2，这两个2排序之后的相对顺序不变

内部排序类：

1. 选择排序：直接选择排序、堆排序
2. 交换排序：冒泡排序、快速排序
3. 插入排序：直接插入排序、折半插入排序、希尔排序
4. 归并排序
5. 线性排序算法：计数排序、桶排序、基数排序

2. 选择排序

2.1 直接选择排序

特点：

• n个数据需要n-1趟比较
• 升序：每次选取当前未处理元素中的最小元素放在数组前面
• 降序：每次选取当前未处理元素中的最大元素放在数组前面
• 不稳定排序
• 时间复杂度: 最好 $O(n^2)$最坏 $O(n^2)$平均 $O(n^2)$
• 空间复杂度：$O(1)$

例子：对数据21 30 49 30* 16 9 加*号是为了判断排序之后数据是否稳定

package datastructure.sort; import java.util.Arrays; public class SelectSort { 
    public static void sort(int[] arr) { 
    int n=arr.length; //依次进行n-1趟比较 第i趟选择第i小的值放在位置i上 for(int i=0;i<n-1;i++) { 
    int minIndex=i;//假设当前最小数据就是arr[i] for(int j=i+1;j<n;j++) { 
   //j=i+1: 第i个数据只和它后面的数据比较 if(arr[j]<arr[minIndex]) { 
    minIndex=j;//minIndex保存本趟比较中较小值的索引 } } if(minIndex!=i) { 
   //相等说明arr[i]就是当前最小 不用交换 不等需要交换 int tmp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=tmp; } } System.out.println(Arrays.toString(arr)); } public static void main(String[] args) { 
    int[] arr= { 
   21,30,49,30,16,9}; sort(arr); } } 

2.2 堆排序

堆排序相关内容参考：优先队列和堆及相关问题

特点：

• 时间复杂度: 最好 $O(nlogn)$最坏 $O(nlogn)$平均 $O(nlogn)$
• 空间复杂度：O(1）
• 不稳定排序

代码实现：

package datastructure.sort; import java.util.Arrays; public class HeapSort { 
    public static void sort(int arr[]) { 
    int N=arr.length; //将数组元素构建出一个大顶堆 //最后一个节点编号是N-1 其父节点编号为:(N-1-1)/2=N/2-1 for(int k=N/2-1;k>=0;k--)// N/2-1指向最后一个父节点 从其开始调整 { 
    sink(arr,k,N); } //交换 下沉 while(N>0) { 
    swap(arr, 0, N-1); N--;//N--可以看出是删除堆顶最大元素 因此需要进行下沉操作进行调整 sink(arr, 0, N);//这里只需要sink一次是因为只影响了堆顶节点和其左右子节点的关系 } System.out.println(Arrays.toString(arr)); } public static void sink(int arr[],int k,int N) { 
    while(2*k+1<N) { 
    int j=2*k+1;//指向左子节点 //根节点>=max(左子节点，右子节点) if(j+1<N&&arr[j]<arr[j+1])//如果右子节点存在且右子节点比左子节点大 j+1指向右子节点  j++;//j指向右子节点 if(arr[k]>=arr[j])//找到<=根节点的子节点 停止  break; swap(arr, k, j); k=j; } } public static void swap(int arr[],int i,int j) { 
    int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } public static void main(String[] args) { 
    int[] arr= { 
   21,30,49,30,16,9}; sort(arr); } } 

3. 交换排序

3.1 冒泡排序

特点：

• n个数据需要n-1趟比较
• 第1趟需要n-1次比较，最后一趟只需要1次比较，即越往后比较次数越少
• 每趟比较结束后，都能确定一个元素到数组的后面
• 如果某一趟没有进行交换，说明数组已经排好序了
• 稳定排序
• 时间复杂度：平均：$O(n^2)$ 最坏：$O(n^2)$ 最好：$O(n)$ （使用了flag标志，如果数组本来就有序，第一趟比较后没有发生交换择排序结束）
• 空间复杂度：O(1)

例子：9 16 21* 23 30 49 21 30*

package datastructure.sort; import java.util.Arrays; public class