内部排序之快速排序（QuickSort）

待我称王封你为后i 2021-09-11 01:48 374阅读 0赞

## **一、基本思想** ##

快速排序法是对冒泡法的改进。基本思想为：从列表中任选一个记录作为枢纽。然后从列表的开始和结束位置向中间遍历，把记录的关键字与枢纽进行比较。小于枢纽的记录放在低位，大于枢纽的记录放在高位。从而把列表分成两部分，一部分大于枢纽，一部分小于枢纽。
    最坏时间O(n*n)

## **二、核心算法** ##

![这里写图片描述][20160907214428859]

## **三、递归调用** ##

![这里写图片描述][20160907214744862]

## **四、例题** ##

[LeetCode之Two Sum][LeetCode_Two Sum]

[快速排序法为什么一定要从右边开始的原因][Link 1]

//java实现
    public class Main{
        public static void main(String[] args){
            int[] a = {1,4,2,5,7,6,-1};
            quickSort(a, 0, a.length-1);
            for(int i=0; i<a.length; i++){
                System.out.println(a[i]);
            }
        }
    
        private static void quickSort(int[] a, int left, int right){
            if(left<right){
                int mid = partition(a, left, right);
                quickSort(a, left, mid-1);
                quickSort(a, mid+1, right);
            }
        }
    
        private static int partition(int[] a, int left, int right){
            int pivot = left;
            int value = a[pivot];
            while(left<right){
                while(left<right && a[right]>=value){  //一定要从右边开始
                    right--;
                }
                while(left<right && a[left]<=value){
                    left++;
                }
                if(left<right){
                    swap(a, left, right);
                }
            }
            swap(a, pivot, right);
            return right;
        }
    
        private static void swap(int[] a, int i, int j){
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

[20160907214428859]: /images/20210520/9dfbcf56f2484e2e8bc61be17176f8fc.png
[20160907214744862]: /images/20210520/47ded77054a44dd6a5426e080070557f.png
[LeetCode_Two Sum]: http://blog.csdn.net/qq_16234613/article/details/52691940
[Link 1]: https://blog.csdn.net/lkp1603645756/article/details/85008715