• 冒泡排序与快速排序


     博主主页: 码农派大星.

        数据结构专栏:Java数据结构

     数据库专栏:MySQL数据库

    关注博主带你了解更多数据结构知识

    1.冒泡排序

    冒泡排序

    1. private static void swap(int[] arrary,int i,int j){
    2.         int tmp = arrary[i];
    3.         arrary[i] = arrary[j];
    4.         arrary[j] = tmp;
    5.  
    6. public static void  bubbleSort(int[] arrary){
    7.         for (int i = 0; i <arrary.length-1 ; i++) {
    8.             for (int j = 0; j < arrary.length-1-i; j++) {
    9.                 if(arrary[j]> arrary[j+1]){
    10.                     swap(arrary,j,j+1);
    11.                 }
    12.  
    13.             }
    14.         }
    15.         return arrary;
    16.     }

    冒泡排序总结

    1. 冒泡排序是一种非常容易理解的排序

    2. 时间复杂度：O(N^2)

    3. 空间复杂度：O(1)

    4. 稳定性：稳定 

    2.快速排序

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

    1.Hoare版

    1. public static void  quickSort(int[] arrary){
    2.         quick(arrary,0,arrary.length-1);
    3.         return arrary;
    4.  
    5.     }
    6.     private static void swap(int[] arrary,int i,int j){
    7.         int tmp = arrary[i];
    8.         arrary[i] = arrary[j];
    9.         arrary[j] = tmp;
    10.     private static void quick(int [] arrary,int start,int end){
    11.         if (start >= end) {
    12.             return;
    13.         }
    14.         int par = partition(arrary,start,end);
    15.         quick(arrary,start,par-1);
    16.         quick(arrary,par+1,end);
    17.     }
    18.     private static int partition(int [] arrary,int left,int right){
    19.         int i = left;
    20.         int tmp = arrary[left];
    21.         while (left < right){
    22.             //right-- : 先走左边会导致最后相遇的地方比基准大的数据,
    23.             // 交换完后,会把大于基准的值换到前面
    24.             while (left < right && arrary[right] >= tmp){
    25.                 right--;
    26.             }
    27.             while (left < right && arrary[left] <= tmp){
    28.                 left++;
    29.             }
    30.             swap(arrary,left,right);
    31.         }
    32.         //此时相遇left=right;
    33.         swap(arrary,left,i);
    34.         return right;
    35.     }

    2.挖坑法 

    1. public static void  quickSort(int[] arrary){
    2.         quick(arrary,0,arrary.length-1);
    3.         return arrary;
    4.  
    5.     }
    6. private static void quick(int [] arrary,int start,int end){
    7.         if (start >= end) {
    8.             return;
    9.         }
    10.         int par = partitionWaken(arrary,start,end);
    11.         quick(arrary,start,par-1);
    12.         quick(arrary,par+1,end);
    13.     }
    14. private static int partitionWaken(int [] arrary,int left,int right){
    15.         int tmp = arrary[left];
    16.         while (left<right){
    17.             while (left < right && arrary[right] >= tmp){
    18.                 right--;
    19.             }
    20.             arrary[left] = arrary [right];
    21.             while (left<right && arrary[left] <= tmp){
    22.                 left++;
    23.             }
    24.             arrary[right] = arrary[left];
    25.         }
    26.         arrary[left] = tmp;
    27.         return left;
    28.     }

    3.快速排序优化

    1. 三数取中法选key

    1.  
    2.  public static void  quickSort(int[] arrary){
    3.         quick(arrary,0,arrary.length-1);
    4. return arrary;
    5.  
    6.     }
    7.     private static void quick(int [] arrary,int start,int end){
    8.         if (start >= end) {
    9.             return;
    10.         }
    11.  
    12.         int index = midThreeNum(arrary,start,end);
    13.         swap(arrary,index,start);
    14.  
    15.         int par = partitionWaken(arrary,start,end);
    16.         quick(arrary,start,par-1);
    17.         quick(arrary,par+1,end);
    18.     }
    19.  
    20. private static int partitionWaken(int [] arrary,int left,int right){
    21.         int tmp = arrary[left];
    22.         while (left<right){
    23.             while (left < right && arrary[right] >= tmp){
    24.                 right--;
    25.             }
    26.             arrary[left] = arrary [right];
    27.             while (left<right && arrary[left] <= tmp){
    28.                 left++;
    29.             }
    30.             arrary[right] = arrary[left];
    31.         }
    32.         arrary[left] = tmp;
    33.         return left;
    34.     }
    35.     private static int midThreeNum(int [] arrary,int left,int right){
    36.         int mid = (left+right)/2;
    37.         if (arrary[left] < arrary[right]){
    38.             if (arrary[mid] < arrary[left]) {
    39.                 return left;
    40.  
    41.             }else if (arrary[mid] > arrary[right]){
    42.                 return right;
    43.             }else {
    44.                 return mid;
    45.             }
    46.         }else{
    47.             if (arrary[mid] < arrary[right]){
    48.                 return right;
    49.             }else if(arrary[mid] > arrary[left]){
    50.                 return left;
    51.             }else {
    52.                 return mid;
    53.             }
    54.         }
    55.     }

    2. 递归到小的子区间时，可以考虑使用插入排序

    我们在数组中数据小于等于10时改为插入排序,提高了排序的效率.

    1.  public static void  quickSort(int[] arrary){
    2.         quick(arrary,0,arrary.length-1);
    3. return arrary;
    4.  
    5.     }
    6.     private static void quick(int [] arrary,int start,int end){
    7.         if (start >= end) {
    8.             return;
    9.         }
    10.         if (end - start + 1 <= 10) {
    11.             inserSortRange(arrary,start,end);
    12.             return;
    13.         }
    14.  
    15.         int index = midThreeNum(arrary,start,end);
    16.         swap(arrary,index,start);
    17.  
    18.         int par = partitionWaken(arrary,start,end);
    19.         quick(arrary,start,par-1);
    20.         quick(arrary,par+1,end);
    21.     }
    22.     public static  void inserSortRange(int [] array,int left,int right){
    23.         for(int i = left+1; i< right;i++){
    24.             int tmp = array[i];
    25.             int j = i-1;
    26.             for (; j >=0 ; j--) {
    27.                 if (array[j] > tmp) {
    28.                     array[j+1] = array[j];
    29.                 }else {
    30.                     //array[j+1]= tmp;
    31.                     break;
    32.                 }
    33.             }
    34.             array[j+1]= tmp;
    35.         }
    36.     }
    37.  private static int partitionWaken(int [] arrary,int left,int right){
    38.         int tmp = arrary[left];
    39.         while (left<right){
    40.             while (left < right && arrary[right] >= tmp){
    41.                 right--;
    42.             }
    43.             arrary[left] = arrary [right];
    44.             while (left<right && arrary[left] <= tmp){
    45.                 left++;
    46.             }
    47.             arrary[right] = arrary[left];
    48.         }
    49.         arrary[left] = tmp;
    50.         return left;
    51.     }
    52.     private static int midThreeNum(int [] arrary,int left,int right){
    53.         int mid = (left+right)/2;
    54.         if (arrary[left] < arrary[right]){
    55.             if (arrary[mid] < arrary[left]) {
    56.                 return left;
    57.  
    58.             }else if (arrary[mid] > arrary[right]){
    59.                 return right;
    60.             }else {
    61.                 return mid;
    62.             }
    63.         }else{
    64.             if (arrary[mid] < arrary[right]){
    65.                 return right;
    66.             }else if(arrary[mid] > arrary[left]){
    67.                 return left;
    68.             }else {
    69.                 return mid;
    70.             }
    71.         }
    72.     }

    4.非递归的快速排序 

    1. //非递归快速排序
    2.  
    3.     public static void quickNot(int[] array){
    4.         Stack<Integer> stack = new Stack<>();
    5.         int left = 0;
    6.         int right = array.length - 1;
    7.         int par = partition(array,left,right);
    8.         if (par > left+1){
    9.             stack.push(left);
    10.             stack.push(par-1);
    11.  
    12.         }
    13.         if (par < right-1){
    14.             stack.push(par+1);
    15.             stack.push(right);
    16.         }
    17.         while (!stack.isEmpty()){
    18.             right = stack.pop();
    19.             left = stack.pop();
    20.             par = partitionWaken(array,left,right);
    21.             if(par > left+1){
    22.                 stack.push(left);
    23.                 stack.push(par-1);
    24.             }
    25.             if (par < right -1){
    26.                 stack.push(par+1);
    27.                 stack.push(right);
    28.             }
    29.         }
    30.          return array;
    31.     }
    32. private static int partition(int [] arrary,int left,int right){
    33.         int i = left;
    34.         int tmp = arrary[left];
    35.         while (left < right){
    36.             //right-- : 先走左边会导致最后相遇的地方比基准大的数据,
    37.             // 交换完后,会把大于基准的值换到前面
    38.             while (left < right && arrary[right] >= tmp){
    39.                 right--;
    40.             }
    41.             while (left < right && arrary[left] <= tmp){
    42.                 left++;
    43.             }
    44.             swap(arrary,left,right);
    45.         }
    46.         //此时相遇left=right;
    47.         swap(arrary,left,i);
    48.         return right;
    49.     }

    未优化的快速排序,再遇到数据过多时,程序会崩. 

    1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

    2. 时间复杂度：O(N*logN)

    快速排序和堆排序时间复杂度一样,但是快速排序要比堆排序快

    3. 空间复杂度：O(logN)

    4. 稳定性：不稳定

  • 相关阅读:
    vscode绿色行数设置
    线程终止的 4 种方式
    OCP Java17 SE Developers 复习题06
    MQ学习之史上最全RabbitMQ（强烈建议收藏）
    TiDB 集群中能够采集的诊断数据类型
    Android 匿名共享内存的使用
    目标追踪Sort与DeepSort算法
    Qt listWidget 详细分析
    springcloud学习笔记：通过openFeign实现微服务接口远程调用
    webpack几个插件的安装使用
  • 原文地址：https://blog.csdn.net/jj666mhhh/article/details/139318786