devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

冒泡排序与快速排序

作者：2023面试高手 | 2024-06-10 15:50:53

赞

踩

冒泡排序与快速排序


 博主主页: 码农派大星.

    数据结构专栏: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. 稳定性：不稳定

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/699362
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号