[数据结构与算法] 排序算法之冒泡排序与快速排序(快排)

小灰灰 2023-07-03 02:42 28阅读 0赞

# 冒泡排序法 #

**冒泡排序（Bubble Sorting）的基本思想**是：

*  通过对待排序序列从前向后（从下标较小的元素开始）,**依次比较相邻元素的值，若发现逆序则交换**，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
 *  因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)

**思路图**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]  
**由思路图可知**

*  一共执行数组长度-1 次大循环
 *  每次大循环的作用是通过两两进行比较, 将本次循环中最大的元素移到后面, 直到所有循环移动完毕
 *  优化: 通过布尔变量flag进行优化,默认为false ,如果发生数据的交换就将flag置为true,并在每次循环结束将flag初始化为false;  
    如果没有发生数据交换说明该数组数据有序,则直接退出当前循环

**代码实现**

> 注意: 两种方法时间复杂度都是 n^2

package ah.sz.tp.algorithm1.sort;
    
    import java.util.Arrays;
    
    /** * 冒泡排序法(正序,时间复杂度n^2) * * @author TimePause * @create 2020-01-31 11:46 */
    public class BubbleSort { 
        public static void main(String[] args) { 
            int[] arr = { 3, 9, -1, 10, 20};
            //int[] arr = {1,2,3,4,5,6};//测试冒泡排序改良是否正确
            bubbleSort2(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        /** * 冒泡排序法 * 1.需要n-1次大循环 * 2.每个大循环需要比较n-i-2(注意是<)次,作用是将当前循环的一个最大值传到右边 * 原因是: 这种方式的排序每次大循环都会确定arr[arr.length-i-1]的顺序 * 3.如果逆序,交换其值;如果都是顺序则直接输出排序结果 * * @param arr */
        public static void bubbleSort(int[] arr){ 
             //这种方式的排序每次大循环都会确定arr[arr.length-i-1]的顺序
            //注意下标: i 代表要执行几次大循环, j 代表每次大循环要执行多少次小循环
            for (int i = 0; i < arr.length-1; i++) { 
                for (int j = 0; j < arr.length-i-1; j++) { 
                    // 确定为正序, 如果违反则交换位置
                    if (arr[j]>arr[j+1]){ 
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
                /*System.out.println("第"+(i+1)+"次排序效果如下"); System.out.println(Arrays.toString(arr));*/
            }
        }
    
        /** * 冒泡排序法优化-使用flag * 1.需要n-1次大循环 * 2.每个大循环需要比较n-i-1次,作用是将当前循环的一个最大值传到右边.例如数组长度为5,第一次循环需要比较4次,第二次并比较需要3次...以此类推 * 3.如果逆序,交换其值;如果都是顺序则直接输出排序结果 * * @param arr */
        public static void bubbleSort2(int[] arr){ 
            // 用于交换数据的临时变量
            int temp=0;
            // 用于标识是否发生了交换
            boolean flag=false;
            for (int i=0;i<arr.length-1;i++){ 
                for (int j=0;j<arr.length-1-i;j++){ 
                    // 正序排序,如果前一个元素大于后一个元素则交换位置
                    if (arr[j]>arr[j+1]){ 
                        // 如果逆序, true
                        flag=true;
                        temp = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = temp;
                    }
                }
                /* System.out.println("第"+(i+1)+"次排序效果如下"); System.out.println(Arrays.toString(arr));*/
                if (!flag){ //如果flag为false,说明没有发生交换
                    break;
                }else { 
                    //如果发生了交换,需要将flag重新置为false, 防止其在下一个循环异常结束
                    flag=false;
                }
            }
        }
    }

**冒泡排序的另一种方法**

*  每次令i与j 的关系都是 j=i+1 (相邻)
 *  每个循环都是将下标为 i 的元素,i 后面的所有元素相比较, 将最大的移到后面

public static void bubbo(int[] arr) { 
     		//核心: 确定顺序后数组元素两两比较. 不符合顺序则换位
            // arr[i]作为两两比较的前一个元素, arr[j]作为后一个元素
            for(int i=0;i<arr.length-1;i++){ 
                for (int j=i+1;j<arr.length;j++){ 
                    // 确定为正序, 如果违反则交换位置
                    if (arr[i]>arr[j]){ 
                        int temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                    }
                }
            }
        }

# 快速排序法 #

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]

**快速排序法应用实例:**

*  要求: 对 \[-9,78,0,23,-567,70\] 进行从小到大的排序，要求使用快速排序法。【测试8w和800w】

**验证分析**

1.  如果取消左右递归，结果是 -9 -567 0 23 78 70
2.  如果取消右递归,结果是 -567 -9 0 23 78 70
3.  如果取消左递归,结果是 -9 -567 0 23 70 78

public class QuickSort { 
    	
    	// 时间复杂度 O(nlogn)
        public static void quickSort(int[] arr, int left ,int right){ 
            int l= left;//左下标
            int r = right;//右下标
            int pivot =arr[(left+right)/2];//中轴值
            int temp=0;//辅助变量,交换数据时使用
            //while循环的作用是让比pivot值小的放在左边,比pivot值大的放在右边
            while (l<r){ 
                // 在pivot的左边一直找, 找到大于等于pivot的值才退出
                // 作用是找到不符合条件的元素,进行元素交换
                while (arr[l]<pivot){ 
                    l+=1;//作用是一直找
                }
                // 在pivot的右边一直找, 找到小于pivot的值才退出
                while (arr[r]>pivot){ 
                    r -= 1;
                }
                //如果l>=r,说明指针已经从左边移动找pivot,或者它的右边.因此pivot的左右两的值,已按照规律排序
                //即: 左边都是小于pivot的值, 右边都是大于pivot的值
                if (l>=r){ 
                    break;
                }
                //交换元素
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
    
                //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
                if(arr[l] == pivot) { 
                    r -= 1;
                }
                //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
                if(arr[r] == pivot) { 
                    l += 1;
                }
            }
            //----如果写到这里直接运行main函数可以测试验证分析第1步----
            // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
            if (l == r) { 
                l += 1;
                r -= 1;
            }
            //向左递归
            if(left < r) { 
                quickSort(arr, left, r);
            }
            //----如果写到这里直接运行main函数可以测试验证分析第2步----
            //向右递归
            if(right > l) { 
                quickSort(arr, l, right);
            }
            //----如果写到这里直接运行main函数可以测试验证分析第3步--
        }
    
    
    
        public static void main(String[] args) { 
            int[] arr = { -9, 78, 0, 23, -567, 70};
            quickSort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
    }

> **测试8w数据排序,用时约为1s以内; 800w数据排序,用时3s左右, 优于希尔排序**

--------------------

**2021.06.15补充: 快速排序简化思路**

1.  定义左下标指针, 右下标指针, 中间值pivot, 临时变量  
    **此时: left = l < pivot < r = right**
2.  l<r 把小于中轴值的放到左边, 大于中轴值的放到右边, 如果 l >=r ,则跳出. 否则需元素交换,  
    如果有元素与中轴值相等则让 l 和 r的下标移动到中轴值上, 使其跳出循环  
    **此时: left < l = pivot = r < right**
3.  l=r 说明坐标都位于中轴值上, 则将 l 后移 r迁移  
    **此时: left<r<pivot<l<right**
4.  执行到这里说明 l>r, 则执行递归, 通过递归快排算法来实现排序  
    **当 left<r , 左侧递归, 当 l<right 执行右侧递归**

/** * 快速排序思路: * 1.定义左下标指针, 右下标指针, 中间值pivot, 临时变量 * 2 l<r 把小于中轴值的放到左边, 大于中轴值的放到右边, 如果 l ==r ,则跳出. 否则需元素交换, * 如果有元素与中轴值相等则让 l 和 r的下标移动到中轴值上, 使其跳出循环 * 3.l=r 说明坐标都位于中轴值上, 则将 l 后移 r前移( 此时 left<r<pivot<l<right ) * 则执行递归, 当 left<r , 左侧递归, 当 l<right 执行右侧递归 * * @param arr 排序数组 * @param left 排序起始下标 * @param right 排序结束下标 */
        public static void quickSort2(int[] arr, int left, int right){ 
            //1.定义左下标指针, 右下标指针, 中间值pivot, 临时变量
            int l = left;
            int r = right;
            int piovt = arr[(l + r) / 2];
            int temp = 0;
    
            //2. l<r 把小于中轴值的放到左边, 大于中轴值的放到右边, 如果 l >=r ,则跳出. 否则需元素交换,
            // 如果有元素与中轴值相等则让 l 和 r的下标移动到中轴值上, 使其跳出循环
            while (l<r){ 
                while (arr[l]<piovt){ 
                    l++;//作用是跳过
                }
                while (arr[r]>piovt){ 
                    r--;
                }
                if (l==r){ 
                    break;
                }
                // 这里是保守逻辑, 如果走到这一步还有元素没有被排序则进行位置交换
                temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
                // 将指针移动到中轴值上
                if (arr[l]==piovt){ 
                    l++;
                }
                if (arr[r] == piovt) { 
                    r--;
                }
            }
            //3.l=r 说明坐标都位于中轴值上, 则将 l 后移 r迁移( 此时 left<r<pivot<l<right )
            if (l==r){ 
                l++;
                r--;
            }
            //4. 执行到这里说明 l>r, 则执行递归, 当 left<r , 左侧递归, 当 l<right 执行右侧递归
            if (left<r){ 
                quickSort2(arr, left, r);
            }
            //一定要注意这里是l, 因为此时 left<r<pivot<l<right
            if (l < right) { 
                quickSort2(arr, l, right);
            }
    
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200131163100351.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200205114124509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70