简单排序算法（直接插入、简单选择、冒泡）

傷城~ 2023-05-21 10:25 76阅读 0赞

## 简单排序算法 ##

**1. 直接插入排序：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70][]

//直接插入排序：                      
    //从左往右扫描出一个无序序列元素作为待插入关键字，扫描到比它大的已插入关键字就往后移动（循环），直到找到第一个比它小的关键字，就可以把待插入关键字插入
    //两层循环：1.从无序序列中一个个挑选出待插入关键字  2.扫描当前有序序列，需要移动元素则移动
    void insertSort(int arr[],int n)        //整型数组，关键字个数
    {
        int i,j,temp;                       //i为无序序列中的第一个元素，temp为暂存待插入的关键字
        for(i=1; i<n; ++i)                  //下标为0的关键字为有序序列，i循环范围1<i<n，外层循环为无序序列，第一个为有序关键字
        {
            temp = arr[i];                  //最大关键字存入辅助常量
            j = i-1;                        //j为有序序列，无序序列的左边一个为有序序列
            while (j>=0 && temp<arr[j])     //有序序列关键字从0开始，temp小于j扫描到的关键字，内层循环为有序序列
            {
                arr[j+1] = arr[j];          //每扫描到关键字往后移动一位
                --j;                        //下标也往前移动一位
            }
            arr[j+1] = temp;                //指示标志落在最后待插入的前一个位置
        }
    }

**2. 简单选择排序：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1][]

//简单选择排序：
    //从左到右扫描，每次找到最小关键字，移动至无序序列最左边
    void selectSort(int arr[],int n)
    {
        int i,j,k;                          //下标
        int temp;
        for(i=0; i<n; ++i)
        {
            k = i;                          //记录下标
            for (j=i+1 ; j<n; ++j)
                if (arr[k] > arr[j])        //比较最值
                    k = j;                  //把最小值的下标赋值给k
            temp = arr[i];                  //第一个关键字（即i所指关键字）与最小值对调
            arr[i] = arr[k];
            arr[k] =temp;
        }
    }

**3. 冒泡排序：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2][]

//冒泡排序：
    //两两关键字对比，大的关键字移动到右边，一轮循环下来最右边关键字为最大值，后续在无序序列进行多趟操作。
    void bubleSort(int arr[],int n)         //整型数组，关键字个数
    {
        int i,j,flag,temp;
        for(i=n-1; i>=1; --i)               //无序序列的范围
        {
            flag = 0;
            for(j=1; j<=i; ++j)             //扫描当前的无序序列，此处为什么没有j=0?下面有arr[j-1] > arr[j]比较，而下标0前面没有数可以比较
                if(arr[j-1] > arr[j])
                {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] =temp;
    
                    flag = 1;               //有交换，flag变更为1
                }
            if(flag == 0)
                return;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70]: /images/20230521/abb296e80b394fbd84df5a94afff101d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1]: /images/20230521/6a6aabdffb474cb4b1a93f08ff7b0bb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2]: /images/20230521/3ada446365e14f4b8ce16b50a84fdb83.png