本文主要是介绍七种排序方式总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*2018.01.23
*A:YUAN
*T:其中排序算法：冒泡排序，简单排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序
*/#include <stdio.h>
#include <math.h>
#include <malloc.h>#define MAXSIZE 10000
#define FALSE 0
#define TRUE 1typedef struct
{int r[MAXSIZE]; //用于存储要排序的数组，r[0]作为哨兵或者临时变量int length; //用于记录顺序表的长度
}SqList;void swap(SqList *L,int i,int j)
{int temp;temp=L->r[i];L->r[i]=L->r[j];L->r[j]=temp;
}//冒泡排序1
void Bubble_Sort0(SqList *L)
{int i,j;int status = TRUE;//以status作为标记,改进增加for(i = 0;i < L->length;i++){status = FALSE;//改进增加//for(j = i+1;j<L->length;j++)//基本冒泡算法for(j = L->length - 1;j>=i;j--)//改进冒泡法{//if(L->r[i]>L->r[j]) //对应基本冒泡算法if(L->r[j]>L->r[j+1])//对应改进冒泡法{swap(L,j,j+1);//交换两者的值status = TRUE;//改进增加}}}}//简单排序法
void Simple_Selection_Sort(SqList *L)
{int i,j,min;for(i = 0;i < L->length;i++){min = i;for(j = i+1;j < L->length;j++){if(L->r[j]<L->r[i]){min = j;}}if(i != min)swap(L,i,min);}
}void Straight_Insertion_Sort(SqList *L)
{int i,j;for(i = 2;i<L->length;i++){if(L->r[i] < L->r[i - 1]){L->r[0] = L->r[i];for(j = i - 1;L->r[j]>L->r[0];j--){L->r[j+1] = L->r[j];}L->r[j+1] = L->r[0];}}
}void Shell_Sort(SqList *L)
{//r[0] 作为哨兵（即缓存）int i,j,parameter;parameter = L->length;do{parameter = parameter/3+1;for(i = parameter + 1;i <= L->length;i++){if(L->r[i] < L->r[i - parameter])//需要将L->r[i] 插入有序增量子表{L->r[0] = L->r[i];for(j = i - parameter;j>0 && L->r[0]<L->r[j];j-=parameter){L->r[j+parameter] = L->r[j];}L->r[j+parameter] = L->r[0];}}}while(parameter > 1);
}//堆排序
void Heap_Ajust(SqList *L,int s,int m)
{int temp,j;temp = L->r[m];for(j = 2*s;j<=m;j*=2){if(j<m && L->r[j] < L->r[j+1])++j;if(temp >= L->r[j])s=j;}L->r[s]=temp;
}void Heap_Sort(SqList *L)
{int i;for(i=L->length/2;i>0;i--){Heap_Ajust(L,i,L->length);}for(i = L->length;i>1;i--){swap(L,1,i);Heap_Ajust(L,1,i-1);}
}//快速排序——此时在它之前（后）的记录均不大于（小）它
int Partitiom(SqList *L,int low,int high)
{int pivotkey;pivotkey = L->r[low];while(low < high){while(low < high && L->r[high]>=pivotkey)high--;swap(L,low,high);while(low < high && L->r[low]<=pivotkey)low++;swap(L,low,high);}return low;
}void QSort(SqList *L,int low,int high)
{int pivot;if(low < high){pivot = Partitiom(L,low,high);//将L->r[low..high]一分为二，算出枢轴值pivotQSort(L,low,pivot - 1); //对低子表递归排序QSort(L,pivot + 1,high); //对高子表递归排序}
}void QuickSort(SqList *L)
{QSort(L,1,L->length);
}//归并排序
/*归并排序的归并函数*/
void Merge(int SR[], int TR[], int i, int middle, int rightend) {//实际上这里的i也就是要排序合并的数组段的左起始点 int j, k, l; for (k = i, j = middle + 1; i <= middle&&j <= rightend; k++) { if (SR[i] < SR[j])/*将SR中的元素按小到大的顺序存入TR,只需比较中点两侧对应下标元素大小*/ TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i <= middle) {/*若中点左边元素剩余,将剩余元素并入TR(注意这里并入只要按照顺序即可,因为SR已经排好序了)*/ for (l = 0; l <= middle - i; l++) TR[k + l] = SR[i + l]; } if (j <= rightend) {/*若中点右边元素剩余,将剩余元素并入TR*/ for (l = 0; l <= rightend - j; l++) TR[k + l] = SR[j + l]; }
} /*归并排序递归函数*/
void MSort(int SR[], int TR1[], int s, int t) { int middle; int TR2[MAXSIZE + 1]; if (s == t) TR1[s] = SR[s]; else { middle = (s + t) / 2;/*将SR分成以middle为界的两部分*/ MSort(SR, TR2, s, middle);/*递归将SR[s,middle]归并为有序的数组TR2*/ MSort(SR, TR2, middle + 1, t);/*递归将SR[middle+1,t]归并为有序的数组TR2*/ Merge(TR2, TR1, s, middle, t);/*将上面的两部分分别有序的TR2归并为总体有序的TR1*/ }
} /*总体调用排序函数*/
void MergeSort(SqList *S) { MSort(S->r, S->r, 1, S->length);
} int main(void)
{int i;int temp;
/*//冒泡排序法
#if 0SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}Bubble_Sort0(&L); //冒泡排序法for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}#else
// SqList *L;//直接定义一个指针是没有指向的，是野指针,程序运行会出错SqList *L=malloc(sizeof(SqList));L->length = MAXSIZE;temp = L->length;for(i = 0;i<L->length;i++){L->r[i] = temp--; //逆序赋值}Bubble_Sort0(L); //冒泡排序法for(i = 0;i<L->length;i++){printf("r[%d] = %d.\n",i,L->r[i]); //顺序输出}
#endif*//*//简单排序法SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}Simple_Selection_Sort(&L); //简单排序法for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}*//*//直接插入排序算法SqList L;L.length = MAXSIZE;temp = L.length;for(i = 1;i<L.length;i++){L.r[i] = temp--; //逆序赋值}Straight_Insertion_Sort(&L); //直接插入排序法for(i = 1;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}*//*//希尔排序SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}Shell_Sort(&L); //希尔排序for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}*/
/*//堆排序示例SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}Heap_Sort(&L); //堆排序for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}*//*//快速排序示例SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}QuickSort(&L); //快速排序for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}*///归并排序SqList L;L.length = MAXSIZE;temp = L.length;for(i = 0;i<L.length;i++){L.r[i] = temp--; //逆序赋值}printf("before sort.\n");MergeSort(&L); //归并排序for(i = 0;i<L.length;i++){printf("r[%d] = %d.\n",i,L.r[i]); //顺序输出}
}
这篇关于七种排序方式总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
