五大排序算法及测试----冒泡、快速、选择、希尔、直接插入排序

五大排序算法及测试----冒泡、快速、选择、希尔、直接插入排序。

/*本文档是自己写的五大排序算法以及测试，记录在这儿，以后自己可以查看，希望大家也可以进行参考*/

/*生成的数是以时间为种子的随机数*/

/*

*时间 ?2018.6.27

*作者 ?JiCunRen

*/

#include

#include

#include

typedef struct ?dicnode {

int key;

}DIC;

typedef struct mydic{

int ? ?n;

DIC *element;

int length;

}SqList;

SqList *dic;

//创建随机数

void create(int num)

{

int i;

dic = (SqList *)malloc(sizeof(struct mydic));

if (dic)

{

dic->element = (DIC *)malloc(sizeof(struct dicnode)*num);

dic->n = 0;

}

srand((unsigned)time(0));

for (i = 0; i < num; i++){

dic->element[i].key = rand() % 100;

}

}

void swap(SqList *dic, int i, int j){

DIC temp = dic->element[i];

dic->element[i] = dic->element[j];

dic->element[j] = temp;

}

//冒泡排序

void BubbleSort(int num){

int i, j;

int flag = 1;

for (i = 0; i flag = 0;

for (j = num - 2; j >= i; j--){

if (dic->element[j].key>dic->element[j + 1].key){

swap(dic, j, j + 1);

flag = 1;

}

}

}

printf(" ? ? 冒泡排序：");

for (i = 0; i printf("%d ", dic->element[i].key);

printf("\n");

}

//快速排序

int Partition(SqList *dic, int ?low, int high){

int pivotkey;

pivotkey = dic->element[low].key;

while (low while (lowelement[high].key >= pivotkey)

high--;

swap(dic, low, high);

while (lowelement[low].key <= pivotkey)

low++;

swap(dic, low, high);

}

return low;

}

void QSort(SqList *dic, int low, int high){

int pivot;

if (low pivot = Partition(dic, low, high);

QSort(dic, low, pivot - 1);

QSort(dic, pivot + 1, high);

}

}

void QuictSort(int num){

int i;

QSort(dic, 0, num - 1);

printf(" ? ? 快速排序：");

for (i = 0; i printf("%d ", dic->element[i].key);

printf("\n");

}

//直接插入排序

void InsertSort(int num){

int i, j, temp = 0;

for (i = 1; i < num; i++){

if (dic->element[i].key < dic->element[i - 1].key){

temp = dic->element[i].key;

for (j = i - 1; dic->element[j].key>temp; j--)

dic->element[j + 1].key = dic->element[j].key;

dic->element[j + 1].key = temp;

}

}

printf(" 直接插入排序：");

for (i = 0; i printf("%d ", dic->element[i].key);

printf("\n");

}

//希尔排序

void ShellSort(int num){

int i, j, temp = 0;

int increment = num;

do{

increment = increment / 3 + 1;

for (i = increment; i < num; i++){

if (dic->element[i].key < dic->element[i - increment].key){

temp = dic->element[i].key;

for (j = i - increment; j >= 0 && temp < dic->element[j].key; j -= increment)

dic->element[j + increment].key = dic->element[j].key;

dic->element[j + increment].key = temp;

}

}

} while (increment > 1);

printf(" ? ? 希尔排序：");

for (i = num; i >0; i--)

printf("%d ", dic->element[i - 1].key);

printf("\n");

}

//选择排序

void SelectSort(int num){

int i, j, temp = 0, min;

for (i = 0; i < num - 1; i++){

min = i;

for (j = i + 1; j < num; j++){

if (dic->element[min].key>dic->element[j].key)

min = j;

}

if (i != min)

swap(dic, i, min);

}

printf(" ? ? 选择排序：");

for (i = 0; i printf("%d ", dic->element[i].key);

printf("\n");

}

int main(){

int num, i,Sort;

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

printf("0、exit\n");

printf("1、BubbleSort\n");

printf("2、QuictSort\n");

printf("3、InsertSort\n");

printf("4、ShellSort\n");

printf("5、SelectSort\n");

for (;;){

printf("\nEnter you dic(0---exit):");

scanf_s("%d", &num);

if (num == 0) return 0;

create(num);

printf("Print the dic:");

for (i = 0; i < num; i++)

printf(" %d", dic->element[i].key);

printf("\n请选择操作:");

scanf("%d", &Sort);

switch (Sort){

case 0:return 0;

case 1:BubbleSort(num);

break;

case 2:QuictSort(num);

break;

case 3:InsertSort(num);

break;

case 4:ShellSort(num);

break;

case 5:SelectSort(num);

break;

}

}

return 0;

}