排序：是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。（本帖只讨论内部排序）
常见排序：1.插入排序：直接插入，二分插入，希尔排序。
2.交换排序：冒泡排序，快速排序。
3.选择排序：直接选择，竞赛树，堆排序。
4.归并排序：二路，多路。
************************************************************
1.插入排序：
1.1直接插入：
1.1.1顺序存储
void InsertSorting(int R[],int n)
{
for(int i=1;i<n;i++)
{
int temp=R[i];
int j=i-1;
while((j>=0)&&(temp<R[j]))
{
R[j+1]=R[i];
j--;
}
R[j+1]=temp;
}
}
1.1.2链式存储
void InsertSorting(List l)
{
node *h,*s,*p,*q,*last;
h=l.h;
q=h;
p=h->next;
last=p->next;
for(;p->next!=null;last=last->next)
{
while((q!=p)&&(p->data>q->data))
{
s=q;
q=q->next;
}
if(q!=p)
{
s->next=p;
p->next=q;
}
p=last;
}
}
1.2.二分插入：
1.2顺序存储
void BInsertSort(int R[],int n)
{
for(int i=1;i<n;i++)
{
left=0; right=i-1;
int temp=R[i];
while(left<=right)
{
int middle=(left+right)/2;
if(temp<R[middle])
right=middle-1;
else
left=middle+1;
}
for(int j=i-1;j>=left;j--)
R[j+1]=R[j];
R[left]=temp;
}
}
1.3shell:
1.3略
2.交换排序
2.1冒泡排序
void BubbleSorting(int R[],int n)
{
for(i=1;i<n;i++)
{
bool change=0;
for(int j=n-1;j<=n;j--)
{
if(R[j]<R[j-1])
{
int temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
change=1;
}
if(!change)
return;
}
}
2.2快速排序
void QuickSort(int R[],int left,int right)
{
int i=left; int j=right;
int temp=R[i];
while(i<j)
{
while((R[j]>temp)&&(i<j))
j--;
if(i<j)
R[i]=R[j];
while((R[i]<temp)&&(i<j))
i++;
if(i<j)
R[j]=R[i];
}
R[i]=temp;
if(left<i-1) QuickSort(R,left, i-1);
if(right>i+1) QuickSort(R,i=1, right);
}
转载于:https://www.cnblogs.com/powerlc/archive/2005/08/26/223760.html
