一.对一个数组用堆排的方法排序
1 #include <iostream> 2 using namespace std; 3 const int maxn = 4e3 + 7; 4 int str[maxn]; 5 void HeapAdjust(int a[], int l, int r) 6 { 7 int rc, j; 8 rc = a[l]; 9 for(j = 2 * l; j <= r; j *= 2) 10 { 11 if((j < r) && (a[j] < a[j + 1])) ++j; 12 if(!(rc <= a[j])) break; 13 a[l] = a[j]; l = j; 14 } 15 a[l] = rc; 16 } 17 18 void HeapSort(int a[], int n) 19 { 20 int i, t; 21 for(i = n/2; i > 0; --i) 22 HeapAdjust(a,i,n); 23 for(i = n; i > 1; --i) 24 { 25 t = a[1]; a[1] = a[i]; a[i] = t; 26 HeapAdjust(a, 1, i-1); 27 } 28 } 29 30 int main() 31 { 32 int n; 33 cin>>n; 34 for(int i = 1; i <= n; i++) cin>>str[i]; 35 HeapSort(str,n); 36 for(int i = 1; i <= n; i++) cout<<str[i]<<" "; 37 return 0; 38 }
二.链表实现插入排序
1 #define int KeyType //定义 KeyType 为 int 型 2 typedef struct node 3 { 4 KeyType key; //关键字域 5 OtherInfoType info; //其他信息域 6 struct node *next; //链表中的指针域 7 }RecNode; //记录节点类型 8 typedef RecNode *LinkList; //单链表用 LinkList表示 9 void InsertSort(LinkList head) //链式存储结构的直接插入排序算法，head 是带头节点的单链表 10 { 11 RecNode *p, *q, *s; 12 if((head -> next) && (head -> next -> next)) //当表中含有的节点数大于 1 13 { 14 p = head -> next -> next; // p 指向第二个节点 15 head -> next = NULL; 16 q = head; //指向插入位置的前趋节点 17 while((p) && (q -> next) && (p -> key < q -> next -> key)) 18 q = q -> next; 19 if(p) 20 { 21 s = p; p = p -> next; //将要插入的节点摘下 22 s -> next = q - > next; //插入合适位置: q 节点后 23 q -> next = s; 24 } 25 } 26 }
三.设计一个算法，在尽可能少的时间里内重排数组，将所有关键字负值记录放在所有关键字非负值记录之前。O( n ) 的时间复杂度
1 void Resort(SeqList R) //重排数组,使负值关键字在前 2 { 3 int i = 1, j = n; //数组存放在 R[ 1...n ] 4 while(i < j) // i < j 表示尚未扫描完毕 5 { 6 while(i < j && R[i].key < 0) //遇到负数继续向后扫描 7 i++; 8 R[0] = R[i]; // R[0] 辅助空间 9 while(i < j && R[i].key > 0) //遇到正数继续向左扫描 10 j--; 11 R[i++] = R[j]; //交换两个元素并交换指针 12 R[j--] = R[0]; 13 } 14 }
四.写双冒泡排序算法。( 排序过程中交替改变扫描方向 )
1 void BubbleSort(SeqList R) 2 { 3 int i,j,k; 4 boolean exchange; //交换标记 5 i= n; j = 1; 6 exchange = true; 7 while((i > j) && (exchange)) 8 { 9 k = i - 1; exchange = false; 10 while(k >= j) //由下往上扫描 11 { 12 if(r[k] > r[k+1]) 13 { 14 r[0] = r[k];r[k] = r[k+1]; r[k+1] = r[k]; //交换 15 exchange = true; 16 } //endif 17 k--; 18 } 19 if(exchange) 20 { 21 exchange = false; 22 j++; k = j + 1; 23 while(k <= i) //由上往下扫描 24 { 25 if(r[k] < r[k-1]) 26 { 27 r[0] = r[k]; r[k] = r[k-1];r[k-1] = r[k]; //交换 28 exchange = true; 29 } 30 k++; 31 } 32 i--; 33 } 34 } 35 }
五.将两个递增的有序的单链表合并成一个递增有序的单链表。( 算法应利用原有的链表节点空间 )
1 #define KeyType int //定义 KeyType 为 int 型 2 #define OtherInfoType string 3 typedef struct node 4 { 5 KeyType key; //关键字域 6 OtherInfoType info; //其他信息域 7 struct node *next; //链表中的指针域 8 }RecNode; //记录节点类型 9 typedef RecNode *LinkList; //单链表用 LinkList表示 10 void Mergesort(LinkList la, LinkList lb, LinkList lc) //链式存储结构的直接插入排序算法，head 是带头节点的单链表 11 { 12 RecNode *p, *q, *s, *r; 13 lc = la; 14 p = la; 15 q = lb -> next; 16 while((p -> next) && (q)) 17 if(p -> next -> key <= q -> key) 18 p = p -> next; 19 else 20 { 21 s = q; q = q -> next; 22 s -> next = p -> next; p -> next = s; 23 p = s; 24 } 25 if(!p->next) p ->next = q; 26 free(lb); 27 }
六.设数组A[0...n-1]中的 n 个互不相同的整数，且每个元素的值均在 0 到 n - 1 之间，写一个时间复杂度为O( n )的算法对数组 A 中的
元素进行排序，结果可以输出到另一个数组 B[0...n-1]中。
1 void Sort(int a[],int b[]) 2 { 3 int i; 4 for(i = 0; i < n; i++) 5 b[a[i]] = a[i]; 6 }