#include<iostream>
#include<iomanip>
#include<string>
#include<fstream>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<array>
#include<vector>
#include<map>
#include<queue>
using namespace std;
void InsertSort(int* a,int num)
{
for (int i = 1; i <= num; i++)
{
cout << setw(5) << a[i];
}
cout << endl;
for (int i = 2; i <= num; i++)
{
int j;
int temp = a[i];
for (j = i-1; a[j] > temp&&j!=0; j--) //哨兵的关键在于控制for循环不必每次都与0相比较查看是否越界 因为他自己肯定不可能大于他自己
{
a[j + 1] = a[j];
}
a[j+1] = temp;
}
for (int i = 1; i <= num; i++)
{
cout << setw(5) << a[i];
}
cout << endl;
}
void InsertSort_Second(int* A, int num) //带哨兵的插排
{
for (int i = 2; i <= num; i++)
{
int j;
A[0] = A[i];
for ( j = i - 1; A[j] > A[0]; j--)
{
A[j + 1] = A[j];
}
A[j + 1] = A[0];
}
for (int i = 1; i <= num; i++)
{
cout << setw(3) << A[i];
}
cout << endl;
}
void Zheban(int* a, int num)
{
for (int i = 1; i < num; i++)
{
int low = 0;
int high = i + 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] < a[i]) //等于的情况考虑到 稳定性 依然放置在右区间
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
//插入的位置是high+1 因为最后一次比对之后，小于比对值mid位于左侧 比较位置即为插入位置
//如果大于mid位于右侧 则插入位置为mid+1 即为high+1
int temp = a[i];
for (int j = i - 1; j >= high + 1; j--)
{
a[j + 1] = a[j];
}
a[high + 1] = temp;
}
for (int p = 0; p < num; p++)
{
cout << setw(5) << a[p];
}
cout << endl;
}
void xier(int* a, int num)
{
for (int xier = num / 2; xier >= 1; xier = xier / 2) //xier既代表了组的数目 也代表了间距
{
for (int i = xier; i < num; i++)
{
int temp = a[i];
if (a[i] < a[i - xier]) //如果i 小于 i-xier
{
int j;
for ( j = i - xier; a[j] > temp&&j>=0; j = j - xier) //这里不是a[i]是temp 这里务必注意不要出错
{
a[j + xier] = a[j];
}
a[j + xier] = temp;
}
}
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
if (i == 9)
{
cout << endl;
}
}
cout << endl;
}
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
}
void xier2(int* a, int num)
{
for (int gap = num / 2; gap >= 1; gap = gap / 2)
{
for (int i = gap; i < num; i++)
{
int temp = a[i];
int j;
if (a[i] < a[i - gap])
{
for ( j = i - gap; j >= 0 && a[j] > temp; j = j-gap)
{
a[j + gap] = a[j];
}
a[j + gap] = temp;
}
}
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
if (i == 9)
{
cout << endl;
}
}
cout << endl;
}
}
void maopao(int* a, int num)
{
for (int i = 0; i < num - 1; i++)
{
bool flag = false;
for (int j = 1; j < num-i; j++)
{
if (a[j] < a[j - 1])
{
flag = true;
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
if (flag == false)
{
break;
}
}
}
void maopao2(int* a, int num)
{
for (int i = 0; i < num - 1; i++)
{
bool flag=false;
for (int j = num - i-1; j > 0; j--)
{
if (a[j - 1] > a[j])
{
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = a[j];
flag = true;
}
}
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
if (flag==false)
{
break;
}
}
}
void quicksort(int* a, int low, int high)
{
int i = low;
int j = high;
int temp = a[low];
if (low < high)
{
while (i < j)
{
while (a[j] >= temp&& i < j)
{
j--;
}//找到第一个a[j]<temp
a[i] = a[j];
while (a[i] < temp && i < j)
{
i++;
}
a[j] = a[i];
}
//此时i==j i的位置就是存放temp的位置
a[i] = temp;
quicksort(a, low, i-1);
quicksort(a, i + 1, high);
}
}
void quicksort2(int* a, int low, int high)
{
if (low < high)
{
int i = low;
int j = high;
int temp = a[low];
while (i < j)
{
while (i < j && a[j] >= temp) //这个等于号很关键 不然会死循环
{
j--;
}
a[i] = a[j];
while (i < j && a[i] < temp)
{
i++;
}
a[j] = a[i];
}
a[i] = temp;
quicksort(a, low, i - 1);
quicksort(a, i + 1, high);
}
}
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void Wangdao_323_2(int* a, int num)
{
bool flag = true;
for (int i = 0; i < num-1; i++)
{
if (flag) //正向
{
for (int j = i/2; j < num - 1- i/2; j++)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
}
}
}
else
{
for (int j = num - 1 - ceil(i / 2); j >= 1 + i / 2; j--)
{
if (a[j] < a[j - 1])
{
swap(a[j], a[j - 1]);
}
}
}
flag = !flag;
for (int i = 0; i < num; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
}
}
void Wangdao_323_3(int* a,int num)
{
int low = 0; int high = num - 1;
while (low < high) //快速排序的代码 两个相等的时候就可以退出了 不需要再继续算下去 否则出现死循环
{
while (a[low] % 2 == 1&&low<high)
{
low++;
}//表示遇到一个偶数
cout << low;
while (a[high] % 2 == 0&&low<high)
{
high--;
}//表示遇到一个奇数
cout << " " << high << endl;
if (low != high)
{
swap(a[low], a[high]);
}
for (int i = 0; i < 20; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
}
}
void Wangdao_323_5(int* a, int num,int k)
{
int low = 0;
int high = num - 1;
while (true)
{
int temp = a[low];
int templow = low;
int temphigh = high;
while (low < high)
{
while (low<high&&a[high] > temp)
{
high--;
}
swap(a[low], a[high]);
while (low < high && a[low] < temp)
{
low++;
}
swap(a[low], a[high]);
}
a[low] = temp; //此时表示 temp的位置在low标时处
if (low == k-1)
{
cout << "这就是要找的对象" << endl;
cout << temp << endl;
return;
}
else if(low<k) //表示这个值小了 往右侧寻找
{
low = low + 1;
high = temphigh;
}
else
{
low = templow;
high = high - 1;
}
}
}
void Wangdao_324_7(int* a,int num)
{
int low = 0;
int high = num - 1;
while (low < high)
{
while (a[high]==2&&low<high)
{
high--;
}
while (a[low] != 2&&low<high)
{
low++;
}
cout << low << high << endl;
swap(a[low], a[high]);
}
//这样可以将蓝色统一移动到最下方
low = 0;
high =high; //(high必定指向从后往前数第一个不是blue的元素)
while (low < high)
{
while (a[low] == 0&&low<high)
{
low++;
}
while ((a[high] == 1 || a[high] == 2) && low < high)
{
high--;
}
swap(a[low], a[high]);
}
}
void Wangdao_324_7_2(int* a, int num)
{
int redpoint = 0;
int bluepoint = num - 1;
int i = 0;
while(i <= bluepoint)
{
//值得注意的是 检测到红色色块的时候i++ 但是检测到蓝色色块不能i++
//不仅是防止换上来的是蓝色色块 换上来的也可能是任何一种色块
//因为i之前是有序的 但是i之后是无序的
switch (a[i])
{
case 0:
swap(a[redpoint], a[i]);
i++; redpoint++;
break;
case 1:
i++;
break;
case 2:
swap(a[bluepoint], a[i]);
bluepoint--;
break;
}
}
}
int main()
{
int a[20];
for (int i = 0; i < 20; i++)
{
cin >> a[i];
}
Wangdao_324_7(a,20);
for (int i = 0; i < 20; i++)
{
cout << setw(4) << a[i];
}
cout << endl;
/*所用二叉树为
A
B C
# D E F
G H I J # #
# # # # # # K L
## ##
*/
//输入内容为 AB#DG##H##CEI##JK##L##F##
//前序为ABDGHCEIJKLF
//中序为BGHDAIEKJLCF
//后序为GHDBIKLJEFCA
//层序为ABCDEFGHIJKL
}
插入排序 交换排序
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
