PS：仅课程实验记录
题目：创建一个顺序表，存放在数组 A[N]中，元素的类型为整型，设计算法调整 A，使其左边的所有元素小于 0，右边的所有元素大于 0（要求算法的时间复杂度和空 间复杂度均为 O(n)）。
//头文件部分 SeqList.h #pragma once #include <iostream> using namespace std; const int MaxSize = 50; class SeqList { public: SeqList(); //无参构造函数 SeqList(int a[], int len); //有参构造函数 ~SeqList() {} //析构函数 void PrintList(); //打印操作 void SwapItem(); // 功能实现 private: int data[MaxSize]; int length; }; //cpp文件部分 SeqList.cpp #include"SeqList.h" SeqList::SeqList() //无参构造函数 { length = 0; } SeqList::SeqList(int a[], int len) //有参构造函数 { if (len > MaxSize) throw std::exception("参数非法"); else { for (int i = 0; i < len; i++) { data[i] = a[i]; } length = len; } } void SeqList::PrintList() //打印操作 { cout << "顺序表元素为： "; for (int i = 0; i < length; i++) { cout << data[i] << " "; } cout << '\n'; cout << '\n'; } // 功能实现 void SeqList::SwapItem() { int i = 0 , j = 0; //将所有小于0的元素排在最左边 for (j = 0; j < length; j++) { if (data[j] < 0) { int temp = data[i]; data[i] = data[j]; data[j] = temp; i++; } } //记录左侧第一个不是小于0的元素下标 int k = 0; for (k = 0; data[k] < 0; k++); //对右侧0元素进行处理 for (int f = k; f < length; f++) { if (data[f] == 0) { int temp = data[k]; data[k] = data[f]; data[f] = temp; k++; } } } //测试函数 int main() { int T[10] = { -1,-2,-4,-3,5,-2,-3,3,-3,8 }; SeqList Seq1(T, 10); cout << "\n排列前："; Seq1.PrintList(); Seq1.SwapItem(); //执行操作 cout << "排列后："; Seq.PrintList(); cout << "------------------------------------------------------------------" << endl; int S[10] = { -1,4,2,6,0,5,-2,-4,0,-1 }; SeqList Seq2(T, 10); cout << "排列前："; Seq2.PrintList(); Seq2.SwapItem(); //执行操作 cout << "排列后："; Seq2.PrintList(); cout << "------------------------------------------------------------------" << endl; return 0; }