下面直接给出这段代码
#include<stdio.h> #include<assert.h> #include<iostream> #include<string.h> using namespace std; #define MAX_SIZE 20 /* *代码中多次出现assert()函数 于是查了一下assert函数的用法 *assert的作用是先计算表达式 expression ，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。 */ typedef struct { int a[MAX_SIZE];//用于储存排序数组 int size;//用于记录顺序表的长度 }seqlist; //顺序表初始化 void init_list(seqlist *l); //尾插 void last_insert(seqlist *l, int n); //读取数组中第n个元素的值 void read(seqlist *l, int n); //把第i个数改为m void change(seqlist *l, int i, int m); //打印顺序表 void print(seqlist *l); //找到数为n在数组中的下标位置 void find(seqlist *l, int n); //在第i个位置上插入数字n int insert(seqlist *l, int i, int n); //交换数组中下标为i和j的值 void swap(seqlist *l,int i,int j); int Partition(seqlist*l,int low,int high); void QSort(seqlist *l,int low,int high); void QuickSort(seqlist*l); int NewPartition(seqlist *l,int low,int high); void QSort1(seqlist *l,int low,int high); void QuickSort1(seqlist *l); #include"SeqList.h" #include<iostream> using namespace std; #define MAX_SIZE 20 //顺序表初始化 void init_list(seqlist *l) { assert(l);//判断l是否为空 memset(l->a, 0, sizeof(l->a));//初始化数组 l->size = 0; } //尾插 void last_insert(seqlist *l, int n) { assert(l); if (l->size < MAX_SIZE) { l->size++;//总数加1 l->a[l->size] = n;//现在下标变成从1开始 然后尾部插入法就是将n赋值给a[l->size] } else { cout << "空间不足" << " "; } } //读取数组中第n个元素的值 void read(seqlist *l, int n) { assert(l); if (n <= l->size) std::cout << n << ":" << l->a[n ] << " "; } //把第i个数改为m void change(seqlist *l, int i, int m) { assert(l); l->a[i] = m; } //打印顺序表 void print(seqlist *l) { assert(l); for (int i = 1; i <= l->size; i++) printf("%d ", l->a[i]); } //找到数为n在数组中的下标位置 void find(seqlist *l, int n) { assert(l); for (int i = 1; i <= l->size; i++) { if (l->a[i] == n) printf("数组下标为%d的等于%d ", i,n); } } //在第i个位置上插入数字n int insert(seqlist *l, int i, int n) { if (i<1 || i>l->size) { cout << "插入位置不对" << " "; return -1; } if (l->size == MAX_SIZE) { cout << "存储空间不足" << " "; return -1; } l->size++;//总个数再加一 for (int j = l->size; j > i; j--) { //数组整体后移 l->a[j-1] = l->a[j]; } //把下标位置为i-1的位置空出来 再赋值 l->a[i] = n; return 0; //return 1和return 0? } //交换数组中下标为i和j的值 void swap(seqlist *l,int i,int j){ int temp=l->a[i]; l->a[i]=l->a[j]; l->a[j]=temp; } //交换顺序表l中子表的记录,使得枢轴记录到位,并返回其所在的位置 int Partition(seqlist *l,int low,int high) { int pivotkey; pivotkey=l->a[low];//用子表的第一个记录作为枢轴记录 while(low<high){//从表的两端交替向中间扫描 while(low<high&&l->a[high]>=pivotkey)//如果最后一个元素大于枢轴记录 ,那么将将下标往前移动一位 high--; swap(l,low,high);//将小值与最后一个位置互换 while(low<high&&l->a[low]<=pivotkey)//如果小坐标的值小于枢轴的值 那么下标前移 low++; swap(l,low,high); } return low; } void QSort(seqlist*l,int low,int high) { int pivot; if(low<high) { pivot=Partition(l,low,high); QSort(l,low,pivot-1); QSort(l,pivot+1,high); } } void QuickSort(seqlist*l) { QSort(l,1,l->size); } int NewPartition(seqlist *l, int low,int high){ int pivotkey; int m=low+(high-low)/2;//计算数组中间元素的下标 if(l->a[low]>l->a[high]) swap(l,low,high); if(l->a[m]>l->a[high]) swap(l,high,m); if(l->a[m]>l->a[low]) swap(l,m,low); pivotkey=l->a[low]; l->a[0]=pivotkey; //至此就可以得到l.a[low]就是整个序列中左右三个位置的关键字 while(low<high) { while(low<high&&l->a[high]>=pivotkey) high--; l->a[low]=l->a[high];//采用替换而不是交换的方式进行操作 while(low<high&&l->a[low]<=pivotkey) low++; l->a[high]=l->a[low]; } l->a[low]=l->a[0]; return low; } void QSort1(seqlist*l,int low,int high) { int pivot; if(low<high) { pivot=NewPartition(l,low,high); QSort1(l,low,pivot-1); QSort1(l,pivot+1,high); } } void QuickSort1(seqlist*l) { QSort1(l,1,l->size); } #include"SeqList.h" int main() { int n; seqlist l; init_list(&l); last_insert(&l, 50); last_insert(&l, 10); last_insert(&l, 90); last_insert(&l, 30); last_insert(&l, 70); last_insert(&l, 40); last_insert(&l, 80); last_insert(&l, 60); last_insert(&l, 20); print(&l); printf("\n"); QuickSort1(&l); print(&l); return 0; }