博主将代码先撸为敬,具体解释均在代码里面。
一 以表格的形式整体出各经典算法的定义(多个版本)、理解、示例、比较、总结等
--------------------为反馈划下华丽的分割线--------------------
...
------------------------------------------------------------------
二 代码实践
(1)运行结果:
优化后的冒泡排序(升序)
优化后的冒泡排序(降序)
简单选择排序(升序)
直接插入排序(升序)
(2)代码:
#include <iostream>#include <string>#include <vector>#include <array>using namespace std;//用来输出数组void coutFun(int r[],int n){for (int k = 0; k < n; k++)cout << r[k] << endl;cout << " " << endl;}//冒泡排序_优化(1)_升序版void bubbleSort(int r[],int n)//int r[] 的形参 接收 int*的实参???怎么一回事啊???C++直接传递引用 起别名{int bubbleSort_flag = -1;for (int i = 0; i < n - 1; i++){bubbleSort_flag = 0;//标记排序是否已经提前完成,即数列中的元素是否已经提前有序for (int j = 0; j < n - i - 1; j++)//j < n - i; 会导致r[j + 1]数组下标越界 可以 7 2 8 0 为例 //改为 n-i-1 除去已经排好的大数,找到最大的数进行比较//for (int j = i + 1; j <= n - 1; j++)//这样写少了小的数进行上升 如 7 2 8 0 上面的j < n - i - 1;这种写法表示相对最大的数已经陈到底部,不用去考虑,只需要考虑小的数如何上升就ok了{if (r[j]>r[j + 1]){swap(r[j], r[j + 1]);bubbleSort_flag = 1;}}//假如有N-1趟,假设在第N-5趟排序就已经完成,数列有序,那么bubbleSort_flag = 0 不再进行(N-1)-(N-5) = 4趟的排序if (bubbleSort_flag != 1)break;}//输出数组coutFun(&r[0],n);}//冒泡排序_优化(2)_Good_倒序版void bubbleSort2(int r[], int n){int bubbleSort_flag2 = -1;//从r[0 1 ... j-1]中找到相对最小的数放到最后 for (int i = n - 1; i > 0; i--){bubbleSort_flag2 = 0;for (int j = 0; j < i; j++){if (r[j] < r[j + 1]){swap(r[j], r[j + 1]);int bubbleSort_flag2 = 1;}}if (bubbleSort_flag2 == 1)break;}//输出数组coutFun(&r[0], n);}//简单选择排序void selectSort(int r[], int n){int min = 0, selectSort_flag = -1;for (int i = 0; i < n - 1; i++){//selectSort_flag = 0;min = i;//关键词:下标 找到最小的那个数的下标 交换到第一个位置上去 以此类推for (int j = i + 1; j <= n - 1; j++){if (r[j] < r[min]){min = j;//selectSort_flag = 1;//这样写其实毫无意义 因为r[i+1 ... n-1]必须与r[min]比较完 选择排序是位置有序 将相对最小的数依次插入}}if (i != min)swap(r[i], r[min]);}//输出数组coutFun(&r[0], n);}//直接插入排序//理解上课可等价于线性表的插入void insertSort(int r[], int n){int i, j, temp = 0;for (i = 1; i <= n - 1; i++){temp = r[i];if (r[i - 1] > r[i])//找到 “要插谁”{for (j = i - 1; r[j] > temp; j--)//找到 “插在哪”{r[j + 1] = r[j];}r[j + 1] = temp;}}//输出数组coutFun(&r[0], n);}int main(){int flag = 0;//退出循环flag//输入界面//vector类创建动态数组 堆区int n, cmd, *pt_vector;while (1){cout << "0:退出1:优化的冒泡排序(1)_升序版" << endl;cout << "2:优化的冒泡排序(2)_Good_倒序版3:简单选择排序" << endl;cout << "4:直接插入排序" << endl;cout << "请输入命令(即数字0~4):";cin >> cmd;if (cmd == 0)break;cout << "请输入要排序的数字的个数:";cin >> n;vector<int>r(n);cout << "依次输入需要排序的那" << n << "个数:" << endl;for (int i = 0; i < n; i++)cin >> r[i];cout << endl;pt_vector = &r[0];switch (cmd){case 1:bubbleSort(pt_vector, n); break;//冒泡排序_优化(1)case 2:bubbleSort2(pt_vector, n); break;//冒泡排序_优化(2)_Goodcase 3:selectSort(pt_vector, n); break;//简单选择排序case 4:insertSort(pt_vector, n); break;//直接插入排序}}system("pause");return 0;}//【01】冒泡排序_优化 /*一维数组大数下沉,小(的)数上浮,故称冒泡。外循环 N个元素N-1趟比较 内循环 相邻两数两两比较,大则交换。*///【02】简单选择排序/*选择排序是位置有序 将相对最小的数依次插入各位置*///【03】直接插入法/*两个关键,要插谁?插哪里?理解上课可等价于线性表的插入*/