java冒泡排序和快速排序的实现

ゝ一纸荒年。 2022-09-23 13:48 10阅读 0赞

冒泡排序和快速排序都是属于交换排序  
1、冒泡排序  
冒泡排序的基本思想是从头开始扫描需要排序的元素，把相邻的元素进行对比，然后移动元素，一直到所有的元素是一个有序排列为止。  
如果有n个元素，一般需要比较n-1趟，第一趟把最大的移动至最后，第2趟就只需要比较前n-1个元素就行了，所以每一趟需要比较的次数是n-趟数。（换一下markdown编辑器）  
![这里写图片描述][SouthEast]  
java算法实现如下：

public class Bubble 
    {
        public static void main(String[] args) 
        {
        int[] values={
       3,1,4,5,2};
        maopao(values);
        for(int i=0;i<values.length;i++){
              system.out.println("Index: "+i+" value: "+values[i]);
        }
        public staic void maopao(int[] values){
            int temp;
            for(int i=0;i<values.length-1;i++){    //趟数
                for(j=0;j<values.length-i-1;j++){     //每一趟比较的次数
                    if(values[j]>values[j+1]){
                              temp=values[j];
                              values[j]=values[j+1];
                              values[j+1]=temp;
                    } 
    
                }
        }
    }

上面5个数
    第0趟比较4次 1 3 4  2 5 i=0 j<5-1
    第1趟比较3次 1 3 2 4 5   i=1; j<5-1-i
    第2趟比较2次 1 2 3 4 5   i=2; j<5-1-i
    第3趟比较1次 1 2 3 4  5  i=3; j<5-1-i

2、快速排序  
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSort { 
    
        static void QuickSort(int[] array,int begin,int end) 
       { 
           if(begin<end) 
           { 
               int key=array[begin];//关键数据(作为key)
               int i=begin,
               int j=0;  
               for(j=start+1;j<=end;j++) 
                 if(array[j]<key)//如果此处元素小于key，则把此元素和i+1处元素交换，并将i加1，如大于或等于key则继续循环 
                   { 
                       int temp=array[j]; 
                       array[j]=array[i+1]; 
                       array[i+1]=temp; 
                       i++; 
                   } 
    
               } 
               array[begin]=array[i];//交换i处元素和key 
               array[i]=key; 
               QuickSort(array, begin, i-1);//递归调用 
               QuickSort(array, i+1, end); //递归调用
    
           } 
    
       } 
       public static void main(String[] args) 
       { 
           int[] array=new int[]{
       10,20,30,40,50,60,70,80,90}; 
           QuickSort(array, 0, array.length-1); 
           for(int i=0;i<array.length;i++) 
           { 
               System.out.println((i+1)+":"+array[i]); 
           } 
       }

[SouthEast]: /images/20220720/a154f2b6ffbc41169b67222ac0e05b3f.png