插入排序 交换排序


#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
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,236评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,867评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,715评论 0赞 340
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,899评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,895评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,733评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,085评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,722评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,025评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,696评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,816评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,447评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,057评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,009评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,254评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,204评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,561评论 2赞 343