【趣学C语言和数据结构100例】

问题描述

86.直接插入排序算法

87.折半插入排序算法

88.冒泡排序算法

89.快速排序算法

90.简单选择排序算法

代码分析

==86.直接插入排序算法 o(n*n)==
基本思想：将一个记录插入到前面已经排好序的子序列中，从而得到一个新的有序子序列。 这个过程重复进行，直到所有记录都被插入。

分析：
1.使用哨兵,即舍弃a[0]，从第二个元素开始（i=2），检查当前元素是否小于前一个元素。如果是，则将当前元素存储在a[0]中（作为哨兵）。然后，使用一个内循环（for(j=i-1; a[j]>a[0]; j--)）将比a[0]大的元素向后移动，为插入当前元素腾出位置。最后，将a[0]的值放入正确的位置。

2.不用哨兵，对应一个temp作为存储值

==87.折半插入排序算法==
基本思想：折半插入排序算法与直接插入排序类似，区别在于它使用二分查找来确定插入位置。

分析：
从第三个元素开始，依次将每个元素插入到已排序的部分。使用二分查找找到合适的插入位置。将已排序部分的元素向右移动以腾出空间。将当前元素插入到正确的位置。

==88.冒泡排序算法==
基本思想：重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

分析：
在本次代码中加入，如果某一轮没有发生交换，则提前结束排序。

==89.快速排序算法 分治法 有序o(nn) 无序和平均o(nlog 2 n)==
基本思想：
1.选择基准 (Pivot): 从数组中选择一个元素作为基准。 这段代码选择第一个元素 a[low] 作为基准。
2.划分 (Partition): 将数组划分成两个子数组：一个子数组包含所有小于基准的元素，另一个子数组包含所有大于等于基准的元素。 基准元素位于两个子数组之间。 partition 函数完成这个划分过程。
3.递归排序: 递归地对两个子数组进行排序。 func 函数完成这个递归过程。

分析
partition 函数: 这个函数实现数组的划分。它使用两个指针 low 和 high，分别从数组的两端向中间移动。 high 指针寻找小于基准的元素，low 指针寻找大于等于基准的元素。 找到后，交换两个指针指向的元素。 这个过程重复进行，直到 low 和 high 指针相遇。 最后，将基准元素放置在 low 指针的位置。
func 函数: 这个函数是快速排序算法的主函数。它接收数组和排序范围 low 和 high 作为输入。 如果 low < high，则表示排序范围有效，算法进行以下步骤：调用 partition 函数进行划分，得到基准元素的位置 p。递归地对左子数组 a[low...p-1] 和右子数组 a[p+1...high] 进行排序。

==90.简单选择排序算法==
基本思想：
在未排序的数组中找到最小（或最大）的元素，将其与未排序部分的第一个元素交换位置。 重复这个过程，直到整个数组有序。

分析
1.外循环 for(int i=0; i<n-1; i++): 控制排序的轮数。 每一轮都会找到未排序部分的最小元素。
2.最小值索引 min = i: min 变量存储当前轮次中最小元素的索引，初始值为 i（未排序部分的第一个元素）。
3.内循环 for(int j=i+1; j<n; j++): 遍历未排序部分的数组，寻找最小元素。 如果找到更小的元素，则更新 min 的值。
4.交换元素: 如果 min 不等于 i，则说明找到了比 a[i] 更小的元素，需要交换 a[i] 和 a[min] 的值。

代码实现

#include<stdio.h>
int main(){
   
//    86.直接插入排序算法  o(n*n)
//哨兵,舍弃a[0]
//从第二个元素开始（i=2），检查当前元素是否小于前一个元素。
//如果是，则将当前元素存储在a[0]中（作为哨兵）。
//然后，使用一个内循环（for(j=i-1; a[j]>a[0]; j--)）将比a[0]大的元素向后移动，为插入当前元素腾出位置。
//最后，将a[0]的值放入正确的位置。
void func(int a[],int n){
    
    for(int i=2;i<=n;i++){
   
        if(a[i]<a[i-1]){
   
            a[0]=a[i];
            int j;
            for(j=i-1;a[j]>a[0];j--){
   
                a[j+1]=a[j];    
            }
            a[j+1]=a[0];
        }    
    }    
}  
//不用哨兵
void func(int a[],int n){
    
    for(int i=1;i<=n;i++){
   
        if(a[i]<a[i-1]){
   
            int temp=a[i];
            int j;
            for(j=i-1;a[j]>a[0] && j>=0;j--){
   
                a[j+1]=a[j];    
            }
            a[j+1]=temp;
        }    
    }    
}  

//    87.折半插入排序算法
//从第三个元素开始，依次将每个元素插入到已排序的部分。
//使用二分查找找到合适的插入位置。
//将已排序部分的元素向右移动以腾出空间。
//将当前元素插入到正确的位置。
void Iusort(int a[],int n){
   
    int low,high,mid,i;
    for(i=2;i<=n;i++){
   
        a[0]=a[i];
        low=1;
        high=i-1;
        while(low<=high){
   
            mid=(low+high)/2;
            if(a[mid]>a[0]){
   
                high=mid-1;
            }else{
   
                low=mid+1;
            }
        }    
        for(int j=i-1;j>=low;j--){
   
            a[j+1]=a[j];
        }
        a[high+1]=a[0]; 
    }
}

//    88.冒泡排序算法
void func(int a[],int n){
   
    for(int i=0;i<n;i++){
   
        bool flag=false;    //flag，用于标记在当前轮次是否发生了交换。如果没有发生交换，说明数组已经有序，可以提前结束排序。
        for(int j=n-1;j>i;j--){
   
            if(a[j]<a[j-1]){
   
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
            }
        }
        if(flag==true){
   
            return;
        }    
    }
}

//    89.快速排序算法   分治法    有序o(n*n)   无序和平均o(n*log 2 n)
int partition(int a[],int low,int high){
   
    int pivot=a[low];    //基准值
    while(low<high){
   
        while(low<high){
       //防止越界 
            high--;
        }
        a[low]=a[high];
        while(low<high && a[low]<=pivot ){
       //防止越界 
            low++;
        }
        a[high]=a[low];
    }
    a[low]=pivot;
    return low;
}
void func(int a[],int low,int high){
   
    if(low<high){
   
        int p=partition(a,low,high);    //分左右 
        func(a,low,p-1);
        func(a,p+1,high);
    }    
}

//    90.简单选择排序算法   //每次选择最小 
void func(int a[],int n){
   
    for(int i=0;i<n-1;i++){
   
        int min=i;
        for(int j=i+1;j<n;j++){
   
            if(a[i]<a[min]){
   
                min=j;
            }
        }
        if(i!=min){
   
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
    }
}    


    return 0;
}

总结

本文介绍了几种常用的排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序，并通过C语言实现了这些算法。这些算法各有特点，适用于不同的场景，是计算机科学中的基础内容。

直接插入排序是一种简单直观的排序方法，它通过构建有序序列，将一个记录插入到已排序的序列中。这种方法类似于我们整理扑克牌时的操作，时间复杂度为O(n^2)，在数据量较小或基本有序的情况下效率较高。

折半插入排序是直接插入排序的改进版，它使用二分查找来减少比较次数，从而提高插入排序的效率。这种方法在插入位置确定上更为高效，但移动元素的次数与直接插入排序相同。

冒泡排序以其“冒泡”至序列顶端的特性而得名，通过重复遍历待排序序列，比较并交换相邻元素，直至没有需要交换的元素为止。冒泡排序的时间复杂度为O(n^2)，且可以通过提前结束循环来优化。

快速排序是一种分治法的典型应用，通过选择基准值并将数组划分为两个子数组，然后递归地对子数组进行排序。快速排序在平均情况下时间复杂度为O(nlogn)，是一种非常高效的排序方法，尤其适用于大规模数据集。

简单选择排序通过不断选择未排序部分的最小元素并将其放到已排序序列的末尾来工作。这种方法的时间复杂度也是O(n^2)，实现简单，但在数据量大时效率较低。

这些排序算法的实现不仅展示了算法的多样性，也体现了算法设计的基本思想，如分治、贪心和优化。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些排序算法各有优劣，选择哪种算法取决于具体的应用场景和数据特性。例如，对于基本有序的数据，直接插入排序可能更有效；而对于大规模的随机数据集，快速排序或归并排序可能更为合适。通过这些算法的学习，我们不仅能够提高编程技能，还能够培养解决问题的思维能力。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。