蓝桥杯算法基础 (12)：十大排序算法（选择排序）（插入排序） c 语言通用版

选择排序 

选择排序的基本思想是冒泡排序，找到最小值，与未排序部分的第一个元素进行交换
前面为已排序部分，后面为未排序部分
选择排序需要用到三个指针
第一个指针:从第一个元素开始，每次与最小值交换位置
第二个指针:从第一个指针所在位置开始，记录未排序部分最小值的位置
第三个指针:从第一个指针所在位置开始，往后找比k所在位置元素小的元素，找到后，k指向此位置


 int selectSort(int arr[],int length){
        for(int i=0;i<length;i++){//第一个指针
        int k=i;//第二个指针
            for(int j=i+1;j<length;j++)
            {
            if(arr[j]<arr[k]){
             k=j;//记录最小值
            }
            //将最小值放到i位置即未排序部分第一个元素
            temp=arr[i];
            arr[i]=arr[k];
            arr[k]=temp;
            }
        }
 }

插入排序

将当前元素，插入到已排序部分中

 优点是:当原始序列已经基本有序时，再将一个新的数据插入进来比较方便，也比较高效率


左方为已排序部分，右方为未排序部分

两者代码，选择自己认为合适的，也可以都学
 void insertSort1(int arr[],int length){
        int target;
        for(int i=0;i<length;i++){
        target=arr[i];
            for(int j=i;j>=0;j--){
            if(arr[j]<arr[i]){
            arr[j+1]=arr[j];
            }
            }
            arr[j]=target;
        }

 }



 void insertSort2(int arr[],int length){
       //有冒泡的影子，类似于倒着排的冒泡
        for(int i=0;i<length;i++){
            for(int j=i;j>=1&&arr[j]<arr[j-1];j--){
                int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }

        }

 }