最后一部分 排序

概念

任意n个关键字基于比较的排序,至少要进行log₂[上取整(n!)]

插入排序

直接插入排序

void InsertSort(ElemType A[],int n)
{
    int i,j,temp;
    for(i=0;i<n;i++)
    {
        if(A[i]<A[i-1])
        {
            temp=A[i];
            for(j=i-1;j>=0&&A[j]>temp;j--)//后移
            {
                A[j+1]=A[j];
            }
            A[j+1]=temp;
        }
    }
}

折半插入排序

void InsertSort(ElemType A[],int n)
{
    int i,j,low,high;
    for(i=2;i<=n;i++)
    {
        A[0]=A[i];
        low=1;high=i-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(A[mid]>A[0]) high=mid-1;//中间元素更大,说明要往左边再找
            else low=mid+1;//包括了等于,保证稳定性,因为如果等于,还是往右边找,就可以保证顺序不变
        }
        for(j=i-1;j>=low;j--)//也即为high+1开始,因为high=low-1是结束的标志
        {
            A[j+1]=A[j];
        }
        A[low]=A[0];//其实j+1也对

    }

}

shell 排序

void ShellSort(ElemType A[],int n)
{
    int i,j,dk;
    for(dk=n/2;dk>=1;dk=dk/2)
    {
        for(i=1+dk;i<=n;i++)//轮流切换分组处理,类似于进程切换,但在画图写的时候,咱是分好组之后,在每组内使用直接插入排序,但是代码中是一个接一个的使用组内插入排序的,实际上也是一样的
        {
            if(A[i]<A[i-dk])
            {
                A[0]=A[i]
                for(j=i-dk;j>0;j-=dk)
                {
                    A[j+dk]=A[j];
                }
                A[j+dk]=A[0];
            }

        }
    }
}

交换排序

冒泡排序

void BubbleSort(ElemType A[],int n)
{
    int i,j;
    bool flag;
    for(i=0;i<n-1;i++)
    {
        flag=false;
        for(j=n-1;j>i;j--)
        {
            if(A[j-1]>A[j])
            {
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false)
        return;
    }
}

快速排序

递归实现

#include <stdio.h>
#define ElemType int
int MyPartition(ElemType A[],int low,int high);
void QuickSort(ElemType A[],int low,int high)
{
    if(low<high)
    {
        int pivotpos;
        pivotpos=MyPartition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }

}
int MyPartition(ElemType A[],int low,int high)
{
    ElemType 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;
}
int AnotherPartition(ElemType A[],int low,int high)
{
    ElemType pivot=A[low];
    int i=low;
    for(int j=low+1;j<=high;j++)
    {
        if(A[j]<pivot)
            swap(A[++i],A[j]);
    }
    swap(A[i],A[low]);
    return i;
}
int main()
{
	int A[10]={23,54,1,33,58,11,67,24,5,8};
   /* 我的第一个 C 程序 */
    int i=0;
	QuickSort(A,0,9);
	i=0;
	printf("ssss\n");
	while(i<=9)
	{
		printf("%d\n",A[i]);
		i++;
	}
   printf("Hello, World! \n");

   return 0;
}

利用交换思想解决问题

1. 荷兰旗

#include <stdio.h>
int swap(int *a,int *b)
{
	int temp=*a;
	*a=*b;
	*b=temp;
	return 0;
}
void Classify(int a[],int n)
{
	int i=0,j=0,k=n-1;
	while(j<=k)
	{
		switch(a[j]){
			case 0:swap(&a[j],&a[i]);j++;i++;break;
			case 1:j++;break;
			case 2:swap(&a[j],&a[k]);k--;break;
		}
	}
	
}
int main()
{
	int a[15]={1,2,1,2,0,1,0,2,0,1,0,0,2,2,1};
	Classify(a,15);
	int i=0;
	while(i<15){
		printf("%d  ",a[i]);
		i++;
	}
   return 0;
}

选择排序

简单选择排序

void SimpleSelectSort(ElemType A[],int n)
{
    int i,j,min;
    for(i=0;i<n-1;i++)
    {
        min=i;
        for(j=i+1;j<n;j++)
        {
            if(A[j]<A[min])
            {
                min=j;
            }
        }
        if(min!=i) swap(A[i],A[min]);
    }
}

堆排序

void BuildMaxHeap(ElemType A[],int len)
{
    for(int i=len/2;i>0;i--)
    {
        HeadAdjust(A,i,len);
    }
}
void HeapAdjust(ElemType A[],int k,int ken)
{
    A[0]=A[k];
    for(i=2*k;i<=len;i*=2)
    {
        if(i<len&&A[i]<A[i+1])//i<len:保证有右兄弟,后面的是是否比右兄弟小
            i++;
        if(A[0]>=A[i])//比孩子结点大,直接退了
        {
            break;
        }
        else
        {
            A[k]=A[i];
            k=i;//转到孩子结点继续判断
        }
    }
    A[k]=A[0];
}
void HeapSort(ElemType A[],int len)
{
    BuildHeapMax(A,len);
    for(int i=len;i>1;i--)
    {
        swap(A[i],A[1]);
        HeapAdjust(A,1,i-1);//由于最后一个元素就是最大元素了,故只调整前面的
    }
}