Java排序（冒泡排序、快速排序）

﹏ヽ暗。殇╰゛Y 2022-03-24 16:20 217阅读 0赞

**一、冒泡排序：**

**冒泡算法原理**：冒泡算法就是依次比较数组中相邻的两个元素，如果左边比右边大则进行调换，以此类推，这样第一次排序就把最大的元素放在最底下。

**举例说明：要排序数组：int\[\] arr = \{7, 2, 6, 5, 9, 4\};**

第1轮排序前数组为：\[7, 2, 6, 5, 9, 4\]

第1轮第1次比较：7大于2交换位置:\[2, 7, 6, 5, 9, 4\]

第1轮第2次比较：7大于6交换位置:\[2, 6, 7, 5, 9, 4\]

第1轮第3次比较：7大于5交换位置:\[2, 6, 5, 7, 9, 4\]

第1轮第4次比较：7小于9不交换位置:\[2, 6, 5, 7, 9, 4\]

第1轮第5次比较：9大于4交换位置:\[2, 6, 5, 7, 4, 9\]

第1轮排序后数组为：\[2, 6, 5, 7, 4, 9\]

第2轮排序前数组为：\[2, 6, 5, 7, 4, 9\]

第2轮第1次比较：2小于6不交换位置:\[2, 6, 5, 7, 4, 9\]

第2轮第2次比较：6大于5交换位置:\[2, 5, 6, 7, 4, 9\]

第2轮第3次比较：6小于7不交换位置:\[2, 5, 6, 7, 4, 9\]

第2轮第4次比较：7大于4交换位置:\[2, 5, 6, 4, 7, 9\]

第2轮排序后数组为：\[2, 5, 6, 4, 7, 9\]

第3轮排序前数组为：\[2, 5, 6, 4, 7, 9\]

第3轮第1次比较：2小于5不交换位置:\[2, 5, 6, 4, 7, 9\]

第3轮第2次比较：5小于6不交换位置:\[2, 5, 6, 4, 7, 9\]

第3轮第3次比较：6大于4交换位置:\[2, 5, 4, 6, 7, 9\]

第3轮排序后数组为：\[2, 5, 4, 6, 7, 9\]

第4轮排序前数组为：\[2, 5, 4, 6, 7, 9\]

第4轮第1次比较：2小于5不交换位置:\[2, 5, 4, 6, 7, 9\]

第4轮第2次比较：5大于4交换位置:\[2, 4, 5, 6, 7, 9\]

第4轮排序后数组为：\[2, 4, 5, 6, 7, 9\]

第5轮排序前数组为：\[2, 4, 5, 6, 7, 9\]

第5轮第1次比较：2小于4不交换位置:\[2, 4, 5, 6, 7, 9\]

第5轮排序后数组为：\[2, 4, 5, 6, 7, 9\]

已排序后的数组为：\[2, 4, 5, 6, 7, 9\]

由此可见：N个数字要排序完成，总共进行N-1轮排序，每i轮的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数，即

for(int i=0;i<arr.length-1;i++)\{

for(int j=0;j<arr.length-i-1;j++)\{

//交换位置

冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一轮比较之后，排在最后的一个数一定是最大的一个数，第二轮排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二轮比较的数后面，第三轮比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，每进行一轮比较，每一轮少比较一次，一定程度上减少了算法的量。

因此冒泡排序总的时间复杂度为O(n\*n)

代码例子：

![u_1938461143_3405288111_fm_173_app_25_f_JPEG_w_496_h_264_s_E8C287475AE0B96A0E6C54030100E0C3][]

**二、快速排序**

快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

接着分别比较左右两边的序列，重复上述的循环。

public class FastSort{
    
         public static void main(String []args){
            System.out.println("Hello World");
            int[] a = {12,20,5,16,15,1,30,45,23,9};
            int start = 0;
            int end = a.length-1;
            sort(a,start,end);
            for(int i = 0; i<a.length; i++){
                 System.out.println(a[i]);
             }
            
         }
         
         public void sort(int[] a,int low,int high){
             int start = low;
             int end = high;
             int key = a[low];
             
             
             while(end>start){
                 //从后往前比较
                 while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                     end--;
                 if(a[end]<=key){
                     int temp = a[end];
                     a[end] = a[start];
                     a[start] = temp;
                 }
                 //从前往后比较
                 while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                    start++;
                 if(a[start]>=key){
                     int temp = a[start];
                     a[start] = a[end];
                     a[end] = temp;
                 }
             //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
             }
             //递归
             if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
             if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
         }
         
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NzU1NzY2_size_16_color_FFFFFF_t_70][]

[u_1938461143_3405288111_fm_173_app_25_f_JPEG_w_496_h_264_s_E8C287475AE0B96A0E6C54030100E0C3]: /images/20220323/7bd861f0eb794f39b4794a1501b86b32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NzU1NzY2_size_16_color_FFFFFF_t_70]: /images/20220323/bc214438cc4540359a2ed27c0c51316e.png