1.快速排序:

算法描述:

• 从待排序记录序列中选取一个记录(这个可以任意选取一个数字，通常选取第一个记录)为枢轴，其关键字设为K1;
• 然后将其余关键字小于K1的记录移到前面，而将关键字大于或者等于K1的记录移到后面，结果将待排序记录序列分为两个子表，最后将关键字K1的值插入到分界线的位置。将这个过程称为一趟快速排序.
• 通过一次划分后，就以关键字为K1的值为界，将待排序序列分成了两个子表，且前边子表中所有记录的值均小于K1，而后面子表中的所有的值均大于或等于K1。
• 对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表.

其实快速排序是基于分治思想

算法分析

y总模板:

void quick_sort(int num[],int l,int r)
{
    if(l>=r) return;

    int i=l-1,j=r+1,mid=num[l];
    while(l<r)
    {
        do i++; while(num[i]<mid);
        do j--; while(num[i]>mid);
        if(i<j) swap(num[i],num[j]);
        else break;
    }
    quick_sort(num,l,j);qucik_sort(num,j+1,r);
}

y总这个代码的思路和学数据结构时老师讲的还不一样，老师当时是先从num[j]开始比较的，其实不管是从num[j]还是num[i]最后结果都是一样的.

#include<iostream>
using namespace std;

int num[]={12,2,16,30,28,10,16,20,6,18};
void quick_sort(int num[],int l,int r)
{
    if(l>=r) return;

    int i=l-1,j=r+1,mid=num[l];
    while(i<j)
    {
        do i++; while(num[i]<mid);
        do j--; while(num[j]>mid);
        if(i<j) swap(num[i],num[j]);
        else break;
    }

    cout<<i<<" "<<j<<endl;
    quick_sort(num,l,j),quick_sort(num,j+1,r);
    //quick_sort(num, l, i-1), quick_sort(num, i, r);这样不行，会陷入死循环 .如果非要用i的话，那么就要更改mid=num[r];其实这个只需要背过一个就行
}

int main()
{
    quick_sort(num,0,9);
    for(int i=0;i<=9;++i)
        cout<<num[i]<<" ";
}

所以还是按照y总的模板走!!!

下面回忆一下do…while:

2.归并排序:

算法描述:

算法分析

y总模板:

void merge_sort(int num[],int l,int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;//等价于mid = (l + r)/2;
    merge_sort(num, l, mid);
    merge_sort(num, mid + 1, r);

    int k=0,i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(num[i] < num[j]) tmp[k ++] = num[i ++];
        else tmp[k ++] =num[j ++];

    while(i <= mid)  tmp[k ++] = num[i ++];
    while(j <= r) tmp[k ++] = num[j ++];

    for(i = l, j = 0; i <= r; ++ i, ++j) num[i] = tmp[j];
 }