排序综合数据结构课程设计论文

#include #include #include #include #include #include #define MAXSIZE 1000 #define TRUE 1 #define FALSE 0 typedef int BOOL; typedef struct{ int key; } RedType; class LinkList {

public:

RedType r[MAXSIZE+1]; int Length;

int CmpNum, ChgNum; LinkList();

bool LT(int i, int j); void Display(); void Insert( int dk); void ShellSort();

int Partition( int low, int high); void QSort( int low, int high); void QuickSort();

void HeapAdjust( int s, int m); void HeapSort(); void BubbleSort();

int SelectMinKey( int k); void SelSort(); void SelectSort(); void AllAbove(); };

LinkList::LinkList(){ int i;

for (i = 0; i <= MAXSIZE; i++) r[i].key = rand()00; Length=MAXSIZE+1; CmpNum=0; ChgNum=0;

- 10 -

10

}

bool LinkList::LT(int i, int j){ (CmpNum)++; if (i < j)

return TRUE; else

return FALSE; }

void LinkList::Display() { int j; for(int i=0;i<=MAXSIZE;i++) { cout<

4.3.2六种排序算法代码

//插入排序

void LinkList::Insert(int dk){ int i, j;

RedType Temp;

for (i = dk; i < Length; i++) {

if (LT(r[i].key, r[i - dk].key)) {

memcpy(&Temp, &r[i], sizeof(RedType));

for (j = i - dk; j >= 0 && LT(Temp.key, r[j].key); j -= dk) {

(ChgNum)++;

memcpy(&r[j + dk], &r[j], sizeof(RedType)); }

memcpy(&r[j + dk], &Temp, sizeof(RedType)); } } }

- 11 -

11

//希尔排序

void LinkList::ShellSort() {

int t=Length+1; do{ t=t/3+1; Insert( t); }

while(t>1); }

//快速排序

int LinkList::Partition(int low, int high){ RedType Temp; int PivotKey;

memcpy(&Temp, &r[low], sizeof(RedType)); PivotKey = r[low].key; while (low < high){

while (low < high &&r[high].key >= PivotKey){ high--;

(CmpNum)++; }

(ChgNum)++;

memcpy(&r[low], &r[high], sizeof(RedType)); while (low < high && r[low].key <= PivotKey){ low++;

(CmpNum)++; }

(ChgNum)++;

memcpy(&r[high], &r[low], sizeof(RedType)); }

memcpy(&r[low], &Temp, sizeof(RedType)); return low; }

void LinkList::QSort( int low, int high){ int PivotLoc = 0; if (low < high){

PivotLoc = Partition( low, high); QSort(low, PivotLoc - 1); QSort( PivotLoc + 1, high); } }

- 12 -

12

void LinkList::QuickSort(){ QSort(0, Length - 1); }

//堆排序

void LinkList::HeapAdjust(int s, int m){ RedType Temp; int j = 0; s++;

memcpy(&Temp, &r[s - 1], sizeof(RedType)); for (j = 2 * s; j <= m; j *= 2){

if (j < m && LT(r[j - 1].key, r[j].key)) ++j;

if (!LT(Temp.key, r[j - 1].key)) break;

(ChgNum)++;

memcpy(&r[s - 1], &r[j - 1], sizeof(RedType)); s = j; }

memcpy(&r[s - 1], &Temp, sizeof(RedType)); }

void LinkList::HeapSort(){ int i = 0;

RedType Temp;

for (i = Length / 2-1; i >= 0; i--) HeapAdjust(i, Length); for (i = Length; i > 1; i--){

memcpy(&Temp, &r[0], sizeof(RedType)); (ChgNum)++;

memcpy(&r[0], &r[i - 1], sizeof(RedType)); memcpy(&r[i - 1], &Temp, sizeof(RedType)); HeapAdjust( 0, i - 1); } }

//冒泡排序

void LinkList::BubbleSort(){ int i, j;

RedType temp;

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

for (j = 1; j <= MAXSIZE - i; j++){ if (!LT(r[j].key, r[j + 1].key)){

- 13 -

13

(ChgNum)++;

memcpy(&temp, &r[j], sizeof(RedType)); memcpy(&r[j], &r[j + 1], sizeof(RedType)); memcpy(&r[j + 1], &temp, sizeof(RedType)); } } } }

//选择排序

int LinkList::SelectMinKey( int i) {

int Min = i;

for (int k=i; k < Length; k++) {

if (!LT(r[Min].key, r[k].key)) Min = k; }

return Min; }

void LinkList::SelSort(){ int i, j;

RedType temp;

for (i = 0; i < Length; i++){ j = SelectMinKey( i); if (i != j){

(ChgNum)++;

memcpy(&temp, &r[i], sizeof(RedType)); memcpy(&r[i], &r[j], sizeof(RedType)); memcpy(&r[j], &temp, sizeof(RedType)); } } }

4.3.3 排序算法的选择

void LinkList::SelectSort(){ cout<<\插入排序\ cout<<\希尔排序\ cout<<\快速排序\ cout<<\堆排序\ cout<<\冒泡排序\

- 14 -

14