2021-3-17C++笔记：奇葩排序之猴子排序、珠排序、面条排序
奇葩排序
猴子排序（佛系排序）
随机打乱数组，检查是否排好序，若是，则输出，否则再次打乱，再检查…最佳情况O(n)，平均O(n*n!)，最坏可执行直到世界的尽头。
无限猴子定理 ：一只猴子随机敲打打字机键盘，如果时间足够长，总是能打出特定的文本，比如莎士比亚全集。
如果数据太多，排序时长完全看运气。
以下是准备好的源码，可以直接看着用，阅读顺序：
monkeySort_main()–>monkeySort()–>monkeyShow()。
void monkeyShow(int arr[])//输出排序结果
{
for (int i = 0; i < 5; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void monkeySort(int arr[])//猴子排序
{
srand((unsigned)time(0));
int flag = 1;
while (flag)
{
random_shuffle(arr, arr + 5);
for (int i = 0; i < 5; i++)
{
if (arr[i] > arr[i + 1])
{
flag = 1;
goto loop;//跳出循环
}
}
flag = 0;
loop:
;//这个空语句很重要
}
//输出最终结果
monkeyShow(arr);
}
void monkeySort_main()
{
int arr[5] = { 2,7,15,8,6 };
cout << "原始数据：" << endl;
monkeyShow(arr);//原始数据
cout << "猴子排序(升序)：" << endl;
monkeySort(arr);//猴子排序实现
}
·
·
珠排序
题目描述：
以下是源码部分，函数可以直接复制使用。
建议阅读顺序：
marbleSort_main()->marbleSort()->marbleShow()->swap()
void marbleShow(int computer[5][5])//输出算盘
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (computer[i][j] == 1)//优化UI
{
cout << "* ";
continue;
}
cout << computer[i][j] << " ";
}
cout << endl;
}
}
void swap(int& a, int& b)//交换数值
{
a = a + b;
b = a - b;
a = a - b;
}
void marbleSort(int arr[])//珠排序实现
{
int computer[5][5] = { 0 };
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < arr[i]; j++)
{
computer[i][j] = 1;
}
}
cout << "排序前：" << endl;
marbleShow(computer);//输出算盘
for (int j = 0; j < 5; j++)//列
{
for (int i = 4; i >= 0; i--)//排序列
{
for (int k = i - 1; k >= 0; k--)
{
if (computer[i][j] < computer[k][j])
{
swap(computer[i][j], computer[k][j]);
}
}
}
}
cout << "排序后：" << endl;
marbleShow(computer);//输出算盘
for (int i = 0; i < 5; i++)//统计数据
{
int cnt = 0;
for (int j = 0; j < 5; j++)
{
if (computer[i][j] == 1)
{
cnt++;
}
}
arr[i] = cnt;
}
}
void marbleSort_main()
{
int arr[] = { 3,2,4,5,1 };
marbleSort(arr);//珠排序实现
cout << "把二维数组转换为一维数组：" << endl;
for (int i = 0; i < 5; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
·
·
面条排序
意大利面条排序(Spaghetti Sort)的思路是，将输入分别对应到不同长度的面条上，每根面条的长度即为对应的数字的大小。比如，对于[1, 4, 2, 8, 9]这个输入，则分别做出长度为1cm、4cm、2cm、8cm、9cm的面条。然后，将这些面条的一头对其，用手抓住，另一头向下。然后慢慢地将手向下垂直下降，第一个触碰到桌面的面条对应的数字则为最大的数字，第二个触碰到的就是第二大的，依次类推。
Spaghetti排序简直不是一个软件可行的想法 - 它是一种按物理长度排序的“物理”理论方法。基本上它说：“将一堆意大利面条棒推到一个平坦的表面上，使最长的那些比最短的更突出 - 从而按长度”排序“它们。
void nuddleSort(int arr[])//面条排序实现
{
int arrSave[5] = { 0 };
int hand = 0;//手
int min = 0;//下限
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (arr[j] > arr[hand])
{
hand = j;//手碰到最长的一根面条
}
}
arrSave[i] = arr[hand];//保存最长的面条
arr[hand] = arr[min];//把最长的面条删除（变成最短的）
}
cout << "面条排序（降序）：" << endl;
for (int i = 0; i < 5; i++)
{
cout << arrSave[i] << " ";
}
cout << endl;
}
void nuddleSort_main()
{
int arr[5] = { 2,7,15,8,6 };
readData(arr);
nuddleSort(arr);//面条排序实现
}
·
·
完整源代码(实验作业结果，未修改)
注意，直接copy代码运行时需要创建test.txt文件用于保存初始数据。（由于是实验作业，for循环是写死的，所以初始数据只能按照我的来。否则需要去修改具体的代码。
原始数据在下：
5
2 7 15 8 6
代码：
#include <iostream>
using namespace std;
#include <fstream>//读取文件
#include <string>
#include <algorithm>//ramdon_shuffle
#include <ctime>
#include <cstdlib>
//------------------------------------------------//猴子排序
void readData(int arr[])//以文字流形式读取文件数据
{
ifstream ifs("test3.txt", ios::in);
if (!ifs.is_open())
{
cout << "文件打开失败！" << endl;
}
string data = " ";
for (int i = 0; ifs >> data; i++)
{
arr[i] = stoi(data);//将string转换为int
}
ifs.close();
}
void monkeyShow(int arr[])//输出排序结果
{
for (int i = 1; i <= 5; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void monkeySort(int arr[])//猴子排序
{
srand((unsigned)time(0));
int flag = 1;
while (flag)
{
random_shuffle(arr + 1, arr + 6);
for (int i = 1; i < 5; i++)
{
if (arr[i] > arr[i + 1])
{
flag = 1;
goto loop;//跳出循环
}
}
flag = 0;
loop:
;//这个空语句很重要
}
//输出最终结果
monkeyShow(arr);
}
//--------------------------------------------//珠排序
void marbleShow(int computer[5][5])//输出算盘
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (computer[i][j] == 1)//优化UI
{
cout << "* ";
continue;
}
cout << computer[i][j] << " ";
}
cout << endl;
}
}
void swap(int& a, int& b)//交换数值
{
a = a + b;
b = a - b;
a = a - b;
}
void marbleSort(int arr[])//珠排序实现
{
int computer[5][5] = { 0 };
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < arr[i]; j++)
{
computer[i][j] = 1;
}
}
cout << "排序前：" << endl;
marbleShow(computer);//输出算盘
for (int j = 0; j < 5; j++)//列
{
for (int i = 4; i >= 0; i--)//排序列
{
for (int k = i - 1; k >= 0; k--)
{
if (computer[i][j] < computer[k][j])
{
swap(computer[i][j], computer[k][j]);
}
}
}
}
cout << "排序后：" << endl;
marbleShow(computer);//输出算盘
for (int i = 0; i < 5; i++)//统计数据
{
int cnt = 0;
for (int j = 0; j < 5; j++)
{
if (computer[i][j] == 1)
{
cnt++;
}
}
arr[i] = cnt;
}
}
//-------------------------------------//面条排序
void nuddleSort(int arr[])//面条排序实现
{
int arrSave[5] = { 0 };
int hand = 1;//手
int min = 1;//下限
for (int i = 0; i < 5; i++)
{
for (int j = 1; j < 6; j++)
{
if (arr[j] > arr[hand])
{
hand = j;//手碰到最长的一根面条
}
}
arrSave[i] = arr[hand];//保存最长的面条
arr[hand] = arr[min];//把最长的面条删除（变成最短的）
}
cout << "面条排序（降序）：" << endl;
for (int i = 0; i < 5; i++)
{
cout << arrSave[i] << " ";
}
cout << endl;
}
//-------------------------------------------------------------------//主函数
void monkeySort_main()
{
int arr[10] = { 0 };//arr[0]记录数组元素个数，arr[1-6]记录排序元素
readData(arr);
cout << "原始数据：" << endl;
monkeyShow(arr);//原始数据
cout << "猴子排序(升序)：" << endl;
monkeySort(arr);//猴子排序实现
}
void marbleSort_main()
{
int arr[] = { 3,2,4,5,1 };
marbleSort(arr);//珠排序实现
cout << "把二维数组转换为一维数组：" << endl;
for (int i = 0; i < 5; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void nuddleSort_main()
{
int arr[10] = { 0 };
readData(arr);
nuddleSort(arr);//面条排序实现
}
int main()
{
monkeySort_main();//猴子排序
cout << "---------------------------------------------" << endl;
marbleSort_main();//珠排序
cout << "---------------------------------------------" << endl;
nuddleSort_main();//面条排序
system("pause");
return 0;
}