数据结构中的各类排序方法

在计算机的世界里有着各种各样的排序，现在就给大家简单的介绍下我的期末作业（数据结构C++版），有着冒泡排序：排序中的经典，希尔排序，快速排序，直接插入排序，简单选择排序。

希望这些可以帮助一下那些和我一样学习数据结构的朋友，元旦了祝大家新年快乐，么么哒

以下是程序的源码还有测试截图。

#include

#include

#define N 100

#define SIZE 15

typedef struct {

int key; //关键字的值

}SLNode;

typedef struct {

SLNode r[SIZE];//存储记录的数组

int length;//记录数组中记录的数量

}SqList;

int count=0,count2=0;//count2比较次数,count移动次数

void showArray(int a[],int len){

for(int i=0;i

printf("%d ",a[i]);

}

}

/**************************************/

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

/**************************************/

void print(int a[], int n ,int i){

printf("第%d趟排序后:",i);

for(int j=0; j

printf("%d ",a[j]);

}

printf("\n");

}

//直接插入排序函数

void InsertSort(int a[], int n)

{

count=0;

count2=0;

for(int i= 1; i

int j= i-1;

int x = a[i];

while(j>-1 && x

a[j+1] = a[j];

count++;

j--;

}

a[j+1] = x; //插入到正确位置

}

count++;

count2++;

print(a,n,i);//打印每次排序后的结果

}

}

/**************************************/

/*****************END ************/

/**************************************/

/**************************************/

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

/**************************************/

void ShellInsert(SqList * L,int dk){

//从 dk+1 个记录起，每间隔 dk 个记录就调取一个进行直接插入排序算法

for (int i=dk+1; ilength; i++) {

//如果新调取的关键字的值，比子表中最后一个记录的关键字小，说明需要将该值调换位置

if (L->r[i].keyr[i-dk].key) {

int j;

//记录表中，使用位置下标为 0 的空间存储需要调换位置的记录的值

L->r[0]=L->r[i];

//做直接插入排序，如果下标为 0 的关键字比下标为 j 的关键字小，则向后一行下标为 j 的值，为新插入的记录腾出空间。

for (j=i-dk; j>0 && (L->r[0].keyr[j].key); j-=dk){

L->r[j+dk]=L->r[j];

count++;

}

//跳出循环后，将新的记录值插入到腾出的空间中，即完成了一次直接插入排序

L->r[j+dk]=L->r[0];

count++;

}

count2++;

}

}

//希尔排序，通过调用不同的增量值（记录），实现对多个子表分别进行直接插入排序

void ShellSort(SqList * L,int dlta[],int t){

for (int k=0; k

ShellInsert(L, dlta[k]);

}

}

/**************************************/

/*****************END********/

/**************************************/

/**************************************/

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

/**************************************/

void swap(int* a,int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

void bubbleSort(int a[],int len)

{

int i,j;

count=0;

count2=0;

for(i=1;i

{

for(j=0;j

{

if(a[j]>a[j+1])

{

swap(&a[j],&a[j+1]);

count++;

}

count2++;

printf("\n%d次排序:",count2);

for(int x=0;x

printf("%3d",a[x]);

putchar('\n');

}

}

}

/**************************************/

/*****************END *****************/

/**************************************/

/**************************************/

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

/**************************************/

int partition(int arr[], int low, int high){

int key;

key = arr[low];

while(low

while(low = key )

high--;

if(low

arr[low++] = arr[high];

count++;

}

while( low

low++;

if(low

arr[high--] = arr[low];

count++;

}

}

arr[low] = key;

return low;

}

void quick_sort(int arr[], int start, int end){

int pos;

if (start

pos = partition(arr, start, end);

quick_sort(arr,start,pos-1);

quick_sort(arr,pos+1,end);

}

return;

}

/**************************************/

/*****************END *****************/

/**************************************/

int main()

{

int dlta[3]=;

int number=0,i=0;

int array[N];

char choice;

SqList *L=(SqList*)malloc(sizeof(SqList));

while(true)

{

printf("请输入待排序记录的个数:");

scanf("%d",&number);

printf("请依次输入%d个待排序整数:",number);

for(i=0;i

scanf("%d",&array[i]);

printf("--------------------------------------------\n");

printf("A:直接插入排序 B:希尔排序 C:冒泡排序\n");

printf("D:快速排序 E:简单选择排序 F:堆排序 \n");

printf("0:退出 \n");

printf("--------------------------------------------\n");

printf("请选择排序算法:");

getchar();

choice=getchar();

switch(choice)

{

case 'a':

case 'A':

InsertSort(array,number);

printf("\n直接排序时间性能分析:");

printf("\n进行了%d次比较,移动了%d次\n",count2,count-1);

break;

case 'b':

case 'B':

for(int l=1;l

L->r[l].key=array[l-1];

L->length=number;

ShellSort(L, dlta, 3);

printf("排序后的顺序为：");

for (int i=1; i

printf("%d ",L->r[i].key);

printf("\n希尔排序时间性能分析:");

printf("\n进行了%d次比较,移动了%d次\n",count2,count);

break;

case 'c':

case 'C':

bubbleSort(array,number);

printf("\n冒泡排序时间性能分析:");

printf("\n进行了%d次比较,移动了%d次\n",count2,count);

break;

case 'd':

case 'D':

count=0;

quick_sort(array,0,number-1);

printf("排序后的顺序为：");

showArray(array,number);

printf("\n%d次比较!",count);

putchar('\n');

break;

default:printf("Error!\n");

}

system("pause");

system("cls");

}

return 0;

}

程序测试截图

程序测试截图

程序测试截图

希望这些能给你有些帮助。