计算机考研常用算法分享(六) 排序

void SelectSort(int * a,int n)
{
    int i,j,k;
    int temp;
    for(i = 0; i < n; i++)
    {
        k = i;
        //循环得到待排序序列的最小元素
        for(j = i+1; j < n; j++)
        {
            if(a[k] > a[j])
                k = j;
        }
        //交换两个元素
        temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
}

void bSort(int * a,int max)
{
    int i,j,flag;
    for(i = 0; i < max - 1; i++)
    {
        flag = 0;
        for(j = 0; j < max - i - 1; j++)
        {
            if(a[j] < a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = 1;
            }
        }
        if(!flag) 		//如果没有发生交换表示后续序列已经有序,结束循环
        {
            return 0;
        }
    }
}

void in_sort(int * a,int n)
{
    int i,j,temp;       //temp充当了哨兵
    for(i = 1; i < n; i++)      //这里是从第二个元素开始比
    {
        temp = a[i];
        j = i - 1;
        //如果temp小于其之前的元素,让这个元素后移,直到找到合适位置
        while(j >= 0 && temp < a[j]) 		//降序只需要改 temp > a[j]
        {
            a[j+1] = a[j];  //后移
            --j;
        }
        a[j+1] = temp;      //插入
    }
}
void in_sort(int * a,int n)
{
    int i,j,temp;
    for(i = 1; i < n; i++) 		//这里加if(a[i] < a[i+1])升序可以简化算法
    {
        temp = a[i];
        for(j = i - 1; j >= 0; j--)
        {
            a[j+1] = a[j];
        }
        a[j+1] = temp;
    }
}

①第一种算法

int partition(int * a,int low,int high)
{
    int pivot = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= pivot)   --high;
        a[low] = a[high];
        while(low < high && a[low] <= pivot)   ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

void quickSort(int * a,int low,int high)
{
    if(low < high)
    {
        int pos = partition(a,low,high);
        quickSort(a,low,pos-1);
        quickSort(a,pos+1,high);
    }
}

②第二种算法

void quicksort(int a[],int left,int right)
{
    int i,j,temp;
    i=left;
    j=right;
    temp=a[left];
    if(left>right)
        return;
    while(i!=j)
    {
        while(a[j]>=temp&&j>i)
            j--;
        if(j>i)
            a[i++]=a[j];
        while(a[i]<=temp&&j>i)
            i++;
        if(j>i)
            a[j--]=a[i];
	}
    a[i]=temp;
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}