快速排序

学习数据结构与算法的肯定会接触到快速排序，包括很多面试都会问你快排怎么些。以前在学习快排的时候搜过很多文章，但是大部分的代码写的都有一些问题，所以决定自己动手写一个可以有效运行的快排代码了。

快速排序的步骤：

1.选取一个基准值，这里选数组最左边的值作为示例

2.给数组设置两个游标，两个游标的初始位置一个在数组最左边，一个在数组最右边。

3.先移动数组右边的游标，直到找他第一个比基准值小的数则停止，再移动数组左边的游标， 直到找到第一个比基准值大的数则停止。然后交换两个游标位置的数。

4.继续执行第三个步骤，直到左边的游标跟右边的游标相遇为止，则停止循环。

5.将基准值与游标位置的值交换。

6.对基准值左边的数和右边的数分别进行递归快速排序。

7.当快速排序的数组只有一个值得时候，退出递归。

实现代码:

public class QuickSort {

public static void main(String []args){

int []arr = {6,4,7,3,2,9,8,10};

        quick_sort(arr,0,7);

        display(arr);

    }

public static void quick_sort(int arr[],int l,int r){

int left,right,key;

        left = l;

        right = r;

        key = arr[l]; //保存基准值

//如果只剩下一个值为一组，则退出，不再递归：递归的出口

        if(l - r >=0){

return;

        }

//循环的条件是left ！= right

        while(left != right){

while(arr[right] >= key && right > left){

right --;

            }

while(arr[left] <= key && right > left){

left ++;

            }

if(left

int temp = arr[left];

                arr[left] = arr[right];

                arr[right] = temp;

            }

}

//循环完之后，将基准值与最后游标所在位置的值交换，这样基准值左边都是小于他的数，右遍都是大于他的数

        arr[l] = arr[left];

        arr[left] = key;

        //对基准值的左边数组和右遍数组分别进行递归

        quick_sort(arr,l,left-1);

        quick_sort(arr,left+1,r);

    }

public static void display(int[] a){

for (int i =0; i< a.length-1; i++){

System.out.print(a[i]+"->");

        }

System.out.print(a[a.length-1]);

    }

}

快速排序的最坏时间复杂度是O(n2),平均之间复杂度是O(nlogn)