美文网首页
快速排序

快速排序

作者: 攻城狮l | 来源:发表于2019-04-20 21:52 被阅读0次

    一、快速排序算法

    快速排序(Quicksort)是对冒泡排序的一种改进。

    二、算法思想

    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    步骤如下:

    1.找到数组中的一个数为基准(一般是数组中的第一个数),然后从右向左找到第一个比基准数小的数,交换位置
    2.然后以当前位置,从左到右的找到第一个比基准数大的数,交换位置
    3.重复步骤1和2,直到左右两个位置相等,然后把基准数存入当前位置,此时 基准数左边的数字 <=基准数 <=基准数右边的数字
    4.然后以当前基准数位置为分界,分为左右两个数组,进行排序,循环执行步骤1,2和3。
    5.如果可排序区间只有一个元素,则说明当前循环排序完成

    三、代码实现

    package xzg.algorithm;
    
    /**
     * 快速排序
     */
    public class QuickSort {
    
        public static void main(String[] args) {
    //        int[] heights = {181, 169, 187, 166,150,172, 163, 191, 189, 182};
            int[] heights = {5, 7, 1, 6, 8, 6};
            quickSortArr(heights, 0, heights.length - 1);
            System.out.println("------排序完成-------");
            // 输出排序后的结果
            for (int height : heights) {
                System.out.print(height + " ");
            }
        }
    
    
        /**
         * @param array 指定的数组
         * @param start 需要快速排序的数组索引起点
         * @param end   需要快速排序的数组索引终点
         */
        public static void quickSort(int[] array, int start, int end) {
            System.out.println("------排序前-------");
            for (int height : array) {
                System.out.print(height + " ");
            }
            System.out.println();
            // i相当于助手1的位置,j相当于助手2的位置
            int i = start, j = end;
            // 取第1个元素为基准元素
            int pivot = array[i];
            // 表示空位的位置索引,默认为被取出的基准元素的位置
            int emptyIndex = i;
            // 如果需要排序的元素个数不止1个,就进入快速排序(只要i和j不同,就表明至少有2个数组元素需要排序)
            while (i < j) {
                // 助手2开始从右向左一个个地查找小于基准元素的元素
                int jValue = array[j];
                while (i < j && pivot <= jValue) {
                    j--;
                }
                if (i < j) {
                    // 如果助手2在遇到助手1之前就找到了对应的元素,就将该元素给助手1的"空位",j成了空位
                    array[emptyIndex] = array[emptyIndex = j];
                }
    
                // 助手1开始从左向右一个个地查找大于基准元素的元素
                int iValue = array[i];
                while (i < j && iValue <= pivot) {
                    i++;
                }
                if (i < j) {
                    // 如果助手1在遇到助手2之前就找到了对应的元素,就将该元素给助手2的"空位",i成了空位
                    array[emptyIndex] = array[emptyIndex = i];
                }
    
                for (int height : array) {
                    System.out.print(height + " ");
                }
                System.out.println();
            }
            // 助手1和助手2相遇后会停止循环,将最初取出的基准值给最后的空位
            array[emptyIndex] = pivot;
            System.out.println("------排序后-------");
            for (int height : array) {
                System.out.print(height + " ");
            }
            System.out.println();
            // =====本轮快速排序完成=====
    
            // 如果分割点i左侧有2个以上的元素,递归调用继续对其进行快速排序
            if (i - start > 1) {
                quickSort(array, 0, i - 1);
            }
            // 如果分割点j右侧有2个以上的元素,递归调用继续对其进行快速排序
            if (end - j > 1) {
                quickSort(array, j + 1, end);
            }
        }
    
        /**
         * 快速排序算法:<br/>
         * 算法思想:<br/>
         * 1.找到数组中的一个数为基准(一般是数组中的第一个数),然后从右向左找到第一个比基准数小的数,交换位置<br/>
         * 2.然后以当前位置,从左到右的找到第一个比基准数大的数,交换位置<br/>
         * 3.重复步骤1和2,直到左右两个位置相等,然后把基准数存入当前位置,此时 基准数左边的数字 <=基准数 <=基准数右边的数字<br/>
         * 4.然后以当前基准数位置为分界,分为左右两个数组,进行排序,循环执行步骤1,2和3
         * 5.如果可排序区间只有一个元素,则说明当前循环排序完成
         *
         * @param arr
         * @param start
         * @param end
         */
        public static void quickSortArr(int[] arr, int start, int end) {
            //数组左边位置,也是基准元素的初始化位置
            int left = start;
            //数组右边位置
            int right = end;
            //基准数
            int temp = 0;
            //当前排序区间只有一个元素
            if (left < right) {
                //以可排序区间的第一个数字为基准数据
                temp = arr[left];
                //当前排序区间元素大于1
                while (left != right) {
                    while (left < right & temp <= arr[right]) {
                        //在当前排序区间中,从右向左找到第一个小于基准元素的数据所在的位置
                        right--;
                    }
                    //找到相关元素,把其赋值给原基准元素所在的位置
                    arr[left] = arr[right];
                    System.out.println("----------while---从右向左找到第一个小于基准元素---right=" + right+" left="+left);
                    for (int height : arr) {
                        System.out.print(height + " ");
                    }
                    System.out.println();
                    while (left < right && temp >= arr[left]) {
                        //在当前排序区间中,从左向右找到第一个大于基准元素的数据所在的位置
                        left++;
                    }
                    //找到相关元素,把其赋值给原基准元素所在的位置
                    arr[right] = arr[left];
                    System.out.println("----------while---从左向右找到第一个大于基准元素---right=" + right+" left="+left);
                    for (int height : arr) {
                        System.out.print(height + " ");
                    }
                    System.out.println();
                }
                //基准元素归位,此时left=right
                arr[left] = temp;
                System.out.println("------排序后--基准元素归位---right=" + right+" left="+left);
                for (int height : arr) {
                    System.out.print(height + " ");
                }
                System.out.println();
                //对基准元素右边的元素进递归排序
                quickSortArr(arr, right + 1, end);
                //对基准元素左边的元素进行递归排序
                quickSortArr(arr, start, left - 1);
            }
        }
    
    }
    
    

    输出结果

    ----------while---从右向左找到第一个小于基准元素---right=2 left=0
    1 7 1 6 8 6 
    ----------while---从左向右找到第一个大于基准元素---right=2 left=1
    1 7 7 6 8 6 
    ----------while---从右向左找到第一个小于基准元素---right=1 left=1
    1 7 7 6 8 6 
    ----------while---从左向右找到第一个大于基准元素---right=1 left=1
    1 7 7 6 8 6 
    ------排序后--基准元素归位---right=1 left=1
    1 5 7 6 8 6 
    ----------while---从右向左找到第一个小于基准元素---right=5 left=2
    1 5 6 6 8 6 
    ----------while---从左向右找到第一个大于基准元素---right=5 left=4
    1 5 6 6 8 8 
    ----------while---从右向左找到第一个小于基准元素---right=4 left=4
    1 5 6 6 8 8 
    ----------while---从左向右找到第一个大于基准元素---right=4 left=4
    1 5 6 6 8 8 
    ------排序后--基准元素归位---right=4 left=4
    1 5 6 6 7 8 
    ----------while---从右向左找到第一个小于基准元素---right=2 left=2
    1 5 6 6 7 8 
    ----------while---从左向右找到第一个大于基准元素---right=2 left=2
    1 5 6 6 7 8 
    ------排序后--基准元素归位---right=2 left=2
    1 5 6 6 7 8 
    ------排序完成-------
    1 5 6 6 7 8 
    Process finished with exit code 0
    

    四、算法分析

    空间复杂度为O(log2n)
    参考资料

    https://www.cnblogs.com/MOBIN/p/4681369.html

    相关文章

      网友评论

          本文标题:快速排序

          本文链接:https://www.haomeiwen.com/subject/jmyibqtx.html