快速排序

思路

1.对于一个数组，首先先选择一个基准值key，这个基准值可以随意选，但是一般选择的是这个数组的第一个元素a[0]
2.之后我们对于这个数组，把数组中所有比这个基准值key小的元素向基准值key的左边扔，把数组中所有比这个基准值key大的元素朝基准值key的右边扔
3.这样的话基准值key就成为了一个"分界线"，所有比基准值key小的元素都在基准值key的左边，所有比基准值key大的元素都在key的右边
4.之后我们在递归的对基准值key左边的序列和右边的序列进行快速排序
5.最终整个序列就是有序的了

图解

转载自http://www.pianshen.com/article/3751395422/

代码实现

package sort;

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a= {10,9,8,7,6,5,4,3,2,1,0};
        for(int k:a)
        {
            System.out.printf("%d ",k);
        }
        System.out.println();
        quickSort(a, 0, a.length-1);
        for(int k:a)
        {
            System.out.printf("%d ",k);
        }

    }

    public static void quickSort(int a[],int left,int right)
    {
        if(left>=right)
        {
            return ;
        }
        int i=left;
        int j=right;
        int key=a[left];
        while(i<j)
        {
            while(i<j&&key<a[j])//从右向左找到第一个比key小的值
            {
                j--;//朝前面寻找
            }
            a[i]=a[j];//找到之后向左移动
            while(i<j&&key>a[i])
            {
                i++;//从左向右找，找到第一个大于key的值
            }
            a[j]=a[i];//将比较大的值移动到右边

        }
        a[i]=key;//把key移动到中间来分割左右,i现在是分割左右的下标
        quickSort(a, left, i-1);
        quickSort(a, i+1, right);

    }

}

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：快速排序使用递归，递归使用栈，因此它的空间复杂度为O(logn)
• 稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法