四个排序，排序

秒速五厘米 2022-09-12 06:43 129阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6KW_55OcTFhG_size_20_color_FFFFFF_t_70_g_se_x_16]  
1、冒泡排序  
冒泡排序就是把最大值向后移，依次把相邻两个数比较，前面数大就交换，首先依次0（n-1）个数相邻比较，,再0（n-2）个数相邻比较,直到0~1

void bubbing_sort(int num_list[],int lenth)
    {
        
        for (int i = 0; i < lenth; i++)
        {
        
            for (int j = 0; j < lenth - 1 -i; j++)
            {
        
                if (num_list[j] > num_list[j+1])
                {
        
                    int a = num_list[j];
                    num_list[j] = num_list[j+1];
                    num_list[j+1] = a;
                }
            }
        }
    }

2、选择排序  
找出最小值，放在最前，依次使用啊a\[0\]与a\[1\]~a\[N-1\]比较，记下最小数的索引index，然后a\[0\]与a\[index\]互换，然后a\[1\]与a\[2\]-a\[n-1\]比较，记下最小数的索引index，然后a\[1\]与a\[index\]互换.直到a\[n-2\]与a\[n-2\]比较后结束。

void select_sort(int num_list[],int lenth)
    {
        
        for (int i = 0; i < lenth; i++)
        {
        
            int index = i;
            for (int j = i + 1; j < lenth; j++)
            {
        
                if (num_list[j] < num_list[index])
                {
        
                    index = j;
                }
            }
            int a = num_list[i];
            num_list[i] = num_list[index];
            num_list[index] = a;
        }
    }

3、插入排序  
依次判断1~（n-1）对应的数，放到该排在的位置。  
首先a\[1\]-a\[0\]比较，a\[1\]小就把a\[1\],a\[0\]互换，然后，a\[2\]和a\[1\],a\[0\]比较，若a\[2\]>a\[1\],不变，若a\[2\]>a\[0\],把a\[2\]放到a\[1\],a\[1\]放到a\[2\]（这里不是互换，而是平移）,若a\[2\]<a\[0\].a\[2\]放到a\[0\],a\[0\]放到a\[1\],a\[1\]放到a\[2\]…

void insert_sort(int num_list[],int lenth)
    {
        
        for (int i = 1; i < lenth; i++)
        {
        
            int a_i = num_list[i];
            int j = i - 1;
            for (; j >= 0; j--)
            {
        
                if (a_i < num_list[j])
                {
        
                    num_list[j + 1] = num_list[j];
                }
                else
                {
        
                  break;
                }
            }
            num_list[j + 1] = a_i;
        }
    }

4、希尔排序  
希尔排序又叫缩小增量排序。是简单插入排序的改进版。分组进行排序，如下，分成每两个一组，每四个一组…；每组进行排序。

void shell_sort_1(int num_list[], int len)
    {
        
        const int seg = 2;
        for (int gap = len/seg; gap > 0; gap /= seg)
        {
        
            for (int i = gap; i < len; i++ )
            {
        
                int temp = num_list[i];
                int j = i - gap;
                for (; j >= 0 && num_list[j] > temp;j -= gap)
                {
        
                    num_list[j + gap] = num_list[j];
                }
                num_list[j + gap] = temp;
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6KW_55OcTFhG_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f7e77411a7b24f2d917e66e7b4fdf9e2.png