数据结构内排序方法

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

数据结构排序方法

1、冒泡排序属于稳定排序，是一种借助“交换”进行排序的方法。首先要将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录与第三个记录的关键字，以此类推，直至第n-1个记录与第n个记录的关键字进行比较为止，这一过程称为第一趟冒泡排序，其结果使得关键字最大的记录被安置在最后一个记录的位置上；然后进行第二趟冒泡排序，对前N-1个记录进行同样操作；以此类推，直到在一趟排序过程中没有进行过交换记录的操作为止。

2、直接插入排序属于稳定的排序，每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟将待比较的数值与它的前一个数值进行比较，当前一数值比待比较数值大的情况下继续循环比较，依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程，结束该次循环。

3、快速排序属于不稳定排序，是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为{R.[s],R.[s+1],…….,R.[t]},首先任意选取一个记录，然后按下述原则从新排序记录：将关键字较他小的记录都安置在他的位置之前，将所有关键字较他大的记录都安置在他的位置后面。由此可以该“枢轴”记录最后所落的位置i作为分界线，将序列{R[s],R[s+1]…….R[t]}分割成两个子序列｛R[s],R[s+1]…..R[i-1]｝和｛R[i+1]……R[t]｝，这个过程称作一趟快速排序。一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向数组第一个数据和最后一个数据，将枢轴记录暂存在R[0]的位置上排序过程中只作R[low]或R[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。

4、简单选择排序属于不稳定排序，基本思想是，每一趟在n-i+1（i=1，2， n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。

5、希尔排序属于不稳定排序，也是一种属插入排序类，它的基本思想是：先将整个待排记录序列分割称为若干个子序列分别进行直接插入排序，待整个序列中记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的一个特点是：子序列的构成不是简单的“逐

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

段分割”，而是将相隔某个“增量”的记录组成一个子序列。

6、堆排序属于不稳定排序，它的基本思想是，先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区，再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key；由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆，然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。

程序流程图：

源程序：

#define NULL 0

#define n 10

#define FALSE 0

#define TRUE 1

#include <math.h>

typedef int KeyType;

typedef char InfoType;

typedef struct{

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

KeyType key;

InfoType otherinfo;

}RecType;

typedef RecType SqList[n+1];

int m,num; /*全局变量m和num存储输出的第趟结果及递归调用的次数*/

SqList R; /*记录待排序的个数*/

int times = 0;

/*--------------------------------冒泡排序--------------------------------------*/

void Bubblesort()

{/*R[1...n]是待排序的文件，采用自下向上扫描对R做冒泡排序*/

int i,j,k;

int exchange;

printf("请输入要输出第几趟结果：");

scanf("\n%d",&m);

for(i=1;i<n;i++)

{/*最多做n-1趟排序*/

exchange=FALSE;

for (j=n-1;j>=i;j--)

{

if (R[j+1].key<R[j].key)

{

R[0]=R[j+1];

R[j+1]=R[j];

R[j]=R[0];

exchange=TRUE;

}

}

if((i==m)||(!exchange))

{

printf("第%d趟的结果是：",m);

for (k=1;k<=n;k++)

printf("%5d",R[k].key);

printf("\n");

printf("请输入还要输出第几趟结果，不想输出时请输入：");

scanf("\n%d",&m);

}

if(!exchange) return(1);

}

printf("最终排序结果是：");

for (k=1;k<=n;k++)

printf("%5d",R[k].key);

printf("\n");

return(1);

}/*Bubblesort*/

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

/*-------------------------------直接插入排序----------------------------------*/

void Insertsort()

{

int i,j,k;

printf("请输入要输出第几趟结果：");

scanf("\n%d",&m);

for(i=2;i<=n;i++)

{

if(R[i].key<R[i-1].key)

{

R[0]=R[i]; j=i-1;

do

{R[j+1]=R[j];j--;}

while(R[0].key<R[j].key);

R[j+1]=R[0];

}

if (i-1==m)

{

printf("第%d趟的结果是：",m);

for(k=1;k<=n;k++)

printf("%5d",R[k].key);

printf("\n");

printf("请输入还要输出第几趟结果，不想输出时请输入：");

scanf("\n%d",&m);

}

}

printf("最终排序结果是：");

for(k=1;k<=n;k++)

printf("%5d",R[k].key);

printf("\n");

}

/*------------------------------快速排序---------------------------------------*/

int partion(SqList R,int low,int high)

{

int i,temp;

R[0].key=R[low].key;

while(low<high)

{

while(low<high&&R[high].key>=R[0].key)

high--;

temp =R[low].key;

R[low].key =R[high].key;

R[high].key = temp;

while(low<high&&R[low].key <=R[0].key)

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

low++;

temp = R[high].key;

R[high].key = R[low].key;

R[low].key = temp;

}

return low;

}

void Quicksort(int *L,int low,int high)

{

int pivotloc,k;

if(low<high)

{

pivotloc= partion(L,low,high);

times++;

printf("第%d趟的结果是：",times);

for(k=1;k<=n;k++)

printf(" %3d",R[k].key);

printf("\n");

Quicksort(L,low,pivotloc-1);

Quicksort(L,pivotloc+1,high);

}

}

/*--------------------------------简单选择排序--------------------------------*/

SelectSort()

{

int i,j,t,k;

int m = 1;

for(i=1;i<=n-1;i++)

{

k=i;

for(j=i+1;j<=n;j++)

if(R[j].key<R[k].key)

k=j;

if(i!=k)

{

t=R[i].key;

R[i].key=R[k].key;

R[k].key=t;

}

printf("第%d趟的结果是：",m);

for (k=1;k<=n;k++)

printf("%3d",R[k].key);

printf("\n");

m++;

}

printf("最终排序结果是：");

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

for(k=1;k<=n;k++)

printf("%3d",R[k].key);

printf("\n");

}

/*-------------------------------希尔排序--------------------------------------*/

void shellinsert(SqList L,int d)

{

int i,j,k;

for(i=d+1;i<=n;++i)

{

times++;

if(R[i].key<R[i-d].key)

{

L[0]=L[i];

for(j=i-d ; j>0&&(R[0].key<R[j].key) ; j-=d)

R[j+d].key=R[j].key;

R[j+d].key=R[0].key;

}

printf("第%d趟步长为%d的排序结果：",times,d);

for(k=1;k<=n;k++)

printf("%3d",R[k].key);

printf("\n");

}

}

void Shellsort(SqList L)

{

int k,dlta[3]={5,3,1};

times = 0;

for(k=0;k<3;++k)

shellinsert(L,dlta[k]);

printf("最终排序结果是：");

for(k=1;k<=n;k++)

printf("%3d",R[k].key);

printf("\n");

}

/*----------------------------------堆排序--------------------------------------*/

void HeapAdjust(SqList R,int s,int m)

{

int j;

R[0].key=R[s].key;

for(j=2*s; j<=m; j*=2)

{

if(j<m && R[j].key<R[j+1].key)

++j;

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

if(!(R[0].key<R[j].key))

break;

R[s].key=R[j].key;

s=j;

}

R[s].key=R[0].key;

}

void HeapSort(SqList R)

{

int i,exch,k;

for(i=n/2;i>0;--i)

{

HeapAdjust(R,i,n);

}

for(i= n;i>1;--i)

{

exch=R[1].key;

R[1].key=R[i].key;

R[i].key=exch;

HeapAdjust(R,1,i-1);

printf("第%d趟的排序结果:",n-i+1);

for(k=1;k<=n;k++)

printf(" %3d ",R[k]);

printf("\n");

}

}

/*---------------------------------主程序--------------------------------------*/

void main()

{

char ch1,ch2; int i;

printf("请输入个待排序数据:(每个数据间用空格隔开)\n");

for(i=1;i<=n;i++)

scanf("%d",&R[i].key);

R[0].key = 12;R[1].key = 18;R[2].key = 24;R[3].key = 5;R[4].key = 1;R[5].key = 32;R[6].key = 8;

R[7].key =41;R[8].key = 17;R[9].key = 22;R[10].key = 10;

ch1='t';

printf("\n欢迎进入排序算法程序，请选择：\n");

while(ch1=='t'||ch1=='T')

{

printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");

printf("┃ 欢迎使用内部排序 ┃\n");

printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

冒泡排序直接插入排序快速排序简单选择排序希尔排序堆排序

printf("┃1 冒泡排序算法 ┃\n");

printf("┃2 直接插入排序算法 ┃\n");

printf("┃3 快速排序算法 ┃\n");

printf("┃4 简单选择排序算法 ┃\n");

printf("┃5 希尔排序算 ┃\n");

printf("┃6 堆排序 ┃\n");

printf("┃7 退出 ┃\n");

printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");

scanf("\n%c",&ch2);

switch(ch2)

{

case '1':printf("冒泡排序算法:\n");

Bubblesort();break;

case '2':printf("直接插入排序算法:\n");

Insertsort();break;

case '3':printf("快速排序算法:\n");

Quicksort(R,1,10);break;

case '4':printf("简单选择排序算法:\n");

SelectSort(R);break;

case '5':printf("希尔排序算法:\n");

Shellsort(R);break;

case '6':printf("堆排序算法:\n");

HeapSort(R);break;

case '7':ch1='n';break;

default:ch1='n';

}

}

}

本文来源：https://www.bwwdw.com/article/4641.html