快排理解以及算法

快排思想：通过每一次排序分成俩个部分，第一部分全部小于第二部分；

以此类推，每一部分的第一部分都小于第二部分，运用了分治的思想；

（升序排序）过程：

1.先从数列中选一个数当作基准数P；【i】指向第一个元素和【j】指向最后一个元素；

2.【j】先从后往前找，找到一个小于等于P的数，交换【i】和【j】的值；

3.【i】开始从前往后找，找到大于P的数，交换【i】和【j】的值；

4.直到i=j位置，开始下一个分区。

例子：

开始先让【i】指向第一个元素【j】指向最后一个元素

设基准数P为第一个元素

此时P=28

j > i   进入程序

从后往前

第一个元素就发现arr[j]=20小于P

交换i，j的元素

继续，从前往后，当i指向31是发现大于P，交换i，j的元素

从后往前，当j指向17发现小于P，交换

从前往后，i指向97时大于P，交换

从后往前，当j指向28时i==j，跳出循环，第一步的快排完成，然后递归分治。

程序如下：

void Quick_Sort(int arr[],int l,int r){
    if(r-l>0){
        int i = l;
        int j=r;
        int p = arr[l];
        while(i<j){
            while(i<j&&arr[j]>=p)
                j--;
            swap(arr[i], arr[j]);
            while(i<j&&arr[i]<p)
                i++;
            swap(arr[i], arr[j]);
        }
        Quick_Sort(arr,l,i-1);
        Quick_Sort(arr, i + 1, r);
    }
}

分治递归时

Quick_Sort(arr,l,i-1);代表从第一部分从开头到基准的前一个位置

Quick_Sort(arr,l,i-1);代表从基准后一个开始到结尾的位置

注意，调用函数时候应当

Quick_Sort(arr,0,N-1)
N-1表示最后一个元素

快排理解以及算法

原文：https://www.cnblogs.com/Itukas/p/12292333.html