实验-各种排序方法的比较.doc

实验六 各种排序方法的比较 一、 实验目的1通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的认识。2掌握各种排序方法的基本思想和算法实现。3能够灵活地选用某种排序方法解决问题。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 保存程序的运行结果，并结合程序进行分析。三、 实验内容编写一个程序，对所给的数据(程序中给出或通过键盘初始化均可)进行排序，要求尽可能多的选择不同的排序算法，并显示排序前和排序后的结果。#include #include #define TRUE 1#define FALSE 0#define N 10int a10 = 9,27,45,87,17,23,25,92,8,75 ;typedef structint key;int info;RecordNode;typedef struct Sortint n; /记录个数RecordNode *record;SortObject;/*直接插入排序*/void insertSort(SortObject *pvector) int i, j;RecordNode temp;for (i = 1; i n; i+) temp = pvector-recordi; j = i - 1;while (temp.key recordj.key) & (j = 0)pvector-recordj + 1 = pvector-recordj; j-; if (j != (i - 1) pvector-recordj + 1 = temp;/*二分法插入排序*/void binSort(SortObject * pvector) int i, j, left, mid, right;RecordNode temp;for (i = 1; i n; i+)temp = pvector-recordi; left = 0; right = i - 1; while (left = right)mid = (left + right) / 2; if (temp.keyrecordmid.key) right = mid - 1; else left = mid + 1; for (j = i - 1; j = left; j-)pvector-recordj + 1 = pvector-recordj;if (left != i) pvector-recordleft = temp;struct Node; typedef struct Node ListNode;struct Nodeint key; ListNode *next; ;typedef ListNode * LinkList;void listSort(LinkList * plist)ListNode *now, *pre, *p, *q, *head;head = *plist;pre = head-next;if (pre = NULL) return;now = pre-next;if (now = NULL) return; while (now != NULL)q = head; p = head-next;while (p != now & p-key key) q = p; p = p-next; if (p = now) pre = pre-next; now = pre-next; continue; pre-next = now-next; q-next = now; now-next = p; now = pre-next;/*Shell排序*/void shellSort(SortObject * pvector, int d) /* 按递增序进行Shell排序 */int i, j, increment;RecordNode temp;for (increment = d; increment 0; increment /= 2) for (i = increment; in; i+)temp = pvector-recordi; j = i - increment;while (j = 0 & temp.keyrecordj.key) pvector-recordj + increment = pvector-recordj; j -= increment;pvector-recordj + increment = temp; /*直接选择排序*/void selectSort(SortObject * pvector) int i, j, k;RecordNode temp;for (i = 0; i n - 1; i+) /* 做n-1趟选择排序 */k = i;for (j = i + 1; jn; j+) /* 在无序区内找出排序码最小的记录Rk*/if (pvector-recordj.keyrecordk.key) k = j;if (k != i) /* 记录Rk与Ri互换 */temp = pvector-recordi;pvector-recordi = pvector-recordk;pvector-recordk = temp;/*起泡排序*/void bubbleSort(SortObject * pvector)int i, j, noswap;RecordNode temp;for (i = 0; in - 1; i+) noswap = TRUE; for (j = 0; jn - i - 1; j+)if (pvector-recordj + 1.keyrecordj.key) temp = pvector-recordj; pvector-recordj = pvector-recordj + 1;pvector-recordj + 1 = temp;noswap = FALSE; if (noswap) break; /*快速排序*/void quickSort(SortObject * pvector, int l, int r)int i, j;RecordNode temp;if (l = r) return; i = l; j = r; temp = pvector-recordi;while (i != j) while (pvector-recordj.key = temp.key) & (ji) j-;if (irecordi+ = pvector-recordj;while (pvector-recordi.key i) i+;if (irecordj- = pvector-recordi;pvector-recordi = temp; quickSort(pvector, l, i - 1); quickSort(pvector, i + 1, r); /*归并*/void merge(RecordNode* r, RecordNode *r1, int low, int m, int high)int i, j, k;i = low; j = m + 1; k = low;while (i = m) & (j = high)if (ri.key = rj.key) r1k+ = ri+;else r1k+ = rj+;while (i = m) r1k+ = ri+; while (j = high) r1k+ = rj+;void mergePass(RecordNode *r, RecordNode *r1, int n, int length)int j, i = 0;while (i + 2 * length - 1n)merge(r, r1, i, i + length - 1, i + 2 * length - 1); i += 2 * length;if (i + length - 1n - 1) merge(r, r1, i, i + length - 1, n - 1);elsefor (j = i; jn; j+) r1j = rj; /*二路归并排序*/void mergeSort(SortObject *pvector)RecordNode recordN;int length = 1;while (lengthn)mergePass(pvector-record, record, pvector-n, length); /* 一趟归并，结果放在r1中*/length *= 2;mergePass(record, pvector-record, pvector-n, length); /* 一趟归并，结果放在r中 */length *= 2;void s1()/* 直接插入排序 */int i;SortObject *p1 = (SortObject *)malloc(sizeof(SortObject);p1-n = 10;p1-record = (RecordNode *)malloc(sizeof(RecordNode)*p1-n);for (i = 0; in; i+)p1-recordi.key = ai;insertSort(p1);printf(直接插入排序后 : );for (i = 0; in; i+)printf(%d , p1-recordi.key);printf(n);void s2()/* 二分法插入排序 */int i;SortObject *p2 = (SortObject *)malloc(sizeof(SortObject);p2-n = 10;p2-record = (RecordNode *)malloc(sizeof(RecordNode)*p2-n);for (i = 0; in; i+)p2-recordi.key = ai;binSort(p2);printf(二分法插入排序后: );for (i = 0; in; i+)printf(%d , p2-recordi.key);printf(n);void s3()/* Shell排序 */int i;SortObject *p3 = (SortObject *)malloc(sizeof(SortObject);p3-n = 10;p3-record = (RecordNode *)malloc(sizeof(RecordNode)*p3-n);for (i = 0; in; i+)p3-recordi.key = ai;shellSort(p3, 4);printf(Shell排 序 后 : );for (i = 0; in; i+)printf(%d , p3-recordi.key);printf(n);void s4()/* 直接选择排序 */int i;SortObject *p4 = (SortObject *)malloc(sizeof(SortObject);p4-n = 10;p4-record = (RecordNode *)malloc(sizeof(RecordNode)*p4-n);for (i = 0; in; i+)p4-recordi.key = ai;selectSort(p4);printf(直接选择排序后 : );for (i = 0; in; i+)printf(%d , p4-recordi.key);printf(n);void s5()/* 起泡排序 */int i;SortObject *p5 = (SortObject *)malloc(sizeof(SortObject);p5-n = 10;p5-record = (RecordNode *)malloc(sizeof(RecordNode)*p5-n);for (i = 0; in; i+)p5-recordi.key = ai;bubbleSort(p5);printf(起 泡 排 序 后 : );for (i = 0; in; i+)printf(%d , p5-recordi.key);printf(n);void s6()/* 快速排序 */int i;SortObject *p6 = (SortObject *)malloc(sizeof(SortObject);p6-n = 10;p6-record = (RecordNode *)malloc(sizeof(RecordNode)*p6-n);for (i = 0; in; i+)p6-recordi.key = ai;quickSort(p6, 0, p6-n - 1);printf(快 速 排 序 后 : );for (i = 0; in; i+)printf(%d , p6-recordi.key);printf(n);void s7()/* 二路归并排序 */int i;SortObject *p7 = (SortObject *)malloc(sizeof(SortObject);p7-n = 10;p7-record = (RecordNode *)malloc(sizeof(RecordNode)*p7-n);for (i = 0; in; i+)p7-recordi.key = ai;mergeSort(p7);printf(二路归并排序后 : );for (i = 0; in; i+)printf(%d , p7-r