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

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

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

/*

*时间  2018.6.27

*作者  JiCunRen

*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


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 <num&&flag == 1; 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 <num; 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<high){
while (low<high&&dic->element[high].key >= pivotkey)
high--;
swap(dic, low, high);
while (low<high&&dic->element[low].key <= pivotkey)
low++;
swap(dic, low, high);
}
return low;
}
void QSort(SqList *dic, int low, int high){
int pivot;
if (low <high){
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 <num; 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 <num; 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 <num; 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;
}