• 数据结构之常见排序算法

    目录

    一、排序中的概念

    二、常见排序算法--升序

    1、插入排序

    （1）直接插入排序

    （2）希尔排序

    2、选择排序

    （1）单指针选择排序

    （2）双指针选择排序

    （3）堆排序

    3、交换排序

    （1）冒泡排序

    （2）双指针快速排序

    （3）挖洞快速排序

    （4）前后指针快速排序

    （5）优化版快速排序

    （6）非递归快速排序

    4、归并排序

    （1）归并排序

    （2）归并排序非递归

    5、计数排序

    6、桶排序

    7、基数排序

    一、排序中的概念

    1、稳定性：在待排序的记录中，存在多个相同的关键字记录，若在排序前和排序后这些相同关键字的相对次序保持不变，则这种排序算法是稳定的，否则称为不稳定的。

    二、常见排序算法--升序

    1、插入排序
    （1）直接插入排序

    ①思想：将要插入的数据和前面比较，要是前面的小，结束比较，要是前面的大，元素后移，再次比较，直到遇到较小的，元素插入。

    ②代码实现：

    1. public static void insertSort(int[] a){
    2.         int size=a.length;
    3.         for(int i=1;i
    4.             int j=i-1;
    5.             int temp=a[i];  //后面会被覆盖
    6.             for(;j>=0;j--){
    7.                 if(a[j]>temp){
    8.                     a[j+1]=a[j];
    9.                 }else {
    10.                     break;
    11.                 }
    12.             }
    13.             a[j+1]=temp;
    14.         }
    15.     }

    ③特性：

    元素越接近有序，时间效率越高；

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

    （2）希尔排序

    ①思想：对元素进行分组，如有10个元素，先分成5组(元素间隔为5)，对着5组进行插入排序；再分成2组(元素间隔为2)，对这2组进行插入排序；最后分成1组(元素间隔为1)，对着1组进行插入排序，此时插入排序时元素已经接近有序了。

    ②代码实现：

    1. public static void shellSort(int[] a){
    2.         int size=a.length;
    3.         while(size/2>=1){
    4.             size/=2;
    5.             shell(a,size);
    6.         }
    7.     }
    8.  
    9.     public static void shell(int[] a,int group){
    10.         int size=a.length;
    11.         for(int i=1;i
    12.             int temp=a[i];
    13.             int j=i-group;
    14.             for(;j>=0;j-=group){
    15.                 if(a[j]>temp){
    16.                     a[j+group]=a[j];
    17.                 }else{
    18.                     break;
    19.                 }
    20.             }
    21.             a[j+group]=temp;
    22.         }
    23.     }

    ③特性：

    是直接插入排序的优化。

    时间复杂度：O(n^1.25)到O(1.6n^1.25)；空间复杂度：O(1)；稳定性：不稳定。

    2、选择排序
    （1）单指针选择排序

    ①思想：

    从第一个数开始，每次找到待排序数的最小值，与第一个数交换位置；然后开始第二个数，每次找到待排序数的最小值，与第二个数交换位置......直到最后一个数结束。

    ②代码实现：

    1. public static void selectSort(int[] a){
    2.         int size=a.length;
    3.         for(int i=0;i1;i++){
    4.             int min=i;
    5.             for(int j=i+1;j
    6.                 if(a[j]
    7.                     min=j;
    8.                 }
    9.             }
    10.             if(i!=min){
    11.                 swap(a,i,min);
    12.             }
    13.         }
    14.     }
    15.     public static void swap(int[] a,int m,int n){
    16.         int temp=a[m];
    17.         a[m]=a[n];
    18.         a[n]=temp;
    19.     }

    ③特性：

    时间复杂度：O(n^2)；空间复杂度：O(1)；稳定性：不稳定。

    （2）双指针选择排序

    ①思想：

    一个指针指向要排序数的最小值，一个指针指向要排序数的最大值，最小值放左边，最大值放右边，往中间遍历，但需注意：最大值在要排序数第一个的情况。

    ②代码实现：

    1. public static void selectSort2(int[] a){
    2.         int size=a.length;
    3.         int left=0;
    4.         int right=size-1;
    5.         while(left
    6.             int max=right;
    7.             int min=left;
    8.             for(int i=left;i<=right;i++){
    9.                 if(a[i]>a[max]){
    10.                     max=i;
    11.                 }else if(a[i]
    12.                     min=i;
    13.                 }
    14.             }
    15.             if(max==left){
    16.                 max=min;
    17.             }
    18.             if(min!=left){
    19.                 swap(a,min,left);
    20.             }
    21.             if(max!=right){
    22.                 swap(a,max,right);
    23.             }
    24.             left++;
    25.             right--;
    26.         }
    27.     }
    28.     public static void swap(int[] a,int m,int n){
    29.         int temp=a[m];
    30.         a[m]=a[n];
    31.         a[n]=temp;
    32.     }
    （3）堆排序

    ①思想：

    若是升序的话，建立大根堆，每次将堆顶元素与最后一个元素交换，前n-1个元素，以第一个父结点进行向下调整......直到交换结束。

    若是降序的话，建立小根堆，每次将堆顶元素与最后一个元素交换，前n-1个元素，以第一个父结点进行向下调整......直到交换结束。

    ②代码实现：

    1. public static void buildPile(int[] a){
    2.         int size=a.length;
    3.         int parent=(size-2)/2;
    4.         for(int i=parent;i>=0;i--){
    5.             buildChildPile(a,i,size);
    6.         }
    7.     }
    8.     public static void buildChildPile(int[] a,int parent,int size){
    9.         int child=2*parent+1;
    10.         while(child
    11.             if(child+11]){
    12.                 child=child+1;
    13.             }
    14.             if(a[child]>a[parent]){
    15.                 swap(a,child,parent);
    16.             }
    17.             parent=child;
    18.             child=2*parent+1;
    19.         }
    20.     }
    21.     public static void pileSort(int[] a){
    22.         int size=a.length-1;
    23.         while(size!=0){
    24.             swap(a,0,size);
    25.             buildChildPile(a,0,size-1);
    26.             size--;
    27.         }
    28.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(1)；稳定性：不稳定。

    3、交换排序
    （1）冒泡排序

    ①思想：

    将大的往左边放，每次遇到一个数，比后面数大，就往后交换。

    ②代码实现：

    1.    public static void bubbleSort(int[] a){
    2.         int size=a.length;
    3.         boolean flag=true;
    4.         for(int i=0;i1;i++){
    5.             for(int j=1;j
    6.                 if(a[j-1]>a[j]){
    7.                     swap(a,j-1,j);
    8.                     flag=false;
    9.                 }
    10.             }
    11.             if(flag){
    12.                 break;
    13.             }
    14.         }
    15.     }

    ③特性：

    时间复杂度：O(n^2)；空间复制度：O(1)；稳定性：稳定。

    （2）双指针快速排序

    ①思想：找到一个基准值，默认为left指针，right往左移，left往右移，如果right小于基准，left大于基准，两者交换，循环进行到left

    ②代码实现：

    1. public static void quickSort(int[] a){
    2.         quickChild(a,0,a.length-1);
    3.     }
    4.     public static void quickChild(int[] a,int left,int right){
    5.         if(left>=right){  //一个元素
    6.             return;
    7.         }
    8.         int index=index(a,left,right); //进行交换，并找到基准值的位置
    9.         quickChild(a,left,index-1);  //左区间接着判断
    10.         quickChild(a,index+1,right);  //右区间接着判断
    11.     }
    12.     public static int index(int[] a,int left,int right){
    13.         int temp=a[left];
    14.         int k=left;
    15.         while (left
    16.             while(left=temp){
    17.                 right--;
    18.             }
    19.             while(left
    20.                 left++;
    21.             }
    22.             swap(a,left,right);
    23.         }
    24.         swap(a,k,left);
    25.         return  left;   //left后走的 right一定是走到了小于等于temp的地方
    26.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(logn)；稳定性：不稳定。

    （3）挖洞快速排序

    ①思想：找到一个基准值，默认为left指针，right往左移，left往右移，如果right小于基准，right和left交换；如果left大于基准，left和right交换，循环进行到left

    ②代码实现：

    1. public static void quickSort2(int[] a){
    2.         quickChild2(a,0,a.length-1);
    3.     }
    4.     public static void quickChild2(int[] a,int left,int right){
    5.         if(left>=right){
    6.             return;
    7.         }
    8.         int index=index2(a,left,right);
    9.         quickChild2(a,left,index-1);
    10.         quickChild2(a,index+1,right);
    11.     }
    12.     public static int index2(int[] a,int left,int right){
    13.         int temp=a[left];
    14.         while(left
    15.             while(left=temp){
    16.                 right--;
    17.             }
    18.             swap(a,left,right);
    19.             while(left
    20.                 left++;
    21.             }
    22.             swap(a,left,right);
    23.         }
    24.         a[left]=temp;
    25.         return left;
    26.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(logn)；稳定性：不稳定。

    （4）前后指针快速排序

    ①思想：前指针pre为left，后指针cur为前指针+1，当cur<=right时，若指针left的值大于指针cur的值，且++pre指针的值不等于cur，交换cur与pre的值，否则不交换；cur++；循环结束后交换left与pre的值。  ----琢磨

    ②代码实现：

    1.  public static void quickSort3(int[] a){
    2.         quickChild3(a,0,a.length-1);
    3.     }
    4.     public static void quickChild3(int[] a,int left,int right){
    5.         if(left>=right){
    6.             return;
    7.         }
    8.         int index=index3(a,left,right);
    9.         quickChild3(a,left,index-1);
    10.         quickChild3(a,index+1,right);
    11.     }
    12.     public static int index3(int[] a,int left,int right){
    13.         int pre=left;
    14.         int cur=pre+1;
    15.         while(cur<=right){
    16.             if(a[left]>a[cur]&&a[++pre]!=a[cur]){
    17.                 swap(a,pre,cur);
    18.             }
    19.             cur++;
    20.         }
    21.         swap(a,left,pre);
    22.         return pre;
    23.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(logn)；稳定性：不稳定。

    （5）优化版快速排序

    ①思想：长度如果小于等于5采用直接插入排序；基准值不再默认为left的值，选择left、right、mid三者的中间值。

    ②代码实现：

    1.  public static void quickSort4(int[] a){
    2.         int size=a.length;
    3.         if(size<=5){
    4.             insertSort(a);
    5.         }else{
    6.             quickChild4(a,0,size-1);
    7.         }
    8.     }
    9.     public static void quickChild4(int[] a,int left,int right){
    10.         if(left>=right){
    11.             return;
    12.         }
    13.         int mid=findMid(a,left,right);  
    14.         swap(a,mid,left);  //改变基准值
    15.         int index=index4(a,left,right);
    16.         quickChild4(a,left,index-1);
    17.         quickChild4(a,index+1,right);
    18.     }
    19.     public static int index4(int[] a,int left,int right){
    20.         int temp=a[left];
    21.         while(left
    22.             while(left=temp){
    23.                 right--;
    24.             }
    25.             swap(a,left,right);
    26.             while(left
    27.                 left++;
    28.             }
    29.             swap(a,left,right);
    30.         }
    31.         a[left]=temp;
    32.         return left;
    33.     }
    34.     public static int findMid(int[] a,int left,int right){
    35.         int mid=(left+right)/2;
    36.         if(a[left]>a[right]){
    37.             if(a[mid]
    38.                 return right;
    39.             }else if(a[mid]>a[left]){
    40.                 return left;
    41.             }else {
    42.                 return mid;
    43.             }
    44.         }else{
    45.             if(a[mid]
    46.                 return left;
    47.             }else if(a[mid]>a[right]){
    48.                 return right;
    49.             }else {
    50.                 return mid;
    51.             }
    52.         }
    53.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(logn)；稳定性：不稳定。

    （6）非递归快速排序

    ①思想：和双指针思想一样，只是此时将left和right的值放进了队列中，只要队列不为空，再拿出来进行交换并获取下标。

    ②代码实现：

    1.  public static void quickSort5(int[] a){
    2.         int right=a.length-1;
    3.         int left=0;
    4.         if(right-left>1){
    5.             quickChild5(a,left,right);
    6.         }
    7.     }
    8.     public static void quickChild5(int[] a,int left,int right){
    9.         Queue queue=new LinkedList<>();
    10.         queue.offer(left);
    11.         queue.offer(right);
    12.         while (!queue.isEmpty()){
    13.             int start=queue.poll();
    14.             int end=queue.poll();
    15.             int index=index(a,start,end);
    16.             if(index-1>start){
    17.                 queue.offer(start);
    18.                 queue.offer(index-1);
    19.             }
    20.             if(right>index+1){
    21.                 queue.offer(index+1);
    22.                 queue.offer(right);
    23.             }
    24.         }
    25.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(logn)；稳定性：不稳定。

    4、归并排序
    （1）归并排序

    ①思想：不断划分区间，直到区间内只有一个元素时结束，然后在区间内进行排序(类似于双指针中的滑动窗口，指针指的数谁小，数往前放，指针后移)合并。

    ②代码实现：

    1.  public static void mergeSort(int[] a){
    2.         mergeChild(a,0,a.length-1);
    3.     }
    4.     public static void mergeChild(int[] a,int left,int right){
    5.         if(left>=right){
    6.             return;
    7.         }
    8.         int mid=(left+right)/2;
    9.         mergeChild(a,left,mid);  //左边拆分
    10.         mergeChild(a,mid+1,right);  //右边拆分
    11.         merge(a,left,mid,right);  //合并
    12.     }
    13.     public static void merge(int[] a,int left,int mid,int right){
    14.         int s1=left;
    15.         int e1=mid;
    16.         int s2=mid+1;
    17.         int e2=right;
    18.         int[] temp=new int[right-left+1];
    19.         int k=0;
    20.         while(s1<=e1&&s2<=e2){
    21.             if(a[s1]
    22.                 temp[k++]=a[s1++];
    23.             }else {
    24.                 temp[k++]=a[s2++];
    25.             }
    26.         }
    27.         if(s1>e1){
    28.             while(s2<=e2){
    29.                 temp[k++]=a[s2++];
    30.             }
    31.         }else {
    32.             while(s1<=e1){
    33.                 temp[k++]=a[s1++];
    34.             }
    35.         }
    36.         for(int i=0;i
    37.             a[i+left]=temp[i]; //a是从left开始的 temp是从0开始的
    38.         }
    39.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(n)；稳定性：稳定。

    （2）归并排序非递归

    ①思想：每次直接求出left，right，mid，然后调用方法进行排序。left根据分组元素求出，mid=left+group-1，right=mid+group。

    ②代码实现：

    1.  public static void mergeSort2(int[] a){
    2.         int group=1;  //区间内元素个数:group+1
    3.         int size=a.length;
    4.         while(group
    5.             for(int i=0;i2) { //left值
    6.                 int left=i;
    7.                 int mid=left+group-1;
    8.                 if(mid>size-1){  //区间里元素个数不够凑成一个group 可能出现mid越界
    9.                     mid=size-1;
    10.                 }
    11.                 int right=mid+group;
    12.                 if(right>size-1){
    13.                     right=size-1;
    14.                 }
    15.                 merge(a,left,mid,right);  //进行合并
    16.             }
    17.             group*=2;
    18.         }
    19.     }

    ③特性：

    时间复杂度：O(n*logn)；空间复杂度：O(n)；稳定性：稳定。

    5、计数排序

    ①思想：统计每个数据出现的次数，并对应下标按照顺序存储，按照顺序再放入排序数组。

    ②代码实现：

    1. public static void countSort(int[] a){
    2.         int size=a.length;
    3.         int min=a[0];
    4.         int max=a[0];
    5.         for(int i=0;i
    6.             if(a[i]>max){
    7.                 max=a[i];
    8.             }else if(a[i]
    9.                 min=a[i];
    10.             }
    11.         }
    12.         int[] count=new int[max-min+1];
    13.         for(int i=0;i
    14.             count[a[i]-min]++;
    15.         }
    16.         int j=0;
    17.         for(int i=0;i
    18.             while (count[i]>0){
    19.                 a[j++]=i+min;
    20.                 count[i]--;
    21.             }
    22.         }
    23.     }

    ③特性：

    时间复杂度：O(n)；空间复杂度：O(范围)；稳定性：稳定

    6、桶排序

    ①思想：

    7、基数排序

    ①思想:

    个位数排序：

    十位数排序：

    百位数排序：

    此时就已经有序了。

  • 相关阅读:
    (vue的入门
    springboot 学习十五：Spring Boot 优雅的集成Swagger2、Knife4j
    jQuery小结三
    mysql安装
    力扣刷题篇之位运算
    技术分享 | 如何写好测试用例？
    记录一次K8s pod被杀的排查过程
    使用id限定优化mysql分页查询limit偏移量大问题
    kubernetes Service详解
    Tomcat运行日志乱码问题/项目用tomcat启动时窗口日志乱码
  • 原文地址：https://blog.csdn.net/m0_69468924/article/details/138130557