算法笔记_快排

几个核心

1）相对于冒泡排序，快排在一次遍历的时候不是光邻居互换，他是右边探测的点和左边探测的点大跨步互换。

2）通过分治的思想提高排序的效率

如何才能熟练的掌握快排的编码

+ 入参分左右，整个过程是个递归过程

+ 退出条件是左边坐标大于或者等于右边。

如果等于说明这个递归说处理的数据片段只有一个数据，那自然不用处理，如果小于，说明递归要处理的数据段已经溢出。不需要处理

+ 把最左边的数据定位基准。

+ 从最右边和最左边分别开始探查，双索引探查，只要这连个索引不重合就继续探查。探查步骤是，先从最右边开始找比基准小的值，然后从最左边开始找比基准大的值。找到后完成一次交换，如果索引重合了，就和基准交换。

+ 基准交换后，二分开始递归。

```

void qSort(int a[], int left, int right)

{

if(left>=right)

    return;

int i = left;

int j = right;

int base = a[left];

while(i!=j)

{

while(a[j]>=temp && j>i)

    j--;

while(a[i]>=temp && i<j)

    i++；

if(i<j)

    swap()

}

swap_base;

qSort(a,left, i-1);

qSort(a,i+1, right);

```