C语言冒泡排序&选择排序&插入排序

怼烎@ 2022-03-02 17:58 353阅读 0赞

因为考试需要，最近看了一点C语言，简单总结一下C语言常见的三大排序算法。

### 冒泡排序 ###

对于冒泡排序，主要采用的是相邻数两两进行比较的思想。假设后一个比前一个大或者小，则将其调换位置，直至所有的数都比较完。如果给定一个大小为n的数组，那么需要比较`n-1`趟，每一趟比较`n-1-i`次 ，i 表示上次循环中已经比较完的下标。写两个循环判断，如需交换则进行交换，如果不需要交换则进行下两个数的比较，直到所有的数比较完。

// 冒泡排序 从小到大
    void bubbleSort(int *a, int len) { 
        int i, j, temp, count1 = 0, count2 = 0;
        for (i = 0; i < len; i++) { 
            for (j = 0; j < len - i - 1; j++) { 
                count1++;
                if (a[j] > a[j + 1]) {  // 判断当前元素是否大于下一个元素，如果大进行交换
                    count2++;
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        printf("总共进行了 %d 次比较, %d 次移动", count1, count2);
    }
    
    int main() { 
        int i;
        int nums[10] = { 10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
        int len = sizeof(nums) / sizeof(int);
    
        printf("冒泡排序前: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
        bubbleSort(nums, len);
        printf("\n");
        printf("冒泡排序后: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
    }

### 选择排序 ###

对于选择排序，首先假定数组的首元素为最大或者最小的。此时就要利用3个变量表示元素的下标。一个表示当前，一个表示找到的最大或者最小的下标，一个用于存放每次循环中最大值的下标。找到最大的下标后赋给每次除非的那个最大的下标。找到之后判断所假设的当前值是否为此次循环的最大值，如果不是，就交换最大与当前的值，从而将数组以一定的顺序排放。

void choiceSort(int *a, int len) { 
        int i, j, temp, min, minIndex, count1 = 0, count2 = 0;
        for (i = 0; i < len; i++) { 
            min = a[i]; // 最小值
            minIndex = i;  // 最小值索引
            for (j = i + 1; j < len; j++) { 
                count1 ++;
                if (a[j] < min) {  // 判断元素是否小于最小值，如果小于最小值将最小值赋值给 min 
                    count2 ++;
                    min = a[j];
                    minIndex = j;
                }
                // 交换位置
                temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
        printf("总共进行了 %d 次比较, %d 次移动", count1, count2);
    }
    
    
    
    int main() { 
        int i;
        int nums[10] = { 10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
        int len = sizeof(nums) / sizeof(int);
    
        printf("选择排序前: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
        choiceSort(nums, len);
        printf("\n");
        printf("选择排序后: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
    }

### 插入排序 ###

插入排序会将目前基本有序的一部分数组提取出来，然后将这部分数组的最右侧的一个元素的右侧元素做标记，将这个元素与前面基本有序的数组进行比较，找到比他稍大的元素，并且移动到比他稍大的元素前面，剩余的未排序元素重复执行上述操作，知道排序结束。所以插入排序的时间复杂度与他的基本有序部分的大小有关，如果数组是正好逆序的，他的时间复杂度甚至不会比，冒泡排序高。

void insertSort(int *a, int len) { 
        int i, j, temp, count1 = 0, count2 = 0;
        for (i = 1; i < len; i++) { 
            j = i - 1;
            temp = a[i];    //需要插入的数据
            while (temp < a[j] && j >=0) {   //当插入的数据小于前面的数据时
                count2 ++;
                a[j+1] = a[j];  //将插入的数据的前面的数据向后移动
                j --;
            }
            count1 ++;
            a[++j] = temp; // 插入数据
        }
        printf("总共进行了 %d 次比较, %d 次插入", count1, count2);
    }
    
    int main() { 
        int i;
        int nums[10] = { 10, 20, 8, 3, 5, 2, 23, 53, 12, 45};
        int len = sizeof(nums) / sizeof(int);
    
        printf("插入排序前: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
        insertSort(nums, len);
        printf("\n");
        printf("插入排序后: ");
        for (i = 0; i < len; i++) { 
            printf("%d ", nums[i]);
        }
    }

### 适用场景 ###

*  冒泡排序：  
    适用于数据量很小的排序场景，因为冒泡原理简单
 *  选择排序：  
    适用于大多数排序场景，虽然他的对比次数较多，但是数据量大的时候，他的效率明显优于冒泡，而且数据移动是非常耗时的，选择排序移动次数少。
 *  插入排序：  
    插入排序适用于已有部分数据有序的情况，有序部分越大越好。

##### ================================================================================ #####

##### 感谢阅读，写得不好的地方请指教，能帮助到你是对我最好的回报，不卑不亢，加油。 #####

##### 请你记住比你优秀的一定比你努力，比你努力的人一定比你优秀。 #####

##### ================================================================================ #####