浙江财经学院数据结构排序实验(2)

high--; CompareNum3++; } CompareNum3++;

data[low] = data[high]; while (low < high && pivot >= data[low]){ low++; CompareNum3++; } CompareNum3++;

data[high] = data[low]; MoveNum3+= 2; }

data[low] = pivot;

MoveNum3 += 2;

return low; }

template

void QuickSort(ElemType data[], int begin, int end) {

if (begin >= end) return;

int pivot = Partition(data , begin , end); QuickSort(data , begin , pivot - 1);

QuickSort(data , pivot + 1, end); }

template

void QuickSort(ElemType data[], int n) {

if (n < 2) return;

CompareNum3 = MoveNum3 = 0; QuickSort(data, 0, n-1); }

6

int CompareNum4;

int MoveNum4;// 简单选择排序 template

void SelectionSort(ElemType data[], int n) {

CompareNum4=0; MoveNum4=0; int i, j, min;

for (i = 0; i < n; i++){ min = i;

for (j = i + 1; j < n; j++){ if ( data[j] < data[min]) min = j; CompareNum4++; }

Swap(data[i],data[min]); MoveNum4 += 3; } }

#include #include \#include \#include \#include %using namespace std;

void main() { // int

CompareNum1,MoveNum1,CompareNum2,MoveNum2,CompareNum3,MoveNum3,CompareNum4,MoveNum4;

int a[10]={1,9,3,7,25,48,21,5,8,10}; int n=10,i;

cout<<\ for(i=0;i

7

InsertSort(a,n); BubbleSort(a,n); QuickSort(a,n); SelectionSort(a,n);

cout<<\ for(i=0;i cout<<\直接插入排序比较次数=\移动次数=\

cout<<\冒泡排序比较次数=\移动次数=\ cout<<\快速排序比较次数=\移动次数=\ cout<<\简单选择排序比较次数=\移动次数=\}

时间复杂度比较程序 //InsretSort.h //直接插入排序

template

void InsertSort(ElemType data[],int n) {

ElemType tmp; int i,j;

for(i=1;idata[i-1]) { continue; } tmp=data[i]; //保存待插入的元素 data[i]=data[i-1]; for(j=i-1;j>0&&data[j-1]>tmp;j--) {

8

data[j]=data[j-1]; //元素后移 } data[j]=tmp; } }

//BubbleSort.h //冒泡排序

template

void BubbleSort(ElemType data[],int n) {

int lastSwapIndex=n-1; int i,j;

for( i=lastSwapIndex;i>0;i=lastSwapIndex ) { lastSwapIndex=0; for(j=0;jdata[j+1]) { Swap(data[j],data[j+1]); lastSwapIndex=j; } } } }

//交换函数

template void Swap(T &a,T &b) {

T c=a; a=b; b=c; }

9

// Partition.h //快速排序

template

int Partition(ElemType data[] , int low , int high) {

ElemType pivot = data[low]; while (low < high){

while (low < high && data[high] >= pivot) high--;

data[low] = data[high];

while (low < high && pivot >= data[low]) low++;

data[high] = data[low]; }

data[low] = pivot; return low; }

template

void QuickSort(ElemType data[], int begin, int end) {

if (begin >= end) return;

int pivot = Partition(data , begin , end); QuickSort(data , begin , pivot - 1);

QuickSort(data , pivot + 1, end); }

template

void QuickSort(ElemType data[], int n) {

if (n < 2) return;

QuickSort(data, 0, n-1); }

// SelectionSort.h // 简单选择排序

10