快速排序算法

讲道理,自从用起了C++库函数里的sort()函数,就再也没手写过快速排序。思路虽懂,但还是要练练手。
快速排序

0X001 介绍快排

快速排序= = 不想讲的很细节怎么办。
快排就是一种分治思想,然后涉及到递归,讲真大一刚学的时候,递归让我头疼了很久。
该方法的基本思想是:

1.先从数列中取出一个数作为基准数

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。


0X002 快排举例

以一个数组作为示例,取区间第一个数为基准数。

快排例子1

初始时,i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为:
快排例子2

i = 3; j = 7; X=72

再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

数组变为:
快排例子3

可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。


0X003 快排总结

1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。


0X004 代码实现

void QuickSort(int a[],int l,int r)
{
    if(l<r)
    {
        int i=l,j=r,x=a[l];
     while(i<j)
     {
     while(i<j && a[j]>=x) //向右扫 
         j--;
     if(i<j) 
     {
         a[i]=a[j];
         i++;
         //a[i++]=a[j]; 
    }
    while(i<j && a[i]<x) //向左扫 
        i++;
    if(i<j)
    {
        a[j]=a[i];
        j--;
        //a[j--]=a[i];
    }
    }
    s[i]=x;
    QuickSort(a,l,i-1);//递归调用 不好理解 
        QuickSort(a,i+1,r);
}
}

添加新评论