美文网首页
快速排序

快速排序

作者: 桑鱼nicoo | 来源:发表于2020-02-28 18:31 被阅读0次

    快速排序使用分治法策略, 就是把一个序列分为较小数值和较大数值的2个子序列, 就是通过递归地排序两个子序列

    快速排序的步骤是:

    1. 挑选基准值:从数列中挑出一个元素,称为基准
    2. 分割:重新排列数列,所有比基准小的元素摆放在基准前面,所以比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成
    3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序

    递归终止条件是数列的大小是零或一,此时该数列显然已经有序了。

    public class Application {
        public static void qSort(int[] arr, int head, int tail){
            if(head >= tail || arr == null || arr.length <= 1){
                return;
            }
            int i = head;
            int j = tail;
            int pivot = arr[(head + tail) / 2];
    
            while (i <= j){
                while (arr[i] < pivot){
                    ++i;
                }
                while (arr[j] > pivot){
                    --j;
                }
                if(i < j){
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                    ++i;
                    --j;
                }else if(i == j){
    
                    ++i;
                }
            }
    
            qSort(arr,head,j);
            qSort(arr,i,tail);
        }
    
        public static void main(String[] args) {
            int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
            qSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    }
    

    相关文章

      网友评论

          本文标题:快速排序

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