快速排序---效率极高

雨点打透心脏的1/2处 2021-09-24 01:04 273阅读 0赞

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

## 代码实现： ##

package sort;
    
    public class quickSort { 
        public static void main(String[] args) { 
    
            int arr[] = { 6, 3, 7, 9, 5, 1, 4, 8};
            quickSort(arr, 0, arr.length - 1);
            for (int i = 0; i < arr.length; i++) { 
                System.out.println(arr[i]);
            }
        }
    
        public static void quickSort(int[] arr, int left, int right) { 
            //进行判断 如果左边索引比右边索引要大 是不合法的 直接使用return结束这个方法
            if (left > right) { 
                return;
            }
    // 定义变量保存基准值
            int base = arr[left];
    // 定义变量i指向最左边
            int i = left;
    // 定义变量j指向最右边
            int j = right;
    
    /** * j从右往左 检索出比基准值小的,如果检索到比基准值小的就停下，否则就继续检索 * * i从左往右 检索出比基准值小的,如果检索到比基准值小的就停下，否则就继续检索 */
    
            while (i != j) { 
    // 从右往左检索
                while (arr[j] >= base && i < j) { 
                    j--;//j从右往左移动
                }
    // 从左往右检索
                while (arr[i] <= base && i < j) { 
                    i++; //i从左往右移动
                }
                //代码走到这里 i停下来 j也停下来 然后就交换两个i和j的位置
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    
            /** * 如果上面while循环的条件不成立 就会跳出过这个循环，往下执行 。 * 同时也说明了这个i和j相遇了 如果i和j相遇了就要交换基准数 * 这个元素和相遇这个位置的元素 */
    
            arr[left] = arr[i];
            //把基准数赋值给相遇位置的元素
            arr[i] = base;
    
            quickSort(arr, left, i - 1);
            quickSort(arr, j + 1, right);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/45e88f2183034104a27aa1accdf9a4b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200317172351381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/f5b65e4cb19744d68248a6f6cb5feb43.png