快速排序

　　　　　　　　　　　　　　快速排序

一起泡排序

每一次比较交换，选出最大的关键字放置到最后一个位置上。

时间复杂度：O（n^2）

例如：

　　　　

二快速排序

1 基本思想

通过一趟排序将待排序的记录分割成独立的两部分，

其中一部分记录的关键字均比另一部分的所有关键字小。

然后再分别对这两部分继续进行相同的排序分割。

树形结构如下：

　　　　

 

　　　　　　　　

通常选取待排序记录的第一个值作为基准比较值。

 

2 实现过程

（1）过程

　　　　

（2）分组

　　　　

（3）代码

//交换两个数的值
void swap(int& a,int &b)
{
    a = a + b;
    b = a - b;
    a = a - b;
}

 

//起泡排序
void BubbleSort(int *src,int len)
{
    int i,j;

    for (i = 0 ; i < len - 1; i++)
    {
        for(j = 0; j < len - i - 1; j++)
        {
            //将最大数往后移动
            if (src[j] > src[j+1])
            {
                swap(src[j],src[j+1]);    
            }
        }
    }
}

 

//快速排序
void quickSort(int *src,int start,int end)
{
    int low = start;
    int high = end;
    int temp = src[low];
    
    if (start < end)
    {
        //分组
        while(low < high)
        {
            while(low < high)
            {
                if (src[high] >= temp )
                {
                    high--;
                }
                else
                {
                    swap(src[low],src[high]);
                    break;
                }
            }

            while(low < high)
            {
                if (src[low] <= temp )
                {
                    low++;
                }
                else
                {
                    swap(src[low],src[high]);
                    break;
                }
            }
        }
        
        //递归
        quickSort(src,start, low - 1);
        quickSort(src,high + 1,end);
    }
}